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

liyifeng295641

1. #include <stdio.h>
   
2. 
   
3. void swap(int array[], int left, int right)
   
4. {
   
5.         int temp;
   
6.         temp = array[left];
   
7.         array[left] = array[right];
   
8.         array[right] = temp;
   
9. }
   
10. 
    
11. int partition(int array[], int left, int right)
    
12. {
    
13.         int pivot = array[left];
    
14. 
    
15.         while(left <= right)
    
16.         {
    
17.                 while(left < right && pivot <= array[right])
    
18.                 {
    
19.                         right--;
    
20.                 }
    
21.                 swap(array, left, right);
    
22.                 while(left < right && array[left] <= pivot)
    
23.                 {
    
24.                         left++;
    
25.                 }
    
26.                 swap(array, left, right);
    
27.         }
    
28. 
    
29.         return left;
    
30. }
    
31. 
    
32. void quick_show(int array[], int left, int right)
    
33. {
    
34.         int pivot;
    
35. 
    
36.         while(left < right)
    
37.         {
    
38.                 pivot = partition(array, left, right);
    
39.                 quick_show(array, left , pivot -1);
    
40.                 quick_show(array, pivot +1, right);
    
41.         }
    
42. 
    
43. }
    
44. 
    
45. void quick_sort(int array[], int length)
    
46. {
    
47.         int left = 0, right = length -1;
    
48.         quick_show(array, left, right);
    
49. }
    
50. 
    
51. int main()
    
52. {
    
53.         int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
    
54.         int length = sizeof(array) / sizeof(array[0]);
    
55. 
    
56.         quick_sort(array, length);
    
57.        
    
58.         printf("排序后的结果是:");
    
59.         int i;
    
60.         for(i = 0; i < length; i++)
    
61.         {
    
62.                 printf("%d ", array[i]);
    
63.         }
    
64.         putchar('\n');
    
65. 
    
66.         return 0;
    
67. }
    

复制代码

@FishC，帮我看下代码哪里有问题？

最佳答案

月排行榜 / 总排行榜

jackz007

2024-4-6 23:09:44

1. #include <stdio.h>
   
2. 
   
3. void swap(int array[] , int left , int right)
   
4. {
   
5.         int temp                                       ;
   
6.         temp = array[left]                             ;
   
7.         array[left] = array[right]                     ;
   
8.         array[right] = temp                            ;
   
9. }
   
10. 
    
11. int partition(int array[] , int left , int right)
    
12. {
    
13.         int pivot = left                               ;
    
14.         while(left < right)
    
15.         {
    
16.                 while(left < right && array[pivot] <= array[right])  // 【修改】
    
17.                 {
    
18.                         right --                       ;
    
19.                 }
    
20. // 【删除】     swap(array , left , right)             ;
    
21.                 while(left < right && array[left] <= array[pivot])   // 【修改】
    
22.                 {
    
23.                         left ++                        ;
    
24.                 }
    
25.                 swap(array , left , right)             ;
    
26.         }
    
27.         swap(array ,  pivot , left)                    ;             // 【添加】            
    
28.         return left                                    ;
    
29. }
    
30. 
    
31. void quick_show(int array[], int left, int right)
    
32. {
    
33.         int pivot                                      ;
    
34.         while(left < right)
    
35.         {
    
36.                 pivot = partition(array , left, right) ;
    
37.                 quick_show(array , left , pivot - 1)   ;
    
38.                 quick_show(array , pivot + 1 , right)  ;
    
39.                 left ++                                ;            // 【添加】
    
40.                 right --                               ;            // 【添加】
    
41.         }
    
42. }
    
43. 
    
44. void quick_sort(int array[], int length)
    
45. {
    
46.         int left = 0 , right = length - 1              ;
    
47.         quick_show(array , left , right)               ;
    
48. }
    
49. 
    
50. int main()
    
51. {
    
52.         int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9}      ;
    
53.         int length = sizeof(array) / sizeof(array[0])  ;
    
54.         quick_sort(array , length)                     ;
    
55.         printf("排序后的结果是:")                      ;
    
56.         for(int i = 0 ; i < length ; i ++)                          //【修改】：略有修改，循环内增加 int i 定义
    
57.         {
    
58.                 printf("%d ", array[i])                ;
    
59.         }
    
60.         putchar('\n')                                  ;
    
61.         return 0                                       ;
    
62. }

复制代码

跳转到最佳答案楼层

FishC

你好，你提供的代码有一些问题，我帮你做了一些修改。下面是修正后的快速排序算法的完整代码：

1. #include <stdio.h>
   
2. 
   
3. void swap(int* array, int left, int right)
   
