设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › C语言 快速排序
返回列表 发新帖
查看: 424|回复: 5

[已解决]C语言 快速排序

[复制链接]
liyifeng295641
发表于 2024-4-6 22:15:12 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x 
#include <stdio.h>

void swap(int array[], int left, int right)
{
        int temp;
        temp = array[left];
        array[left] = array[right];
        array[right] = temp;
}

int partition(int array[], int left, int right)
{
        int pivot = array[left];

        while(left <= right)
        {
                while(left < right && pivot <= array[right])
                {
                        right--;
                }
                swap(array, left, right);
                while(left < right && array[left] <= pivot)
                {
                        left++;
                }
                swap(array, left, right);
        }

        return left;
}

void quick_show(int array[], int left, int right)
{
        int pivot;

        while(left < right)
        {
                pivot = partition(array, left, right);
                quick_show(array, left , pivot -1);
                quick_show(array, pivot +1, right);
        }

}

void quick_sort(int array[], int length)
{
        int left = 0, right = length -1;
        quick_show(array, left, right);
}

int main()
{
        int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
        int length = sizeof(array) / sizeof(array[0]);

        quick_sort(array, length);
        
        printf("排序后的结果是:");
        int i;
        for(i = 0; i < length; i++)
        {
                printf("%d ", array[i]);
        }
        putchar('\n');

        return 0;
}

@FishC，帮我看下代码哪里有问题？
最佳答案
月排行榜 / 总排行榜
jackz007
2024-4-6 23:09:44
本帖最后由 jackz007 于 2024-4-6 23:37 编辑 
#include <stdio.h>

void swap(int array[] , int left , int right)
{
        int temp                                       ;
        temp = array[left]                             ;
        array[left] = array[right]                     ;
        array[right] = temp                            ;
}

int partition(int array[] , int left , int right)
{
        int pivot = left                               ;
        while(left < right)
        {
                while(left < right && array[pivot] <= array[right])  // 【修改】
                {
                        right --                       ;
                }
// 【删除】     swap(array , left , right)             ; 
                while(left < right && array[left] <= array[pivot])   // 【修改】
                {
                        left ++                        ;
                }
                swap(array , left , right)             ;
        }
        swap(array ,  pivot , left)                    ;             // 【添加】            
        return left                                    ;
}

void quick_show(int array[], int left, int right)
{
        int pivot                                      ;
        while(left < right)
        {
                pivot = partition(array , left, right) ;
                quick_show(array , left , pivot - 1)   ;
                quick_show(array , pivot + 1 , right)  ;
                left ++                                ;            // 【添加】
                right --                               ;            // 【添加】
        }
}

void quick_sort(int array[], int length)
{
        int left = 0 , right = length - 1              ;
        quick_show(array , left , right)               ;
}

int main()
{
        int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9}      ;
        int length = sizeof(array) / sizeof(array[0])  ;
        quick_sort(array , length)                     ;
        printf("排序后的结果是:")                      ;
        for(int i = 0 ; i < length ; i ++)                          //【修改】：略有修改，循环内增加 int i 定义 
        {
                printf("%d ", array[i])                ;
        }
        putchar('\n')                                  ;
        return 0                                       ;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

FishC
发表于 2024-4-6 22:15:32 | 显示全部楼层
你好，你提供的代码有一些问题，我帮你做了一些修改。下面是修正后的快速排序算法的完整代码：
#include <stdio.h>

