912. Sort an Array排序复习快速排序，选择排序，插入排序，归并排序，堆排序

本文主要是介绍912. Sort an Array排序复习快速排序，选择排序，插入排序，归并排序，堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速排序

选择排序

插入排序

归并排序

堆排序

总结

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

题目链接： Loading...

快速排序

class Solution {
public:void quicksort(vector<int>&nums,int left,int right){if(left>=right)//此处应该是大于等于，等于的时候就可以停止了{return ;}int i=left,j=right,key=nums[left];while(i<j){while(i<j&&nums[j]>=key){//选出来的nums[j] 小于 keyj--;}nums[i]=nums[j];while(i<j&&nums[i]<=key)//选出来的nums[i] 大于 key{i++;}nums[j]=nums[i];}nums[i]=key;quicksort(nums,left,i-1);quicksort(nums,i+1,right);}vector<int> sortArray(vector<int>& nums) {quicksort(nums,0,nums.size()-1);return nums;}
};

快速排序是不稳定的，为什么呢？

经过第一次sort后，对于j，j=5就停止了，对于i，i一直++到5。

这样赋值后，红色的9跑到黑色的9后面了。

有的例子就刚好不会变，下面这种就不会变化。

选择排序

是想复习一下，但是选择排序复杂度比较高，过不了。这些排序的复杂度表

void selectSort(vector<int>&nums){int len=nums.size();int index=0;for(int i=0;i<len;i++){index=i;for(int j=i+1;j<len;j++){if(nums[j]<nums[index]){index=j;}}int tmp=nums[i];nums[i]=nums[index];nums[index]=tmp;}}

插入排序

也是超时，原理很简单，在从小到大的排序方法中，就是左边有序序列，新来一个值newvalue,就和左边有序序列比较，只要比我小，我就往右边挪位置,nums[j+1]=nums[j]。

void insertSort(vector<int>& nums){int len=nums.size(),tmp=0,i=0,j=0;for(i=1;i<len;i++){tmp=nums[i];for(j=i-1;j>=0&&tmp<nums[j];j--){nums[j+1]=nums[j];//nums[j]小于 tmp，往后挪位置}nums[j+1]=tmp;//j退出时候,要么j=-1，或者 nums[j]< tmp,那你tmp只能放在 j+1的位置上}}

归并排序

这道题在归并排序上真是给我好好上了一课，之前写的归并排序没有问题，但是有一些额外的空间浪费和时间开销。就是我全行注释那行，如果每次都是按照nums的真实长度来初始化tmp，会浪费时间和空间，这题LeetCode会超时。刚开始我百思不得其解，后来发现是这个问题，真是学习了。我之前写的归并代码：随手写写之归并排序

    void mergeArray(vector<int>& nums,int start,int mid,int last){vector<int> tmp(last-start+1,0);// vector<int> tmp(nums.size(),0);这一点真的很棒，考虑数组元素多的时候，这样初始化很浪费时间，会超时，这点leetcode给我上了一课。int i=start,j=mid+1,k=0;//k记录start位置，tmp从哪个下标开始while(i<=mid&&j<=last){if(nums[i]<nums[j]){tmp[k++]=nums[i++];}else{tmp[k++]=nums[j++];}}while(i<=mid){tmp[k++]=nums[i++];}while(j<=last){tmp[k++]=nums[j++];}for(int t=start;t<=last;t++){nums[t]=tmp[t-start];}}void mergeSort(vector<int>& nums,int start,int last){if(start<last){int mid=(start+last)/2;mergeSort(nums,start,mid);mergeSort(nums,mid+1,last);mergeArray(nums,start,mid,last);}}

堆排序

堆排序（这篇博客说的挺好的排序六堆排序）是使用大根堆（父节点不小于子节点），为啥从下往上调整呢，看个例子

把3和1调完之后，根节点还要调整（因为4是最大的，4还要和根节点调整，导致根节点的值换了2次，从下往上调整，根节点只需要调整一次就行了，这样从下往上调整，所有非叶子节点调整一次，绝对就是对的了，不用考虑有的节点是不是还要调整一次），一个节点就可能重复调整，不止一次。从下往上调整，省去了父节点的二次调整，简单省事了，不用考虑二次调整了。

这个例子第一次的调整构造初始堆过程如下图：

上面这个例子层数有点少，2种遍历都是调整3次，但是对于一个节点，既是父节点又是子节点，它的子节点还有子节点，步骤就上来了，比如下图的数字4

void heapAdjust(vector <int> & arr, int parent,int N){int largest = parent;int child=2*parent+1;while(child<N)//N代表整个数组的元素个数，下标从0开始，child必须小于N{if(arr[child]>arr[largest]){largest=child;}if(child+1<N&&arr[child+1]>arr[largest]){largest=child+1;child++;//更新child的值}swap(arr[parent],arr[largest]);//交换parent=largest;// parent=child;在没有child大于parent的时候，largest还是parent，child是2*parent+1,所以不能这么写child=2*child+1;//child根据child值翻倍，这样如果么有需要更新的，parent一直不变，child一直增大会退出}}void heapSort(vector<int>& nums){for(int i = nums.size()/2; i >= 0; i--){//从最后一个非叶子节点开始调整heapAdjust(nums,i,nums.size());}for(int i = nums.size()-1; i >= 0; i--){swap(nums[0] , nums[i]);//下标0存放的是调整后最大值，交换后放到下标 i(当前未排序的最后位置)heapAdjust(nums,0,i);//i表示调整的元素个数，i从 size()-1  开始}}

堆排序是不稳定的，看个图，原先的数组顺序是 1 2 2,调整之后 1 2 2，黄框是排序一次后的堆结构。

总结

对于这道题，我把所有排序方法都汇总在一起了

class Solution {
public:
void quickSort(vector<int>&nums,int left,int right){if(left>right){return ;}int i=left,j=right,key=nums[left];while(i<j){while(i<j&&nums[j]>=key){//选出来的nums[j] 小于 keyj--;}nums[i]=nums[j];while(i<j&&nums[i]<=key)//选出来的nums[i] 大于 key{i++;}nums[j]=nums[i];}nums[i]=key;quickSort(nums,left,i-1);quickSort(nums,i+1,right);}void selectSort(vector<int>&nums){int len=nums.size();int index=0;for(int i=0;i<len;i++){index=i;for(int j=i+1;j<len;j++){if(nums[j]<nums[index]){index=j;}}int tmp=nums[i];nums[i]=nums[index];nums[index]=tmp;}}void insertSort(vector<int>& nums){int len=nums.size(),tmp=0,i=0,j=0;for(i=1;i<len;i++){tmp=nums[i];for(j=i-1;j>=0&&tmp<nums[j];j--){nums[j+1]=nums[j];//nums[j]小于 tmp，往后挪位置}nums[j+1]=tmp;//j退出时候,要么j=-1，或者 nums[j]< tmp,那你tmp只能放在 j+1的位置上}}void mergeArray(vector<int>& nums,int start,int mid,int last){vector<int> tmp(last-start+1,0);// vector<int> tmp(nums.size(),0);这一点真的很棒，考虑数组元素多的时候，这样初始化很浪费时间，会超时，这点leetcode给我上了一课。int i=start,j=mid+1,k=0;//k记录start位置，tmp从哪个下标开始while(i<=mid&&j<=last){if(nums[i]<nums[j]){tmp[k++]=nums[i++];}else{tmp[k++]=nums[j++];}}while(i<=mid){tmp[k++]=nums[i++];}while(j<=last){tmp[k++]=nums[j++];}for(int t=start;t<=last;t++){nums[t]=tmp[t-start];}}void mergeSort(vector<int>& nums,int start,int last){if(start<last){int mid=(start+last)/2;mergeSort(nums,start,mid);mergeSort(nums,mid+1,last);mergeArray(nums,start,mid,last);}}void heapAdjust(vector <int> & arr, int parent,int N){int largest = parent;int child=2*parent+1;while(child<N)//N代表整个数组的元素个数，下标从0开始，child必须小于N{if(arr[child]>arr[largest]){largest=child;}if(child+1<N&&arr[child+1]>arr[largest]){largest=child+1;child++;//更新child的值}swap(arr[parent],arr[largest]);//交换parent=largest;// parent=child;在没有child大于parent的时候，largest还是parent，child是2*parent+1,所以不能这么写child=2*child+1;}// int left = 2*parent+1;// int right = 2*parent+2;// if(left < N && arr[left] > arr[largest])//     largest = left;// if(right < N && arr[right] > arr[largest])//     largest = right;// if(largest != parent){//     swap(arr[parent], arr[largest]);//     heapAdjust(arr,largest,N);// }}void heapSort(vector<int>& nums){for(int i = nums.size()/2; i >= 0; i--){//从最后一个非叶子节点开始调整heapAdjust(nums,i,nums.size());}for(auto it:nums){cout<<it<<endl;}for(int i = nums.size()-1; i >= 0; i--){swap(nums[0] , nums[i]);//下标0存放的是调整后最大值，交换后放到下标 i(当前未排序的最后位置)heapAdjust(nums,0,i);//i表示调整的元素个数，i从 size()-1  开始}}vector<int> sortArray(vector<int>& nums) {// quickSort(nums,0,nums.size()-1);// selectSort(nums);// insertSort(nums);// mergeSort(nums,0,nums.size()-1);heapSort(nums);return nums;}};