4. {
   
5.     int temp = array[left];
   
6.     array[left] = array[right];
   
7.     array[right] = temp;
   
8. }
   
9. 
   
10. int partition(int* array, int left, int right)
    
11. {
    
12.     int pivot = array[left];  // 将第一个元素作为基准值
    
13.     int i = left;  // 左指针
    
14.     int j = right;  // 右指针
    
15. 
    
16.     while (i < j) {
    
17.         // 从右往左找比基准值小的元素
    
18.         while (i < j && array[j] >= pivot) {
    
19.             j--;
    
20.         }
    
21.         if (i < j) {
    
22.             swap(array, i, j);
    
23.             i++;
    
24.         }
    
25. 
    
26.         // 从左往右找比基准值大的元素
    
27.         while (i < j && array[i] <= pivot) {
    
28.             i++;
    
29.         }
    
30.         if (i < j) {
    
31.             swap(array, i, j);
    
32.             j--;
    
33.         }
    
34.     }
    
35. 
    
36.     return i;  // 返回基准值最终的位置
    
37. }
    
38. 
    
39. void quickSort(int* array, int left, int right)
    
40. {
    
41.     if (left < right) {
    
42.         int pivotIndex = partition(array, left, right);  // 找到基准值的位置
    
43.         quickSort(array, left, pivotIndex - 1);  // 对左半部分递归进行快速排序
    
44.         quickSort(array, pivotIndex + 1, right);  // 对右半部分递归进行快速排序
    
45.     }
    
46. }
    
47. 
    
48. int main()
    
49. {
    
50.     int array[] = {5, 2, 9, 3, 6, 1, 8, 4, 7};
    
51.     int length = sizeof(array) / sizeof(array[0]);
    
52. 
    
53.     quickSort(array, 0, length - 1);
    
54. 
    
55.     printf("排序后的数组：");
    
56.     for (int i = 0; i < length; i++) {
    
57.         printf("%d ", array[i]);
    
58.     }
    
59.     printf("\n");
    
60. 
    
61.     return 0;
    
62. }

复制代码

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

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

希望对你有所帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

jackz007

1. #include <stdio.h>
   
2. 
   
3. void swap(int array[] , int left , int right)
   
4. {
   
5.         int temp                                       ;
   
6.         temp = array[left]                             ;
   
7.         array[left] = array[right]                     ;
   
8.         array[right] = temp                            ;
   
9. }
   
10. 
    
11. int partition(int array[] , int left , int right)
    
12. {
    
13.         int pivot = left                               ;
    
14.         while(left < right)
    
15.         {
    
16.                 while(left < right && array[pivot] <= array[right])  // 【修改】
    
17.                 {
    
18.                         right --                       ;
    
19.                 }
    
20. // 【删除】     swap(array , left , right)             ;
    
21.                 while(left < right && array[left] <= array[pivot])   // 【修改】
    
22.                 {
    
23.                         left ++                        ;
    
24.                 }
    
25.                 swap(array , left , right)             ;
    
26.         }
    
27.         swap(array ,  pivot , left)                    ;             // 【添加】            
    
28.         return left                                    ;
    
29. }
    
30. 
    
31. void quick_show(int array[], int left, int right)
    
32. {
    
33.         int pivot                                      ;
    
34.         while(left < right)
    
35.         {
    
36.                 pivot = partition(array , left, right) ;
    
37.                 quick_show(array , left , pivot - 1)   ;
    
38.                 quick_show(array , pivot + 1 , right)  ;
    
39.                 left ++                                ;            // 【添加】
    
40.                 right --                               ;            // 【添加】
    
41.         }
    
42. }
    
43. 
    
44. void quick_sort(int array[], int length)
    
45. {
    
46.         int left = 0 , right = length - 1              ;
    
47.         quick_show(array , left , right)               ;
    
48. }
    
49. 
    
50. int main()
    
51. {
    
52.         int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9}      ;
    
53.         int length = sizeof(array) / sizeof(array[0])  ;
    
54.         quick_sort(array , length)                     ;
    
55.         printf("排序后的结果是:")                      ;
    
56.         for(int i = 0 ; i < length ; i ++)                          //【修改】：略有修改，循环内增加 int i 定义
    
57.         {
    
58.                 printf("%d ", array[i])                ;
    
59.         }
    
60.         putchar('\n')                                  ;
    
61.         return 0                                       ;
    
62. }

复制代码

liyifeng295641

jackz007 发表于 2024-4-6 23:09

1. #include <stdio.h>
   
2. 
   
3. void swap(int *array, int left, int right)
   
4. {//交换
   
5.         int temp;
   
6.         temp = array[left];
   
7.         array[left] = array[right];
   
8.         array[right] = temp;
   
9. }
   
