[已解决]关于快速排序的问题

1613551

这个是代码是用快速排序的方式把数组a里面的整形从小到大排列，但是代码好像实现不了，我是不是又哪里理解错了

#include <stdio.h>
#include <stdlib.h>
#define num 9
void mostly(int low, int high, int a[]);
int integrate(int low, int high, int a[]);
void mostly(int low, int high, int a[])
{
    if (low < high)
    {
        int total = integrate(low, high, a);
        mostly(low, total - 1, a);
        mostly(total + 1, high, a);
    }
}
int integrate(int low, int high, int a[])
{
    int p = a[low];
    while (low < high)
    {
        if (p < a[high] && low < high)
        {
            high--;
        }
        a[low] = a[high];
        if (p > a[low] && low < high)
        {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = p;
    return p;
}
int main(void)
{
    int a[num] = {5, 2, 3, 7, 4, 2, 9, 7, 8};
    int low = 0, high = num - 1;

    mostly(low, high, a);
    printf(",%d", a[0]);
    for (int k = 1; k < num; k++)
    {
        printf(",%d", a[k]);
    }
    system("pause");
    return 0;
}

最佳答案

月排行榜 / 总排行榜

xiaosi4081

2022-11-18 19:34:08

写错了刚刚

感觉应该是上面的问题

上面假设遇到两个值的时候怎么办呢？

还帮你小改了一下

pwq

代码：

#include <stdio.h>
#include <stdlib.h>
#define num 9
void mostly(int low, int high, int a[]);
int integrate(int low, int high, int a[]);
void mostly(int low, int high, int a[])
{
        if (low < high-1)
        {        
                int total = integrate(low, high, a);
                mostly(low, total - 1, a);
                mostly(total + 1, high, a);
        }
}
int integrate(int low, int high, int a[])
{
        int p = a[low];
        while (low < high)
        {
                while (p <= a[high] && low < high)
                {
                        high--;
                }
                if(low < high)
                {
                        a[low] = a[high];
                }
                
                while (p > a[low] && low < high)
                {
                        low++;
                }
                
                if(low<high){
                        a[high] = a[low];
                }
        }
        a[low] = p;
        return p;
}
int main(void)
{
        int a[num] = {5, 2, 3, 7, 4, 2, 9, 7, 8};
        int low = 0, high = num - 1;
        
        mostly(low, high, a);
        printf(",%d", a[0]);
        for (int k = 1; k < num; k++)
        {
                printf(",%d", a[k]);
        }
        system("pause");
        return 0;
}

给个最佳答案球球了

跳转到最佳答案楼层

xiaosi4081

不是，建议还是写个一体化递归哈

xiaosi4081

写错了刚刚

感觉应该是上面的问题

上面假设遇到两个值的时候怎么办呢？

还帮你小改了一下

pwq

代码：

#include <stdio.h>
#include <stdlib.h>
#define num 9
void mostly(int low, int high, int a[]);
int integrate(int low, int high, int a[]);
void mostly(int low, int high, int a[])
{
        if (low < high-1)
        {        
                int total = integrate(low, high, a);
                mostly(low, total - 1, a);
                mostly(total + 1, high, a);
        }
}
int integrate(int low, int high, int a[])
{
        int p = a[low];
        while (low < high)
        {
                while (p <= a[high] && low < high)
                {
                        high--;
                }
                if(low < high)
                {
                        a[low] = a[high];
                }
                
                while (p > a[low] && low < high)
                {
                        low++;
                }
                
                if(low<high){
                        a[high] = a[low];
                }
        }
        a[low] = p;
        return p;
}
int main(void)
{
        int a[num] = {5, 2, 3, 7, 4, 2, 9, 7, 8};
        int low = 0, high = num - 1;
        
        mostly(low, high, a);
        printf(",%d", a[0]);
        for (int k = 1; k < num; k++)
        {
                printf(",%d", a[k]);
        }
        system("pause");
        return 0;
}

给个最佳答案球球了

zhangjinxuan

我觉得就写传统的快速排序吧，不要去写一些奇怪易出错的排序

zhangjinxuan

正如二楼说的，用一体化递归

一般我写快排通常就是记代码和思路，之后就一直按这样的代码去写，不然容易出错

#include <stdio.h>
#include <stdlib.h>
#define num 9
void mostly(int low, int high, int a[])
{
    if (low >= high) return;
    int i = low, j = high, t = a[low];
    while (i <= j) {
                while (i <= j && a[i] < t) ++i;
                while (i <= j && a[j] > t) --j;
                if (i <= j) {
                        int t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                        ++i, --j;
                }
        }
        mostly(low, j, a);
        mostly(i, high, a);
}
int main(void)
{
    int a[num] = {5, 2, 3, 7, 4, 2, 9, 7, 8};
    int low = 0, high = num - 1;

    mostly(low, high, a);
    printf(",%d", a[0]);
    for (int k = 1; k < num; k++)
    {
        printf(",%d", a[k]);
    }
    puts("");
    system("pause");
    return 0;
}

zhangjinxuan

xiaosi4081 发表于 2022-11-18 19:34
写错了刚刚

感觉应该是上面的问题

没必要写两个函数吧

你不是说你要用一体化递归吗

我学快排就是把代码记下来，思路能理解就行，之后一直找这样去写即可

xiaosi4081

zhangjinxuan 发表于 2022-11-18 19:50
没必要写两个函数吧

你不是说你要用一体化递归吗

没事，他写这样子他看的懂

xiaosi4081

再领个币，顺便提醒个最佳

1613551

xiaosi4081 发表于 2022-11-18 20:46
再领个币，顺便提醒个最佳

我还在看代码，我大概知道我的问题了

1613551

zhangjinxuan 发表于 2022-11-18 19:50
没必要写两个函数吧

你不是说你要用一体化递归吗

懂了

桃花飞舞

被 xiaosi4081改的可以排序了哎