排序算法复习——包括插入排序、希尔排序、冒泡排序、快排（包括霍尔法、挖坑法、快慢指针法）、堆排、选择排序、归并排

1.插入排序

        插入排序就像我们打斗地主的时候，有一大把牌我们来不及理，就会一张一张的拿然后把拿到的牌放到合适的位置。

        对于插入排序我们可以将待排序的数组理解为那一堆没有整理的牌，将排序好的部分理解为手上的牌，对于第i张牌我们的i-1张牌是理好的，那么我们只需要将第i张的大小与前面的第i-1张牌比较就可以找到他的位置，具体实现如下

void InsertSort(vector<int> &a, int n) { for (int i = 1; i < n; i++) { int end = i - 1; int tmp = a[i]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else break; } a[end + 1] = tmp; } } 2.希尔排序

        希尔排序是对插入排序的优化，对于插入排序来讲如果数组是有序的那么插入排序的时间复杂度是O(N)，那么如果我们让数组尽可能的有序其实就提升了插入排序的效率，根据这个想法希尔排序就诞生了。

        希尔大佬将待排序的数组根据某个整数分成n组，这n组每一组都采用插入排序，先对这n组排序然后缩小n值再对这n组排序，直到n == 1，其实n == 1的时候就是插入排序，再希尔排序中我们将这个整数称为gap，一般初始gap = 数组大小/2也有的是 gap = 数组大小/3+1，当然了这两种方法的效率应该差的不大具体见下面的图片

void ShellSort(vector<int> &a, int n) { int gap = n; while (gap > 1) { gap /= 2; for (int i = 0; i < gap; i++) { for (int j = i; j < n; j += gap) { int end = j, tmp; if (j + gap < n) tmp = a[j + gap]; else break; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = tmp; } } } }

        我的代码可能不是那么易懂，所以我在这里讲解一下       

        首先我的gap其实第一次分的组数是n/2，对于这gap组我是通过他们的头部来确定整个数组的，就是我的第一个for循环，然后每个组的头部加上gap其实就是这个组内下一个元素的位置，这个时候是有边界条件的如果+gap以后的数大于或者等于数组大小那么就可以不管他了，这就是第二个for循环然后while里是插入排序的逻辑

3.选择排序（很抽象的一个排序，时间复杂度稳定O（N^2））

        简单来说就是遍历数组找到最小的数将他和待排序区间的头元素交换，我们可以进行一定的优化，比如我们既然已经遍历了，就随便把最大的元素也找了一次排两个数效率就提升了一些。

        但是优化后存在一些问题比如你的最大值的位置在待排序左端，但是我们的最小值是需要和待排序左端进行交换的那么交换后最大值的位置是不是就到了原来最小值的位置。所以我们在进行最大值交换的时候需要先判断最大值的位置是不是待排序左端，如果是那么最大值的位置就要修正为原最小值的位置。

        这里先提供一份不优化版的

void SelectSort(vector<int> &a, int n) { for (int i = 0; i < n; i++) { int tmp = a[i], tmpps = i; for (int j = i + 1; j < n; j++) { if (a[j] < tmp) { tmpps = j; tmp = a[j]; } } Swap(a[tmpps], a[i]); } }

        这里是优化版本

void SelectSort(vector<int> &a, int n, int level) { int left = 0, right = n - 1; while (left < right) { int min = a[left], max = a[right]; int minps = left, maxps = right; for (int i = left + 1; i < right; i++) { if (a[i] <= min) { min = a[i]; minps = i; } if (a[i] > max) { max = a[i]; maxps = i; } } // 这里需要修正 如当left与maxps相等时第一次交换会导致a[maxps]的值改变到a[minps] Swap(a[left], a[minps]); if (left == maxps) maxps = minps; Swap(a[right], a[maxps]); left++; right--; } } 4.堆排序

        这里先讲一些堆排序的前置知识，堆的底层是数组，但是逻辑结构是完全二叉树，然后根据完全二叉树的父子关系，以及向上调整完成建堆，然后通过向下调整完成排序。

        

        这是一个大根堆向下调整做降序，所谓向下调整其实就是先将根与最末节点交换然后对除最末节点以外的堆的根进行向下调整，具体就是将这个根与他的子节点中大的的那个交换（如果跟的数组序号是parent那么左孩子节点的数组序号就是child = parent*2+1右孩子就是child+1）直到到叶子位置或者比两个孩子都大时就结束了。

        代码部分包括建堆

// 向上调整建堆 void AdjustUp(vector<int> &a, int n) { for (int i = 1; i < n; i++) { int child = i, parent = (i - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { Swap(a[child], a[parent]); child = parent; parent = (child - 1) / 2; } else break; } } } // 从root位置开始向下调整 void AdjustDwon(vector<int> &a, int n, int root) { int parent = root, child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) child++; if (a[child] > a[parent]) { Swap(a[child], a[parent]); parent = child; child = parent * 2 + 1; for (auto ch : a) std::cout << ch << " "; std::cout << std::endl; } else break; } } // 堆排序 堆的逻辑结构是完全二叉树 底层结构是数组 // 根据parent 可以找到左孩子节点child = parent*2+1 void HeapSort(vector<int> &a, int n) { AdjustUp(a, n); for (auto ch : a) cout << ch << " "; std::cout << std::endl; for (int i = n - 1; i >= 0; i--) { std::cout << "a[0] : " << a[0] << " " << "a[" << i << "] : " << a[i] << "::"; Swap(a[0], a[i]); AdjustDwon(a, i, 0); for (auto ch : a) cout << ch << " "; std::cout << std::endl; } } 5.冒泡排序

        比较简单就是从数组的每一个位置开始将该位置的数与后面的数比较如果该位置大就交换，反之不做处理，直到比较到数组末尾单趟结束，然后从上次开始的位置的后一个位置开始重复。

void BubbleSort(vector<int> &a, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n-i; j++) { if (a[j-1] > a[j]) Swap(a[j-1], a[j]); } } } 6.快速排序 6.1 霍尔大佬版

        简单来说就是选定一个key然后有一个left是这段区域的开头，一个right是这段区域的结尾，然后right先走直到找到小于key的位置停下，然后left开始走直到找到大于key的位置然后交换这两个位置的值，然后重复这个过程直到right和left相遇就将相遇位置的值与key位置的值交换。这样单趟快排就完成了，通过现在key的位置可以将数组划分为两个区域在对这两个区域快排，不断重复就可以完成排序

        

        这里keyi值的选取有三数取中法即：left、rigth、(left+right)/2 的中间值（对应在数组中的值的大小来比较的）来当key这样是为了提高快排在数组相对有序的时的效率。

