希尔排序

希尔排序本质上是对插入排序的一种优化，它既有插入排序的简单，同时也解决了插入排序每次只交换相邻两个元素的缺点。插入排序过程如下：

1.将数组按照一定的间隔分为多个子数组（每跳跃一定间隔取一个值组成一组），每组分别进行插入排序。

2.缩小间隔进行下一轮排序。最后一轮排序时，间隔为 1，也就等同于于直接使用插入排序。由于前面的排序，现在数组已经基本有序了，此时的插入排序只需进行少量的交换即可完成。

举个例子：对数组【2，16，8，1，8，4，7，13，20，3】。

第一轮（设间隔为5）：分割数组为[2,4]，[16,7]，[8,13]，[1,20]，[8,3]，排序后分别为[2,4]，[7,16]，[8,13]，[1,20]，[3,8]。合并排序后的数组为【2，7，8，1，3，4，16，13，20，8】 第二轮（设间隔为2）：分割数组为【2，8，3，16，20】，【7，1，4，13，8】，排序后分别为【2，3，8，16，20】，【1，4，7，8，13】，合并排序后的数组为【2，1，3，4，8，7，16，8，20，13】 第三轮（设间隔为1）：直接进行插入排序，完成整个排序。

void shellSort(vector<int>& nums) {for(int gap=nums.size()/2;gap>0;gap/=2) {//从下标为gap的位置开始，按顺序将每个元素向前插入自己所在组的合适位置for(int i=gap;i<nums.size();i++) {//num开始找合适的位置插入int num=nums[i];//j记录该组的前一个数字下标int j=i-gap;while(j>=0&&num<nums[j]){nums[j+gap]=nums[j];j-=gap}nums[j+gap]=num;}}}

增量序列

每一轮排序的间隔在希尔排序中被称为增量，所有的增量组成的序列称为增量序列

增量序列的选择会极大地影响希尔排序的效率。希尔排序时间复杂度非常难以分析，它的平均复杂度界于 O(n)到 O(n^2)之间，普遍认为它最好的时间复杂度为 O(n^1.3)

堆排序

堆通常是一个可以被看做一棵完全二叉树的数组对象。

根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆/大顶堆；根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆/小顶堆；

堆排序过程如下：

用数列构建出一个大顶堆，取出堆顶的数字；调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；循环往复，完成整个排序。

构建大顶堆有两种方式：

方案一：从 0 开始，将每个数字依次插入堆中，一边插入，一边调整堆的结构，使其满足大顶堆的要求；

方案二：将整个数列的初始状态视作一棵完全二叉树，自底向上调整树的结构，使其满足大顶堆的要求。

方案二更为常用。

在介绍堆排序具体实现之前，我们先要了解完全二叉树的几个性质。将根节点的下标视为 0，则完全二叉树有如下性质：

对于完全二叉树中的第 i 个数，它的左子节点下标：left = 2i + 1

对于完全二叉树中的第 i 个数，它的右子节点下标：right = left + 1

对于完全二叉树中的第 i 个数，它的父节点下标：parent = (i - 1) / 2

对于有 n 个元素的完全二叉树(n≥2)(n≥2)，它的最后一个非叶子结点的下标：n/2 - 1

void heapSort(vector<int>& nums) {//构建初始大顶堆buildMaxHeap(nums);for(int i=nums.size()-1;i>0;i--) {///将最大值交换到最后swap(nums,0,i);//调整剩余数组，使其满足大顶堆maxHeapify(nums,0,i);}}void buildMaxHeap(vector<int>& nums) {// 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标是 nums.size()/2-1for(int i=nums.size()/2-1;i>=0;i--) {maxHeapify(nums,i,nums.size());}}void maxHeapify(vector<int>& nums, int i, int heapSize) {int l=2*i+1; //左子节点索引int r=l+1;//右子节点索引int largest=i;//记录根结点、左子树结点、右子树结点三者中的最大值索引while(l<heapSize&&nums[l]>nums[largest]) {// 与左子树结点比较largest=l;}while(r<heapSize&&nums[r]>nums[largest]) {// 与右子树结点比较largest=r;}if(i!=largest) {swap(nums,i,largest); // 将最大值交换为根结点maxHeapify(nums,largest,heapSize);// 再次调整交换数字后的大顶堆 }}void swap(vector<int>& nums ,int i, int j) {int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}

初始化建堆的时间复杂度为 O(n)，重建堆的时间复杂度为 O(nlog n)O，所以堆排序总的时间复杂度为 O(nlog n)，空间复杂度为O(1)。

快速排序

快速排序算法的基本思想是：

从数组中取出一个数，称之为基数（pivot）

遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域

将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

第一轮遍历排好 1 个基数，第二轮遍历排好 2 个基数，第三轮遍历排好 4 个基数，以此类推。总遍历次数为 logn～n 次，每轮遍历的时间复杂度为 O(n)，所以很容易分析出快速排序的时间复杂度为 O(nlogn)～ O(n^2)，平均时间复杂度为 O(nlogn)。

void quickSort(vector<int>& nums, int start, int end) {// 如果区域内的数字少于 2 个，退出递归if(start >= end)return ;// 将数组分区，并获得中间值的下标int mid = partition(nums, start, end);// 对左边区域快速排序quickSort(nums, start, mid-1);// 对右边区域快速排序quickSort(nums, mid+1, end);}// 将 nums 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标int partition(vector<int>& nums, int start, int end) {// 取第一个数为基数int pivot = nums[start];// 从第二个数开始分区int left = start + 1;// 右边界int right = end;// left、right 相遇时退出循环while(left < right) {// 找到第一个大于基数的位置while(left < right && nums[left] <= pivot) left++;// 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数if(left != right) {swap(nums, left, right);right--;}}// 如果 left 和 right 相等，单独比较 arr[right] 和 pivot, 方便后面交换基数if(left == right && nums[right] > pivot) {right--;}// 将基数和中间数交换if(right != start) {swap(nums, start, right); }// 返回中间值的下标return right;}//交换两个元素void swap(vector<int>& nums, int l, int r) {int temp=nums[l];nums[l]=nums[r];nums[r]=temp;}

除了上述的分区算法外，还有一种双指针的分区算法更为常用：从 left 开始，遇到比基数大的数，记录其下标；再从 right 往前遍历，找到第一个比基数小的数，记录其下标；然后交换这两个数。继续遍历，直到 left 和 right 相遇。

void quickSort(vector<int>& nums, int start, int end) {if(start >= end)return ;int mid = partition(nums, start, end);quickSort(nums, start, mid-1);quickSort(nums, mid+1, end);}int partition(vector<int>& nums, int start, int end) {int pivot = nums[start];int left = start + 1;int right = end;while(left < right) {while(left < right && nums[left] <= pivot) left++;while(left<right && nums[right] > pivot) right--;if(left != right) {swap(nums, left, right);left++;right--;}}if(left == right && nums[right] > pivot) {right--;}if(right != start) {swap(nums, start, right); }return right;}void swap(vector<int>& nums, int l, int r) {int temp=nums[l];nums[l]=nums[r];nums[r]=temp;}

快速排序的时间复杂度上文已经提到过，平均时间复杂度为 O(nlogn)，最坏的时间复杂度为 O(n^2)，空间复杂度与递归的层数有关，每层递归会生成一些临时变量，所以空间复杂度为 O(logn)~O(n)，平均空间复杂度为 O(logn)。

归并排序

归并排序的核心思想是合并有序数组。

有序数组可以通过不断将数组拆分为一个个数组（一个数组拆分成两个数组，两个数组分别拆分成四个数组...），最后每个数组只有一个元素即可视为有序对拆分的数组不断进行合并，保证合并后的数组有序，合并完成时，整个数组排序完成

void mergeSort(vector<int>& nums) {if(nums.size()==0) return;vector<int>ans(nums.size());mergeSortHelp(nums,0,nums.size()-1,ans);}void mergeSortHelp(vector<int>& nums,int start,int end,vector<int>& ans) {if(start==end) return;int mid=start+(end-start)/2;//等价于(start+end)/2,这样处理是为了防止栈(start+end)溢出mergeSortHelp(nums,start,mid,ans);mergeSortHelp(nums,mid+1,end,ans);merge(nums,start,end,ans);}void merge(vector<int>& nums,int start,int end,vector<int>& ans) {int mid=start+(end-start)/2;//start1,start2记录两个数组的开始位置int start1=start;int start2=mid+1;//index1,index2记录遍历两个数组的位置int index1=start1;int index2=start2;while(index1<=mid&&index2<=end) {if(nums[index1]<=nums[index2]) {//ans的索引位置等于start1+（index1-strat1）+(index2-start2).ans[index1+index2-start2]=nums[index1];index1++;//注意，这里ans内的索引包括了index1，所以不要用nums[index1++]，index1++会影响“index1+index2-start2”，这里要将++提到下一行使用。}else{ans[index1+index2-start2]=nums[index2];index2++;}}//将剩下的数组添加到ans中while(index1<=mid) {ans[index1+index2-start2]=nums[index1];index1++;}while(index2<=end) {ans[index1+index2-start2]=nums[index2];index2++;}//将ans中的数字复制到nums中while(start<=end){nums[start]=ans[start];start++;}}

归并排序的复杂度比较容易分析，拆分数组的过程中，会将数组拆分 logn 次，每层执行的比较次数都约等于 n 次，所以时间复杂度是 O(nlogn)。空间复杂度是 O(n)，主要占用空间的就是我们在排序前创建的长度为 n 的 ans数组。

分析归并的过程可知，归并排序是一种稳定的排序算法。其中，对算法稳定性非常重要的一行代码是：

if(nums[index1]<=nums[index2]) {ans[index1+index2-start2]=nums[index1];index1++;}

在这里我们通过arr[index1] <= arr[index2]来合并两个有序数组，保证了原数组中，相同的元素相对顺序不会变化，如果这里的比较条件写成了arr[index1] < arr[index2]，则归并排序将变得不稳定。

总结：

参考：排序算法全解析 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-)