C语言快速排序,C\C++交流,技术交流,鱼C论坛

liyifeng295641 发表于 2024-4-6 22:15:12

C语言快速排序

#include <stdio.h>

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

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

while(left <= right)
{
while(left < right && pivot <= array)
{
right--;
}
swap(array, left, right);
while(left < right && array <= 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);

quick_sort(array, length);

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

return 0;
}

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

FishC 发表于 2024-4-6 22:15:32

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

#include <stdio.h>

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

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

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

   // 从左往右找比基准值大的元素
   while (i < j && array <= 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);

quickSort(array, 0, length - 1);

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

return 0;
}

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

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

希望对你有所帮助！

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

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                         ;
   array = array                   ;
   array = temp                         ;
}

int partition(int array[] , int left , int right)
{
   int pivot = left                            ;
   while(left < right)
   {
            while(left < right && array <= array)// 【修改】
            {
                     right --                   ;
            }
// 【删除】 swap(array , left , right)          ;
            while(left < right && array <= array) // 【修改】
            {
                     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);
   quick_sort(array , length)                   ;
   printf("排序后的结果是:")                   ;
   for(int i = 0 ; i < length ; i ++)                      //【修改】：略有修改，循环内增加 int i 定义
   {
            printf("%d ", array)             ;
   }
   putchar('\n')                               ;
   return 0                                     ;
}

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;
array = array;
array = temp;
}

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

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

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

还是不对啊。

jackz007 发表于 2024-4-7 10:38:42

本帖最后由 jackz007 于 2024-4-7 10:40 编辑

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

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

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

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

jackz007 发表于 2024-4-7 11:01:47

      4 楼代码的错误：
#include <stdio.h>

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

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

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

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

页: [1]

鱼C论坛's Archiver

C语言 快速排序

C语言快速排序