常见排序算法之快速排序

       快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

       基本思想为∶任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return; int div = partion(array, left, right);QuickSort(array, left, div); QuickSort(array, div+1, right);
}

       上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，我们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有:

        1.hoare版本

        2.挖坑法

        3.前后指针版本

下面将介绍三种方法，在此之前我们现需写一个三数取中代码：

int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  {return left;}else{return right;}}else {if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) {return left;}else{return right;}}
}

---

一、hoare版本

具体步骤

1. 先选取数组左边的第一个数作为key，定义一个左下标left指向最左边的数，定义一个右下标right指向最右边的数。
2. 然后让right先往左遍历，找到第一个比key大的值，让left后向右遍历，找到第一个比key小的值。
3. 这时，左边的值都比key小，右边的值都比key大，交换left和right指向的值。
4. 这样一趟排序就结束了，key就在了它应该在的位置上。重复以上步骤，直到整个序列有序。

核心代码

int PartSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){--right;}while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

实验结果

---

二、挖坑法

具体步骤

       首先设置两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。从末尾位置开始，向前遍历，找到第一个小于基准元素的元素，并将其填入起始位置的坑中。然后从起始位置开始，向后遍历，找到第一个大于基准元素的元素，并将其填入上一步所挖的坑中。重复上述步骤，直到起始位置和末尾位置相遇。此时，将基准元素填入最后一个坑中，这样就完成了一次分区操作。最后对分区后的左右两个子数组，分别递归地进行上述步骤。

核心代码

int PartSort2(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];int hole = left;while (left < right){while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

实验结果

---

三、前后指针版本

具体步骤

1. 选择枢轴元素：在数组中选择一个元素作为枢轴，一般选择第一个元素或最后一个元素。

2. 初始化左右指针：左指针指向数组的第一个元素，右指针指向数组的最后一个元素。

3. 划分过程：从前往后遍历数组，当找到一个比枢轴大的元素时，将左指针向右移动一位；从后往前遍历数组，当找到一个比枢轴小的元素时，将右指针向左移动一位。当左指针大于等于右指针时，说明已经找到正确的位置，将枢轴与左指针所在位置的元素交换。

4. 递归处理：将枢轴左边的部分作为新的子数组，递归调用快速排序函数；将枢轴右边的部分作为新的子数组，递归调用快速排序函数。

核心代码 

int PartSort3(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

实验结果

---

四、非递归版本

       快速排序的非递归版本是递归版本的一种优化，主要是通过将递归过程转化为循环来实现。基本思路是将数组分为两部分，一部分比基准值小，另一部分比基准值大，然后对这两部分分别进行快速排序。这个过程可以通过循环来实现，而不是通过递归调用函数自身。

具体步骤

       首先从数组中挑选一个元素作为基准值，然后将所有小于基准值的元素移动到基准值的左边，将所有大于基准值的元素移动到基准值的右边。接下来，对基准值左右两边的子数组分别进行相同的操作，直到数组完全有序。

核心代码

void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (StackEmpty(&st) != 0)
{right = StackTop(&st);StackPop(&st);left = StackTop(&st);StackPop(&st);if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)StackPush(&st, div+1);StackPush(&st, right);StackPush(&st, left);StackPush(&st, div);
}StackDestroy(&s);
}

       感兴趣的同学可以自行练习。

---

五、快速排序特性总结

        1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

        2.时间复杂度:O(N*logN)

        3.空间复杂度:O(logN)

        4.稳定性:不稳定

---

结语：快速排序的相关分享到这里就结束了，希望对大家的学习会有帮助，如果大家有什么问题或者不同的见解，欢迎大家的留言~~~