数据结构第六课 -----排序-1
https://developer.aliyun.com/article/1498935
快速排序
hoare版本
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
这个图可能有点简陋
时间复杂度：每一次都会把当前数组的每个元素遍历一遍，然后再把key交换， 需要进行log（n）次递归
时间复杂度是：O(n*log(n))
复杂的话,就如同这个一样,这种情况就是有n层, 时间复杂度就是 1+2+3+…+n, 所以时间复杂度就是O(n^2)
//快速排序 void QuickSrot(int* a, int begin, int end) { //当只有一个元素就不用进行了 if (begin >= end) return; int key = begin; int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错 int right = end; while (left < right) { // 找最小 while (left < right) { if (a[right] < a[key]) { break; } right--; } // 找最大 while (left < right) { if (a[left] > a[key]) { break; } left++; } excheng(&a[right], &a[left]); } excheng(&a[right], &a[key]); //左 QuickSrot(a, begin, right - 1); // 右 QuickSrot(a, right + 1, end); }
优化点
三数取中
思路:
我们可以在数组的前后和中间选取中位数,然后把中位数和开头进行交换,
int TriNum(int *a,int begin, int end) { int mid = (begin - end) / 2 + end; if (begin > end) { if (end > mid) { return end; } else if(begin < mid) { return begin; } return mid; } else { if (begin > mid) { return begin; } else if (end < mid) { return end; } else return mid; } } //快速排序 void QuickSrot(int* a, int begin, int end) { //当只有一个元素就不用进行了 if (begin >= end) return; //三数取中 int key = 0; key = TriNum(a, begin, end); exchange(&a[begin], &a[key]); key = begin; int left = begin; int right = end; //普通方法 //int key = begin; //int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错 //int right = end; while (left < right) { // 找最小 while (left < right) { if (a[right] < a[key]) { break; } right--; } // 找最大 while (left < right) { if (a[left] > a[key]) { break; } left++; } excheng(&a[right], &a[left]); } excheng(&a[right], &a[key]); //左 QuickSrot(a, begin, right - 1); // 右 QuickSrot(a, right + 1, end); }
小区间优化
当我们在使用快速排序的时候，一直排序知道递归到还剩下该数组的10%的数没有排序，我们如果使用递归就很对栈的空间浪费很大。那我们可以选择使用插入排序，
//快速排序 void QuickSrot(int* a, int begin, int end) { //当只有一个元素就不用进行了 if (begin >= end) return; if (end - begin + 1 <= 10) { //插入排序 InsertSort(a + begin, end - begin + 1);//我们要清楚要从哪里开始插入排序 } else { //三数取中 int key = 0; key = TriNum(a, begin, end); excheng(&a[begin], &a[key]); key = begin; int left = begin; int right = end; //普通方法,有可能会栈溢出 //int key = begin; //int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错 //int right = end; while (left < right) { // 找最小 while (left < right) { if (a[right] < a[key]) { break; } right--; } // 找最大 while (left < right) { if (a[left] > a[key]) { break; } left++; } excheng(&a[right], &a[left]); } excheng(&a[right], &a[key]); //左 QuickSrot(a, begin, right - 1); // 右 QuickSrot(a, right + 1, end); } }
挖坑法
//挖坑法 void QuickSrot2(int* a, int begin, int end) { if (begin >= end) return; if (end - begin + 1 <= 10) { InsertSort(a + begin, end - begin + 1); } else { //三数取中 int key = TriNum(a, begin, end); excheng(&a[key], &a[begin]); //坑 key = begin; int num = a[key]; int left = begin; int right = end; while (left < right) { //找小 while (left < right) { if (a[right] < num) { a[key] = a[right]; key = right; break; } right--; } //找大 while (left < right) { if (a[left] > num) { a[key] = a[left]; key = left; break; } left++; } } a[key] = num; //左 QuickSrot(a, begin, right - 1); // 右 QuickSrot(a, right + 1, end); } }
前后指针版本
思路:
cur遇见比key大的值,cur++
cur遇见比key小的值,prev++,交换prev和cur的值交换,然后cur++
//前后指针版本 // 快速排序版本3 void QuickSrot3(int* a, int begin, int end) { if (begin >= end) return; int key = TriNum(a, begin, end); excheng(&a[key], &a[begin]); key = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { //cur 比较 if (a[cur] < a[key] && ++prev != cur)//增加++prev != cur可以有效解决相同位置进行交换 { exchange(&a[cur], &a[prev]); } cur++; } exchange(&a[key], &a[prev]); //左 QuickSrot(a, begin, prev - 1); // 右 QuickSrot(a, prev + 1, end); }
疑惑
- 为什么相遇位置比key小
原因:是right先走
两种情况:
(1).R遇见L —>(L和R交换后,R先走)R没有找到比key小的,一直走,直到R遇见L,(特殊情况除外)
(2)L遇见R----->(R找到小了),然后L没有找到比key大的,一直走,直到L遇见R,(特殊情况除外)