// 2. 三数取中 int GetMidNumi(vector<int> &a, int left, int right) { int numi = (right + left) / 2; if (a[left] > a[right]) { if (a[right] >= a[numi]) return right; else { if (a[left] >= a[numi]) return numi; else return left; } } else { if (a[left] >= a[numi]) return left; else { if (a[right] >= a[numi]) return numi; else return right; } } } void PartSort1(vector<int> &a, int left, int right) { if (left >= right) return; int begin = left, end = right; // int randi = left + (rand() % (right-left)); 随机取keyi int randi = GetMidNumi(a, left, right); // 三数取中 Swap(a[left], a[randi]); int keyi = left; while (begin < end) { if (a[end] < a[keyi]) { if (a[begin] > a[keyi]) { Swap(a[begin], a[end]); } else { begin++; continue; } } end--; } // 走出循环说明end和begin相遇 Swap(a[end], a[keyi]); keyi = end; PartSort1(a, left, keyi); PartSort1(a, keyi + 1, right); } 6.2 挖坑法

        其实说白了就是先保存keyi对应的数组位置的值key，然后在right找到小于key就直接放到keyi对应位置上然后坑的位置就到了当前right的位置，然后left开始走找到大于key的值的位置就直接将值放到right的位置同时坑的位置到了left重复这个过程直到相遇将key放到相遇位置剩下的和霍尔大佬一样

        

// 快速排序挖坑法 void PartSort2(vector<int> &a, int left, int right) { if (left >= right) return; int keyi = left, key = a[left]; int begin = left, end = right; while (begin < end) { while (begin < end && a[end] >= key) end--; a[keyi] = a[end]; keyi = end; while (begin < end && a[begin] <= key) begin++; a[keyi] = a[begin]; keyi = begin; } a[keyi] = key; PartSort2(a, left, keyi); PartSort2(a, keyi + 1, right); } 6.3 前后指针法

        cur初始化在prev的后一个位置，cur先走cur找小于key的位置，prev的位置不能超过cur，cur不能超出区域，其实就是当cur与prev相差大于一时，我们交换他们两个的值，然后让cur继续走找小当cur刚好越界时prev的位置就是key应该在的位置

// 快速排序前后指针法 void PartSort3(vector<int> &a, int left, int right) { if (left >= right) return; int keyi = left; int prev = left, cur = left + 1; while (cur <= right) { // if(cur <= right) Swap(a[cur++],a[prev++]); if (a[cur] < a[keyi] && ++prev != cur) Swap(a[prev], a[cur]); cur++; } Swap(a[keyi], a[prev]); keyi = prev; PartSort3(a, left, keyi); PartSort3(a, keyi + 1, right); } 7.归并排序

        其是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

        实现起来类似牛客网上的一道合并两个链表的题

合并两个排序的链表_牛客题霸_牛客网 (nowcoder )

        

void _MergeSort(vector<int> &a, int left, int right, vector<int> &tmp) { if (left >= right) return; int mid = (left + right) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int i = left; int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; } while (begin1 <= end1) tmp[i++] = a[begin1++]; while (begin2 <= end2) tmp[i++] = a[begin2++]; for (int i = left; i <= right; i++) a[i] = tmp[i]; } // 归并排序递归实现 void MergeSort(vector<int> &a, int n) { std::vector<int> tmp(n); _MergeSort(a, 0, a.size() - 1, tmp); }