C语言 快速排序 Quick Sort

算法描述： 快速排序一般是选择数组的第一个数据为对称轴参考值pivot。按照大小数组分割成左右两个区间。然后对左右两个区间再进行递归排序，知道结束为止。

例子演示：

数组：4 3 2 5 1，长度：5，对称轴参考值选择第一个数据4。比它小的我们放到它的右边，比它大的我们放到左边。设置左右两个工作位置。指向开头和末尾。

第一轮：

• 4 3 2 5 1→4 3 2 5 1 开始右边的工作，比较最后一位1是否比4大，否，不复制
• 4 3 2 5 1→5 3 2 5 1 移动右边的工作位置到左一位，比较5是否比4大，是，复制5到左边工作位置上
• 5 3 2 5 1→5 3 2 5 1 切换工作工作位置到左边，比较5是否比4小，否，不复制
• 5 3 2 5 1→5 3 2 3 1 移动左边工作位置到右边一位，比较3是否比4小，是，交换到右边工作位置上
• 5 3 2 3 1→5 3 2 3 1 切换工作方向到右边，比较2是否大于4，否，不用复制
• 5 3 2 3 1→5 4 2 3 1 左右工作结束，把对称轴参考值复制到左边工作位置最后的位置上

第二轮

• 5→5  计算过程仿照第一轮。计算对称轴左边的区间，只有一个数字，完成。
• 2 3 1 → 3 2 1 计算过程仿照第一轮。计算对称轴右边的区间，把2选为对称轴参考值

总结：快速排序算法优点：运算快，操作少，相同的数据长度，只进行了两轮运算。缺点：逻辑复杂，需要处理两个工作方向，有递归。运算不稳定，左右区间可能长度不对称。

1#include <iostream>
2
3void quickSort(int *array, int left, int right)
4{
5    if (left < right)
6    {
7        int pivot = array[left];
8        int leftWorkPos = left;
9        int rightWorkPos = right;
10        while (leftWorkPos < rightWorkPos)
11        {
12            while (leftWorkPos < rightWorkPos && array[rightWorkPos] <= pivot)
13            {
14                rightWorkPos--;
15            }
16            array[leftWorkPos] = array[rightWorkPos];
17            while (leftWorkPos < rightWorkPos && array[leftWorkPos] >= pivot)
18            {
19                leftWorkPos++;
20            }
21            array[rightWorkPos] = array[leftWorkPos];    
22        }
23        array[leftWorkPos] = pivot;
24        quickSort(array, left, leftWorkPos - 1);
25        quickSort(array, leftWorkPos + 1, right);
26    }
27}
28
29int main()
30{
31    int array[] = {1, 7, 9, 2, 4};
32    printf("array before quick sort=");
33    int i = 0;
34    for (i = 0; i < sizeof(array)/sizeof(array[0]); i++)
35    {
36        printf("%d ", array[i]);
37    }
38    printf("\n");
39    quickSort(array, 0, sizeof(array)/sizeof(array[0]) - 1);
40    printf("array after  quick sort=");
41    for (i = 0; i < sizeof(array)/sizeof(array[0]); i++)
42    {
43        printf("%d ", array[i]);
44    }
45    return 0;
46}