10. 
    
11. int partition(int *array, int left, int right)
    
12. {//比较基准点，大了就放右边，小了就放左边，把left返回
    
13.         int pivot = left;
    
14.         if(left <= right)
    
15.         {
    
16.                 while(left < right && array[left] <= array[pivot])
    
17.                 {
    
18.                         left++;
    
19.                 }
    
20.                 swap(array, left, right);
    
21.                 while(left < right && array[pivot] <= array[right])
    
22.                 {
    
23.                         right--;
    
24.                 }
    
25.                 swap(array, left, right);
    
26.         }
    
27.         swap(array, pivot, left);
    
28. 
    
29.         return left;
    
30. }
    
31. 
    
32. 
    
33. void quick(int *array, int left, int right)
    
34. {
    
35.         int pivot;
    
36. 
    
37.         if(left < right)
    
38.         {
    
39.                 pivot = partition(array, left, right);
    
40.                 quick(array, left, pivot -1);
    
41.                 quick(array, pivot +1, right);
    
42.                 left++;
    
43.                 right--;
    
44.         }
    
45. }
    
46. 
    
47. 
    
48. void quick_sort(int *array, int length)
    
49. {
    
50.         int left = 0;
    
51.         int right = length -1;
    
52.         quick(array, left, right);
    
53. }
    
54. 
    
55. int main(void)
    
56. {
    
57.         int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
    
58.         int length = sizeof(array) / sizeof(array[0]);
    
59. 
    
60.         quick_sort(array, length);
    
61.         printf("排序后的结果是:");
    
62. 
    
63.         int i;
    
64.         for(i = 0; i < length; i++)
    
65.         {
    
66.                 printf("%d ", array[i]);
    
67.         }
    
68.         putchar('\n');
    
69.         return 0;
    
70. }

复制代码

还是不对啊。

jackz007

liyifeng295641 发表于 2024-4-7 10:03
还是不对啊。

           这个所谓改过的代码错误依然很多，为何不直接试试 3 楼的代码？
           3 楼代码的编译、运行实况：

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

复制代码

           先有了正确的代码，再对照自己的代码找错误，不一样可以学到东西吗？

jackz007

         4 楼代码的错误：

1. #include <stdio.h>
   
2. 
   
3. void swap(int *array, int left, int right)
   
4. {//交换
   
5.         int temp;
   
6.         temp = array[left];
   
7.         array[left] = array[right];
   
8.         array[right] = temp;
   
9. }
   
10. 
    
11. int partition(int *array, int left, int right)
    
12. {//比较基准点，大了就放右边，小了就放左边，把left返回
    
13.         int pivot = left;
    
14.         while(left < right)                                            // 【错误1】：这里不是 if(left <= right)
    
15.         {
    
16.                 while(left < right && array[pivot] <= array[right])    // 【错误2】：这里不是 while(left < right && array[left] <= array[pivot])
    
17.                 {
    
18.                         right -- ;                                     // 【错误3】：这里不是 left ++
    
19.                 }
    
20.                 // swap(array, left, right);                              【错误4】：此句必须删除
    
21.                 while(left < right && array[left] <= array[pivot])     // 【错误5】：这里不是 while(left < right && array[pivot] <= array[right])
    
22.                 {
    
23.                         left ++ ;                                      // 【错误6】：这里不是 right --
    
24.                 }
    
25.                 swap(array , left, right);
    
26.         }
    
27.         swap(array, pivot, left);
    
28. 
    
29.         return left;
    
30. }
    
31. 
    
32. 
    
33. void quick(int * array, int left, int right)
    
34. {
    
35.         int pivot;
    
36. 
    
37.         while(left < right)                                             // 【错误7】：这里不是 if(left < right)
    
38.         {
    
39.                 pivot = partition(array, left, right);
    
40.                 quick(array, left, pivot -1);
    
41.                 quick(array, pivot +1, right);
    
42.                 left++;
    
43.                 right--;
    
44.         }
    
45. }
    
46. 
    
47. 
    
48. void quick_sort(int *array, int length)
    
49. {
    
50.         int left = 0;
    
51.         int right = length -1;
    
52.         quick(array, left, right);
    
53. }
    
54. 
    
55. int main(void)
    
56. {
    
57.         int array[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
    
58.         int length = sizeof(array) / sizeof(array[0]);
    
59. 
    
60.         quick_sort(array, length);
    
61.         printf("排序后的结果是:");
    
62. 
    
63.         int i;
    
64.         for(i = 0; i < length; i++)
    
65.         {
    
66.                 printf("%d ", array[i]);
    
67.         }
    
68.         putchar('\n');
    
69.         return 0;
    
70. }

复制代码