写出一个较好的高速排序程序
- 高速排序是经常使用的排序算法之中的一个，但要想写出一个又快又准的使用程序，就不是那么简单了
须要注意的事项
- 首先要写正确。通常使用递归实现。其递归相当于二叉树展开，因此假设要用迭代实现的话须要使用一个队列来保存兴许遍历信息。
- 高速排序须要找到一个pivot值，假设顺序选择pivot则易造成N^2的复杂度，假设使用随机数则效果最好，但开销又太大，採取三数中值法比較合适。三数中值法指的是选取第一个值，最后一个值，数组中间的值的中值。有文献表明能够提升5%的执行时间。
- 当数组长度较小时，如10个元素下面，最好使用插入排序或者选择排序完毕，以防止复杂度常数因子过大或多次函数调用带来的开销。而递归究竟层数组长度总是会变小的，因此这么做很有必要。
- 在合并前后两部分数组时，採用两边夹方法，在前后两部分各找到一个大于和小于的值再交换。相比通常情况下找到比pivot小的值就进行交换，能提高执行效率。
实现代码
- 代码例如以下。包含插入排序insert_sort，递归函数，三分中值函数三个辅助函数。
- 三分中值函数事实上採用的是插入排序。通过三次比較，确定中值。
- 插值算法使用暂时变量tmp避免了大量swap函数调用。
#include #include #include #include #include #include using namespace std;inline void swap(vector & num, int p, int q){ int t = num[p]; num[p] = num[q]; num[q] = t;}void insert_sort(vector & num){ int tmp, j; for (int i = 1; i < num.size(); i++){ tmp = num[i]; for (j = i - 1; j >= 0 && num[j] > tmp; j--) num[j + 1] = num[j]; num[j + 1] =tmp; }}int quick_sort_sub(vector & num, int p, int q){ if (p >= q) return 0; // if 4 elements or less, use insert sort if (p + 10 > q){ vector tnum(num.begin() + p, num.begin() + q + 1); insert_sort(tnum); for (int i = 0; i < tnum.size(); i++) num[p + i] = tnum[i]; } int idx = quick_three_partition(num, p, q); swap(num, idx, q); int pivot = num[q]; int left = p, right = q - 1; while (1){ while (num[left] < pivot) ++left; while (num[right] >= pivot) --right; if (left < right) swap(num, left, right); else break; } swap(num, left, q); quick_sort_sub(num, p, left - 1); quick_sort_sub(num, left + 1, q); return left;}void quick_sort(vector & num){ quick_sort_sub(num, 0, num.size() - 1);}int main(){ const int n = 10; /*int num_array[n]= {2,1}; vector num(num_array, num_array + n);*/ srand( time(NULL) ); vector num(n); for (auto& e : num) e = rand() % n; quick_sort(num); for (auto& e : num) cout << setw(4) << e << ' '; cout << endl; cout << "vector is sorted? : " << is_sorted(num.begin(), num.end()) << endl; return 0;}
转载请注明作者：Focustc，博客地址为 ，原文链接为