void swap(int* array, int left, int right)
{
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

int partition(int* array, int left, int right)
{
    int pivot = array[left];  // 将第一个元素作为基准值
    int i = left;  // 左指针
    int j = right;  // 右指针

    while (i < j) {
        // 从右往左找比基准值小的元素
        while (i < j && array[j] >= pivot) {
            j--;
        }
        if (i < j) {
            swap(array, i, j);
            i++;
        }

        // 从左往右找比基准值大的元素
        while (i < j && array[i] <= pivot) {
            i++;
        }
        if (i < j) {
            swap(array, i, j);
            j--;
        }
    }

    return i;  // 返回基准值最终的位置
}

void quickSort(int* array, int left, int right)
{
    if (left < right) {
        int pivotIndex = partition(array, left, right);  // 找到基准值的位置
        quickSort(array, left, pivotIndex - 1);  // 对左半部分递归进行快速排序
        quickSort(array, pivotIndex + 1, right);  // 对右半部分递归进行快速排序
    }
}

int main()
{
    int array[] = {5, 2, 9, 3, 6, 1, 8, 4, 7};
    int length = sizeof(array) / sizeof(array[0]);

    quickSort(array, 0, length - 1);

    printf("排序后的数组：");
    for (int i = 0; i < length; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

这段代码实现了快速排序算法。在 `partition` 函数中，我们选择数组的第一个元素作为基准值，通过比较和交换的操作将比基准值小的元素放到左边，大的元素放到右边，最终返回基准值的位置。然后，我们使用递归的方式对左右两个子数组进行快速排序。

在 `main` 函数中，我们定义了一个测试数组，调用 `quickSort` 函数进行排序，并输出排序后的结果。

希望对你有所帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jackz007
发表于 2024-4-6 23:09:44 | 显示全部楼层    本楼为最佳答案   
本帖最后由 jackz007 于 2024-4-6 23:37 编辑 
#include <stdio.h>

void swap(int array[] , int left , int right)
{
        int temp                                       ;
        temp = array[left]                             ;
        array[left] = array[right]                     ;
        array[right] = temp                            ;
}

int partition(int array[] , int left , int right)
{
        int pivot = left                               ;
        while(left < right)
        {
                while(left < right && array[pivot] <= array[right])  // 【修改】
                {
                        right --                       ;
                }
// 【删除】     swap(array , left , right)             ; 
                while(left < right && array[left] <= array[pivot])   // 【修改】
                {
                        left ++                        ;
                }
                swap(array , left , right)             ;
        }
        swap(array ,  pivot , left)                    ;             // 【添加】            
        return left                                    ;
}

void quick_show(int array[], int left, int right)
{
        int pivot                                      ;
        while(left < right)
        {
                pivot = partition(array , left, right) ;
                quick_show(array , left , pivot - 1)   ;
                quick_show(array , pivot + 1 , right)  ;
                left ++                                ;            // 【添加】
                right --                               ;            // 【添加】
        }
}

void quick_sort(int array[], int length)
{
        int left = 0 , right = length - 1              ;
        quick_show(array , left , right)               ;
}

int main()
{
        int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9}      ;
        int length = sizeof(array) / sizeof(array[0])  ;
        quick_sort(array , length)                     ;
        printf("排序后的结果是:")                      ;
        for(int i = 0 ; i < length ; i ++)                          //【修改】：略有修改，循环内增加 int i 定义 
        {
                printf("%d ", array[i])                ;
        }
        putchar('\n')                                  ;
        return 0                                       ;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

liyifeng295641
 楼主| 发表于 2024-4-7 10:03:40 | 显示全部楼层
jackz007 发表于 2024-4-6 23:09

#include <stdio.h>

void swap(int *array, int left, int right)
{//交换
        int temp;
        temp = array[left];
        array[left] = array[right];
        array[right] = temp;
}

int partition(int *array, int left, int right)
{//比较基准点，大了就放右边，小了就放左边，把left返回
        int pivot = left;
        if(left <= right)
        {
                while(left < right && array[left] <= array[pivot])
                {
                        left++;
                }
                swap(array, left, right);
                while(left < right && array[pivot] <= array[right])
                {
                        right--;
                }
                swap(array, left, right);
        }
        swap(array, pivot, left);

        return left;
}


void quick(int *array, int left, int right)
{
        int pivot;

        if(left < right)
        {
                pivot = partition(array, left, right);
                quick(array, left, pivot -1);
                quick(array, pivot +1, right);
                left++;
                right--;
        }
}


void quick_sort(int *array, int length)
{
        int left = 0;
        int right = length -1;
        quick(array, left, right);
}

int main(void)
{
        int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
        int length = sizeof(array) / sizeof(array[0]);

        quick_sort(array, length);
        printf("排序后的结果是:");

        int i;
        for(i = 0; i < length; i++)
        {
                printf("%d ", array[i]);
        }
        putchar('\n');
        return 0;
}

还是不对啊。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jackz007
发表于 2024-4-7 10:38:42 | 显示全部楼层
本帖最后由 jackz007 于 2024-4-7 10:40 编辑
liyifeng295641 发表于 2024-4-7 10:03
还是不对啊。


           这个所谓改过的代码错误依然很多，为何不直接试试 3 楼的代码？
           3 楼代码的编译、运行实况：
D:\[exercise]\C>g++ -o x x.c

D:\[exercise]\C>x
排序后的结果是:1 2 3 4 5 6 7 8 9

D:\[exercise]\C>
           先有了正确的代码，再对照自己的代码找错误，不一样可以学到东西吗？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

jackz007
发表于 2024-4-7 11:01:47 | 显示全部楼层
         4 楼代码的错误：
#include <stdio.h>

void swap(int *array, int left, int right)
{//交换
        int temp;
        temp = array[left];
        array[left] = array[right];
        array[right] = temp;
}

int partition(int *array, int left, int right)
{//比较基准点，大了就放右边，小了就放左边，把left返回
        int pivot = left;
        while(left < right)                                            // 【错误1】：这里不是 if(left <= right)
        {
                while(left < right && array[pivot] <= array[right])    // 【错误2】：这里不是 while(left < right && array[left] <= array[pivot])
                {
                        right -- ;                                     // 【错误3】：这里不是 left ++
                }
                // swap(array, left, right);                              【错误4】：此句必须删除
                while(left < right && array[left] <= array[pivot])     // 【错误5】：这里不是 while(left < right && array[pivot] <= array[right])
                {
                        left ++ ;                                      // 【错误6】：这里不是 right --
                }
                swap(array , left, right);
        }
        swap(array, pivot, left);

        return left;
}


void quick(int * array, int left, int right)
{
        int pivot;

        while(left < right)                                             // 【错误7】：这里不是 if(left < right)
        {
                pivot = partition(array, left, right);
                quick(array, left, pivot -1);
                quick(array, pivot +1, right);
                left++;
                right--;
        }
}


void quick_sort(int *array, int length)
{
        int left = 0;
        int right = length -1;
        quick(array, left, right);
}

int main(void)
{
        int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
        int length = sizeof(array) / sizeof(array[0]);

        quick_sort(array, length);
        printf("排序后的结果是:");

        int i;
        for(i = 0; i < length; i++)
        {
                printf("%d ", array[i]);
        }
        putchar('\n');
        return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-23 21:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表