快速排序的三种方法 - 好文

快速排序算法主要用到的基本算法思想是分治算法：排序数组时，将数组分为两个小部分，然后对它们进行递归排序。

在本篇文章中，将采用三种方法实现快速排序。现在有数组a定义为{ 55.3, 55.2, 59.5, 26, 53, 58, 97, 93 }。

第一种

我们给定一个t值，然后重新组织数组a[m...n]，并计算下标p，使得所有小于t的元素在p的一端，所有大于t的元素在p的另一端。我们通过一个从左到右扫描数组的简单for循环完成这一任务。排序过程如下图所示：

代码实现如下所示：
#include <iostream> using namespace std; template <typename T> void swap(T
a[], int m, int n) { T temp = a[m]; a[m] = a[n]; a[n] = temp; } template
<typename T1> void sort_one(T1 a[], int m, int n) { int p=m; T1 t = a[m]; if (m
> n) return; for (int i = m+1; i <= n; i++) { if (a[i] < t) { swap<T1>(a, ++p,
i); } } swap<T1>(a, m, p); sort_one(a,m,p-1); sort_one(a, p + 1, n); } int
main() { double a[]= { 55.3, 55.2, 59.5, 26, 53, 58, 97, 93 };
sort_one<double>(a, 0, 7); for (int i=0; i < 8; i++) cout << a[i]<<","; return
0; }

该快速排序方法能快速完成对随机整数数组的排序。在具有n个相同的数组元素时，采用插入排序时每个元素需要移动的距离都为0，总的运行时间为O(n)；但该方法需要的n-1次划分中都需要O(n)时间来去掉一个元素，所以总的运行时间为O(n)。

第二种

对于上述中出现的问题，我们引入第二种方法，使用双向划分避免上述中的问题。如下图所示：

下标p和q初始化为待划分数组的两端。主循环中有两个内循环，第一个内循环将p向右移过小元素，遇到大元素时停止；第二个内循环将q向左移过大元素，遇到小元素时停止。然后主循环测试这两个下标是否交叉并交换他们的值。

实现代码如下所示：
#include <iostream> using namespace std; template <typename T> void swap(T
a[], int m, int n) { T temp = a[m]; a[m] = a[n]; a[n] = temp; } template
<typename T2> void sort_two(T2 a[], int m, int n) { if (m > n) return; T2 t =
a[m]; int p = m,q=n+1; while (1) { for (p++; p <= n&&a[p] < t; p++); for (q--;
a[q]>t; q--); if (p > q) break; swap<T2>(a, p, q); } swap<T2>(a, m, q);
sort_two(a, m, q - 1); sort_two(a, q + 1, n); } int main() { double a[]= {
55.3, 55.2, 59.5, 26, 53, 58, 97, 93 }; sort_two<double>(a, 0, 7); for (int
i=0; i < 8; i++) cout << a[i]<<","; return 0; }
如果数组已经按升序排好了，那么它就会围绕最小的元素进行划分，然后是第2小的元素，依此类推，总共需要O(n^2)的时间。

第三种

为了解决上述问题，引入随机选择划分元素可以得到好的多的性能，我们通过把a[m]与a[m...n]中的一个随机项交换实现这一点。

代码实现如下所示
#include <iostream> using namespace std; template <typename T> void swap(T
a[], int m, int n) { T temp = a[m]; a[m] = a[n]; a[n] = temp; } template
<typename T3> void sort_three(T3 a[], int m, int n) { if (m > n) return;
swap<T3>(a, a[m], a[rand() % (n - m + 1) + m]); T3 t = a[m]; int p = m, q = n +
1; while (1) { for (p++; p <= n&&a[p] < t; p++); for (q--; a[q]>t; q--); if (p
> q) break; swap<T3>(a, p, q); } swap<T3>(a, m, q); sort_two(a, m, q - 1);
sort_two(a, q + 1, n); } int main() { double a[]= { 55.3, 55.2, 59.5, 26, 53,
58, 97, 93 }; sort_three<double>(a, 0, 7); for (int i=0; i < 8; i++) cout <<
a[i]<<","; return 0; }
本篇中源代码工程文件下载地址：https://github.com/XiaoYaoNet/QuickSort
<https://github.com/XiaoYaoNet/QuickSort>

热门工具换一换