快速排序是不稳定的排序方法, 原因在于 pivot 元素移位的时候可能会造成相等元素之间位置发生变化.
快排的时间复杂度是 O(nlogn), 最差情况时间复杂度是 O(n^2)
一般语言内置的排序函数都是通过快速排序实现的, 其中 JS 的 sort 函数就是快速排序和插入排序实现的.
原始的快速排序算法 (双路快排)
- // 升序排序
- void quick_sort(int s[], int l, int r)
- {
- if (l <r)
- {
- //Swap(s[l], s[(l + r) / 2]); // 将中间的这个数和第一个数交换
- int i = l, j = r, x = s[l];
- while (i < j)
- {
- while(i < j && s[j]>= x) // 从右向左找第一个小于 x 的数
- j--;
- if(i <j)
- s[i++] = s[j];
- while(i < j && s[i] < x) // 从左向右找第一个大于等于 x 的数
- i++;
- if(i < j)
- s[j--] = s[i];
- }
- s[i] = x;
- quick_sort(s, l, i - 1); // 递归调用
- quick_sort(s, i + 1, r);
- }
- }
插入排序的优化
因为当数组规模较小时采用插入排序的效率高于快速排序, 尤其是当数组是经过快速排序处理之后, 所以可以在快排时设置一个阈值, 当分治得到的数组长度小于该阈值时使用插入排序, 这样可以有一定的优化.
随机选取 pivot
三数取中法进行优化
如果原始的数列近似一个排好的升序数列或者降序数列, 再用原始的快排对它进行升序排序时, 就会出现性能问题, 因为每次选择的 pivot 都是第一个数, 分治的时候分得的两个子数组极不平衡, 此时的时间复杂度是 n 的平方. 所以需要进行优化, 优化的方法就是三数取中法, 取 arr[left], arr[mid],arr[right] 三个数的中位数作为 pivot 来进行快排.
当然, 三数取中的方法还有很多种, 也不一定仅仅是对三个数取中
- // 优化后的快排比原始的多一个三数取中的过程
- void dealPivot(int[] arr, int left, int right) {
- int mid = (left + right) / 2;
- if (arr[left]> arr[mid]) {
- swap(arr, left, mid);
- }
- if (arr[left]> arr[right]) {
- swap(arr, left, right);
- }
- if (arr[right] <arr[mid]) {
- swap(arr, right, mid);
- }
- swap(arr, left, mid);
- // 将三个数的中位数放置到左边的位置作为 pivot
- }
三路快排优化
虽然三数取中可以优化数组基本排序好的情况, 但是对于出现很多相同数据的数列, 还是无法优化, 譬如一个数列全是由 1 组成的, 对这个数列进行排序时时间复杂度就是 n 的平方, 因为原始的快排对于大量重复的数据束手无策, 这时就需要进行三路快排, 在遍历的过程中把与 pivot 相同的数收集在数组的两侧, 在 pivot 放置到正确的位置后再将数组两侧收集好的这些相同的数放在 pivot 的两边, 再对除了 pivot 及相同数据以外的数组进行分治快排. 当然在进行三路快排的同时还可以继续使用三数取中, 同时优化.
具体过程: 在处理过程中, 会有两个步骤
第一步, 在划分过程中, 把与 key 相等元素放入数组的两端
第二步, 划分结束后, 把与 key 相等的元素移到枢轴周围
- void QSort(int arr[],int low,int high)
- {
- // high,low 作为移动的游标, first,last 则是保存左右节点, 用于分治
- int first = low;
- int last = high;
- // 这是用来记录与 pivot 相等的数据的游标
- int left = low;
- int right = high;
- // 用来记录聚集在两端的和 pivot 相等的数据的数量
- int leftLen = 0;
- int rightLen = 0;
- // 插入排序的优化
- if (high - low + 1 < 10)
- {
- InsertSort(arr,low,high);
- return;
- }
- // 一次分割
- int key = SelectPivotMedianOfThree(arr,low,high);// 使用三数取中法选择枢轴
- while(low < high)
- {
- while(high> low && arr[high]>= key)
- {
- if (arr[high] == key)// 处理相等元素
- {
- swap(arr[right],arr[high]);
- right--;
- rightLen++;
- }
- high--;
- }
- while(high> low && arr[low] <= key)
- {
- if (arr[low] == key)
- {
- swap(arr[left],arr[low]);
- left++;
- leftLen++;
- }
- low++;
- }
- if(low <high) {
- swap(arr[low], arr[high]);
- }
- }
- arr[low] = key;
- // 一次快排结束
- // 把与枢轴 key 相同的元素移到枢轴最终位置周围
- int i = low - 1;
- int j = first;
- // 如果 arr[i] == key 了说明右边的数都已经和 pivot 相同了, 没必要再继续交换下去了, 继续的交换只是无用功
- while(j < left && arr[i] != key)
- {
- swap(arr[i],arr[j]);
- i--;
- j++;
- }
- i = low + 1;
- j = last;
- while(j> right && arr[i] != key)
- {
- swap(arr[i],arr[j]);
- i++;
- j--;
- }
- // leftLen 和 rightLen 的使用地方
- QSort(arr,first,low - 1 - leftLen);
- QSort(arr,low + 1 + rightLen,last);
- }
来源: http://www.jianshu.com/p/005a8e7db678