目前，最常见的排序算法大概有七八种，其中“快速排序”（Quicksort）使用得最广泛，速度也较快。
"快速排序"的思想很简单，整个排序过程只需要三步：
（1）在数据集之中，选择一个元素作为"基准"（v）。
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
如果 e>v,向i后移位，纳入>v的范畴。
如果e<v, 将e和j+1元素互换位置
全部元素放好位置之后，处理基准元素v。
交换l和j的位置，这样就使得左侧值均小于v，右侧值均大于v，而v就是它排序后应该放的位置。
代码实现如下。
template<typename T> int __Partition(T arr[], int l, int r){ int v = arr[l]; int j = l; //j保存分界位置 for (int i = l; i <= r; i++){ if (arr[i] < v){ swap(arr[i], arr[j + 1]); j++; } } swap(arr[l], arr[j]); return j; } //对arr[l .... r]进行partition排序 //返回p 使得arr[l...p-1] < arr[p],arr[p+1 ... r] >arr[p] template<typename T> void __QuickSort(T arr[], int l,int r){ if (l <= r){ return; } //当递归到一定数量时，采用插入排序 会提高速度 //if (r - l <= 15){ // insertionSort(arr,l,r); // return; //} int p = __Partition(arr, l, r); __QuickSort(arr, l, p - 1); __QuickSort(arr, p + 1, r); } template<typename T> void QuickSort(T arr[], int n){ __quickSort(arr, 0, n - 1); }
然而，在数组近乎有序的情况下，如果选取第一个元素作为基准值，快速排序耗时较长，其复杂度接近O(n^2)。 解决办法是随机选择数组中的一个元素作为基准值。
代码变动地方如下。
template<typename T> void QuickSort(T arr[], int n){ srand(time(null)); //设置随机种子 __quickSort(arr, 0, n - 1); }
template<typename T> int __Partition(T arr[], int l, int r){ swap(arr[l],arr[rand()%(r-l+1) + l]); //选择一个随机元素和l交换 int v = arr[l]; int j = l; //j保存分界位置 for (int i = l; i <= r; i++){ if (arr[i] < v){ swap(arr[i], arr[j + 1]); j++; } } swap(arr[l], arr[j]); return j; }
此外，对于数组中有大量重复的数组元素时，可以采用以下办法。小于v的元素放在左侧，大于v的元素放在右侧
//方法2，对于有大量重复的数组元素采用的方法 template<typename T> int __partition2(T arr[], int l, int r){ swap(arr[l], arr[rand() % (r - l + 1) + l]); //选择一个随机元素和l交换 对于有序数组将极大提高计算速度 T v = arr[l]; int i = l + 1, j = r; while (true){ while (i <=r && arr[i] < v) i++; while (j >=l+1 && arr[j]>v) j--; if (i >= j) break; swap(arr[i], arr[j]); i++; j--; } swap(arr[l], arr[j]); return j; }