快速排序
快速排序是一种分割的思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列再次重复该过程，直到所有元素都排列在相应位置上为止
快排有几种版本：1、经典hoare法，2、挖坑法，3、前后指针法
hoare法
根据快排的思想，选定一个key值，key值要放到数组的首位置，然后数组的头和尾同时往中间走，头负责找比key大的，尾负责找比key小的，当一个找到时停下来等待另一个找到，两个都找到后进行交换，直至头尾相遇或者头比尾大后直接与key值交换。这样一趟下来就可以确保key值的左边全部比key值小，右边全部比key值大。如以下动图所示：
//单趟Hoare法 int OnceQuickHoare(vector<int>& v, int left, int right) { //记录key值 int key = left; //记录相遇点 int meet = 0; while (left < right) { while (left < right && v[right] >= v[key]) --right; while (left < right && v[left] <= v[key]) ++left; if (left < right) swap(v[left], v[right]); } meet = left; swap(v[meet], v[key]); return meet; }
挖坑法
挖坑法的思路和Hoare有点像，也是左边找大右边找小。不同的是挖坑法并不是原地交换，而是会有一个坑位记录。先把左边作为坑，然后右边找小，找到之后将该值放到坑位，然后更新坑位为找到该值的位置。再从左边找大，把找到的值放在坑位上，再更新一下坑位。如此反复直至头尾相遇，返回相遇位置即可。
以下动图只演示左区间，右区间同理：
//单趟挖坑法 int OnceQuickHole(vector<int>& v, int left, int right) { int key = v[left]; int keyi = left; while (left < right) { while (left < right && v[right] >= key) --right; if (left < right) { v[keyi] = v[right]; keyi = right; } while (left < right && v[left] <= key) ++left; if (left < right) { v[keyi] = v[left]; keyi = left; } } v[keyi] = key; return keyi; }
前后指针法
利用一前一后指针，后指针负责找小，前指针只负责跟着后指针。当后指针找到了小值之后，前指针此时对应并不是大值则前指针走到后指针的位置，后指针继续往后走。若后指针找到小值且前指针对应的值为大值，则两个指针对应的值交换，后指针继续走直至超出数组范围。最后前指针所在的位置和key值一交换就符合了快排的思想
以下动图仅演示单趟：
//单趟前后指针法 int OnceQuickPP(vector<int>& v, int left, int right) { int key = v[left]; int prev = left; int cur = left + 1; while (cur <= right) { if (v[cur] < key && ++prev != cur) swap(v[cur], v[prev]); ++cur; } swap(v[prev], v[left]); return prev; }
递归调用
以上是快排的实现的单趟排序，因为快排每一次都会分为两个区间，以key值为分割。所以一趟排序只能减少一半的数据，还要接着排序分开的区间，可以采用递归的思想，每一次都递归到小区间逐步返回到整体。
//快排 void Quick(vector<int>& v, int begin, int end) { if (begin >= end) return; //每次都取到分割的位置 int keyi = OnceQuickHoare(v, begin, end); //递归左区间 Quick(v, begin, keyi - 1); //右区间 Quick(v, keyi + 1, end); }
优化
对于快排而言，不管哪种方式实现都需要找到一个key值，而这个key值的取值可以是具有针对性的。这里就介绍一种，用首元素，尾元素，中间元素，这三个元素取最中间的那个值。取到中值后再将它与首元素交换，保证key值在数组的头
//三数取中 int GetMidIndex(vector<int>& v, int left, int right){ int mid = left + (right - left) / 2; if (v[left] < v[mid]){ if (v[mid] < v[right]) return mid; else if (v[left] > v[right]) return left; else return right; } else{ if (v[mid] > v[right]) return mid; else if (v[right] > v[left]) return left; else return right; } }
还有一点优化，就是快排这种排序在越接近有序的情况下效率就越低，而上面提及的插入排序在越有序的情况下效率越高。因此当快排到当前区间数值较少时，可以直接使用插入排序。
加上优化后的整体代码
插入排序可以自行编写，上面写的插入排序与这里的参数对不上就不演示了
//快速排序 //三数取中 int GetMidIndex(vector<int>& v, int left, int right){ int mid = left + (right - left) / 2; if (v[left] < v[mid]){ if (v[mid] < v[right]) return mid; else if (v[left] > v[right]) return left; else return right; } else{ if (v[mid] > v[right]) return mid; else if (v[right] > v[left]) return left; else return right; } } //单趟Hoare法 int OnceQuickHoare(vector<int>& v, int left, int right) { // 三数取中 int mid = GetMidIndex(v, left, right); swap(v[left], v[mid]); //记录key值 int key = left; //记录相遇点 int meet = 0; while (left < right) { while (left < right && v[right] >= v[key]) --right; while (left < right && v[left] <= v[key]) ++left; if (left < right) swap(v[left], v[right]); } meet = left; swap(v[meet], v[key]); return meet; } //单趟挖坑法 int OnceQuickHole(vector<int>& v, int left, int right) { // 三数取中 int mid = GetMidIndex(v, left, right); swap(v[left], v[mid]); //记录key值和坑位 int key = v[left]; int keyi = left; while (left < right) { while (left < right && v[right] >= key) --right; if (left < right) { v[keyi] = v[right]; keyi = right; } while (left < right && v[left] <= key) ++left; if (left < right) { v[keyi] = v[left]; keyi = left; } } v[keyi] = key; return keyi; } //单趟前后指针法 int OnceQuickPP(vector<int>& v, int left, int right) { // 三数取中 int mid = GetMidIndex(v, left, right); swap(v[left], v[mid]); //记录key值 int key = v[left]; int prev = left; int cur = left + 1; while (cur <= right) { if (v[cur] < key && ++prev != cur) swap(v[cur], v[prev]); ++cur; } swap(v[prev], v[left]); return prev; } //快排 void Quick(vector<int>& v, int begin, int end) { if (begin >= end) return; //每次都取到分割的位置 int keyi = OnceQuickHole(v, begin, end); //递归左区间 Quick(v, begin, keyi - 1); //右区间 Quick(v, keyi + 1, end); }
非递归法
实现快排最重要的是利用每次的相遇位置分好区间，把每个小区间排好整体也就排好了。那么在实现快排时关键点就变成了找到区间的边界，因此可以利用栈后进先出的性质将边界保存，把左区间的边界先保存，右区间的后保存，这样每次从栈中取出数据就可以模拟出递归的过程。
只要把每个小区间拿到并排好，那么整体自然就排好序了
//快排非递归 void QuickR(vector<int>& v, int begin, int end) { //利用栈 stack<int> s; //先保存整体的区间边界 s.push(begin); s.push(end); //因为栈是后进先出 //所以可以利用插入边界模拟递归分割 //把右区间的边界先插入，左区间的后插入 //这样每次拿出边界进行单趟快排时就可以实现先把左区间全部排完 //再去排右区间 //注意插入左右区间边界，要确保左区间的后插入才能保证先拿出 while (!s.empty()) { //取出右边界 int right = s.top(); s.pop(); //取出左边界 int left = s.top(); s.pop(); //获得分割位置并排序 int keyi = OnceQuickHoare(v, left, right); //插入分割后的右区间的两边界 if (keyi + 1 < right) { s.push(keyi + 1); s.push(right); } //插入分割后的左区间的两边界 if (left < right - 1) { s.push(left); s.push(keyi - 1); } } }
快排总结
实现快排的关键在于分割区间，只要将每个小区间排好序，整体就会排好了
快排是一个效率非常好的排序，像C语言的qsort函数底层就是使用快排实现的
时间复杂度为O(N * logN)，是个不稳定的排序
归并排序
归并排序的思想源自与分治法，其根本思路就是将数组对半分割成一小块一小块，然后把每一小块排好序之后再合并回来，每次合并都排好序再合并，直至全部小块都合并回成原数组。
递归法
代码编写思路：可以采用递归分割每一小块，开辟一块新的空间存储每一小块排序后的数据，每一次排序合并后的数据都放在临时空间中，待放好后再将数据拷贝回原数组。注意的是分割后排序的数据的在原数组的位置和临时数组的位置要保持一致。例如 数据2和0，这两个数据的位置在原数组为下标6和7，那么将它们排序合并后放在临时数组的位置也应该是下标6和7，这样拷贝回去原数组后才能保证这两个数据还是在原来的位置和其他数据就不会冲突。
//归并排序 void OnceMerge(vector<int>& v, int begin, int end, vector<int>& tmp) { if (begin >= end) return; //取中间分割 int mid = (end + begin) / 2; //往左区间递归 OnceMerge(v, begin, mid, tmp); //往右区间 OnceMerge(v, mid + 1, end, tmp); //归并 //左区间和右区间的起始位置与终止位置 int Leftbegin = begin, Leftend = mid; int Rightbegin = mid + 1, Rightend = end; //确保临时数组插入数据时和原数组的位置保持一致 int i = begin; //左右区间比较，较小的数据先插入到临时数组，实现升序 while (Leftbegin <= Leftend && Rightbegin <= Rightend) { if (v[Leftbegin] <= v[Rightbegin]) tmp[i++] = v[Leftbegin++]; else tmp[i++] = v[Rightbegin++]; } //为确保左右区间的数据全部都已经插入临时数组里 //需要对两个区间做最后的判断 while (Leftbegin <= Leftend) tmp[i++] = v[Leftbegin++]; while(Rightbegin <= Rightend) tmp[i++] = v[Rightbegin++]; //拷贝归并后的数据回原数组 for (int j = begin; j <= end; ++j) v[j] = tmp[j]; } void Merge(vector<int>& v) { //借用临时数组 vector<int> tmp(v.size()); OnceMerge(v, 0, v.size() - 1, tmp); }
非递归法
归并的大思路就是分割成一小块然后每一小块排序合并。那么不使用递归去分割也是可以的，一开始就可以将每个数据当成一小块，然后第二次就可以将两个数据当成一小块，以此类推。
所以可以用一个变量来记录当前有多少个数据组成一小块，每次都有2倍的数据当成一小块。但是要考虑奇数个时的越界情况，因此还需要判断是否越界，如果越界了就把多出来的数据当成一小块。
void MergeR(vector<int>& v) { //借用临时数组 vector<int> tmp(v.size()); //记录每一小块的个数 int gap = 1; //当整体为一块时就是最后一次排序 while (gap < v.size()) { //合并每一组时，后一组的起始位置是前一组的最后一个位置 + 1 //通过规律就可得知以下循环条件 for (int j = 0; j < v.size(); j += gap * 2) { //归并 //记录前一小块的区间 int Leftbegin = j, Leftend = j + gap - 1; //记录后一小块的区间 int Rightbegin = Leftend + 1, Rightend = Rightbegin + gap - 1; //判断越界情况 if (Leftend >= v.size()) Leftend = v.size() - 1; if (Rightend >= v.size()) Rightend = v.size() - 1; //临时数组记录合并后的数据 int i = j; while (Leftbegin <= Leftend && Rightbegin <= Rightend) { if (v[Leftbegin] <= v[Rightbegin]) tmp[i++] = v[Leftbegin++]; else tmp[i++] = v[Rightbegin++]; } while (Leftbegin <= Leftend) tmp[i++] = v[Leftbegin++]; while (Rightbegin <= Rightend) tmp[i++] = v[Rightbegin++]; //拷贝归并后的数据回原数组 for (int k = j; k <= Rightend; ++k) v[k] = tmp[k]; } //每一次小块个数翻倍 gap *= 2; } }
归并排序总结
归并排序是一个非常优秀效率不错的排序，其根本思想是分治，利用空间换时间的思想提高效率
时间复杂度为：O(N * logN)
因为需要开辟临时的数组空间，所以空间复杂度为：O(N)
归并排序也是一个稳定的排序
