1、快速排序概念
快速排序（ quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
设要排序的数组是A[0]…A[n-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
2、算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
3、动画演示
4、过程实例
举个栗子详细的说明一下：下面序列
把第一位57作为基准位，用变量把它存起来，因为一会就没了
- 把所有比57小的数放在57的左面，把比57大的数放在57的右面
- 两边同时进行，左边找大的，右边找小的，把小的放左边，大的放右边，具体操作如下：
第一趟：从指针j开始，24小于57，放到左边，把57覆盖掉
之后：指针i右移，指向68，68>57，放到右边
之后：指针j左移指向33，33<57，放到左边
之后：指针i右移指向59，59>57，放右边
之后：指针j左移指向96，96>57，j再左移指向28，28<57，放左边
之后：指针i右移指向52，52<57,i继续右移指向72，72>57,放右边
之后：指针j左移，与指针i重合指向NULL，这时放入57
这时发现左边的数都比57小，右边都比57大
然后再对57左边的数，即：0到i-1进行快速排序（同样操作，把24作为基准，左边小，右边大），对57右边的数，即：i+1到n进行快速排序（以72位基准，左边小，右边大）直到不能再进行排序为止；
5、算法实例
#include "stdio.h"
void quick_sort(int* arr,int start, int end)
{
int temp = arr[start];
if (start >= end)
return;
int i = start, j = end;
while (i < j)
{
while (i < j && arr[j] >= temp)
{
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= temp)
{
i++;
}
arr[j] = arr[i];
}
arr[i] = temp;
quick_sort(arr, start, i-1);
quick_sort(arr, i+1, end);
}
void print(int* arr, int e)
{
for (int i = 0; i < e; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[10] = { 25,8,79,5,4,15,3,88,14,56 };
quick_sort(arr, 0, 9);
print(arr, 10);
return 0;
}
评论区