目录
快速排序
选择排序
插入排序
归并排序
堆排序
总结
Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums &＃61; [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: nums &＃61; [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Constraints:
1 <&＃61; nums.length <&＃61; 50000-50000 <&＃61; nums[i] <&＃61; 50000
题目链接&＃xff1a; Loading...
快速排序
class Solution {
public:void quicksort(vector&nums,int left,int right){if(left>&＃61;right)//此处应该是大于等于&＃xff0c;等于的时候就可以停止了{return ;}int i&＃61;left,j&＃61;right,key&＃61;nums[left];while(i&＃61;key){//选出来的nums[j] 小于 keyj--;}nums[i]&＃61;nums[j];while(i sortArray(vector& nums) {quicksort(nums,0,nums.size()-1);return nums;}
};
快速排序是不稳定的&＃xff0c;为什么呢&＃xff1f;
经过第一次sort后&＃xff0c;对于j&＃xff0c;j&＃61;5就停止了&＃xff0c;对于i&＃xff0c;i一直&＃43;&＃43;到5。
这样赋值后&＃xff0c;红色的9跑到黑色的9后面了。
有的例子就刚好不会变&＃xff0c;下面这种就不会变化。
选择排序
是想复习一下&＃xff0c;但是选择排序复杂度比较高&＃xff0c;过不了。这些排序的复杂度表
堆排序
堆排序&＃xff08;这篇博客说的挺好的排序六 堆排序&＃xff09;是使用大根堆&＃xff08;父节点不小于子节点&＃xff09;&＃xff0c;为啥从下往上调整呢&＃xff0c;看个例子
把3和1调完之后&＃xff0c; 根节点还要调整&＃xff08;因为4是最大的&＃xff0c;4还要和根节点调整&＃xff0c;导致根节点的值换了2次&＃xff0c;从下往上调整&＃xff0c;根节点只需要调整一次就行了&＃xff0c;这样从下往上调整&＃xff0c;所有非叶子节点调整一次&＃xff0c;绝对就是对的了&＃xff0c;不用考虑有的节点是不是还要调整一次&＃xff09;&＃xff0c;一个节点就可能重复调整&＃xff0c;不止一次。从下往上调整&＃xff0c;省去了父节点的二次调整&＃xff0c;简单省事了&＃xff0c;不用考虑二次调整了。
这个例子第一次的调整构造初始堆过程如下图&＃xff1a;
上面这个例子层数有点少&＃xff0c;2种遍历都是调整3次&＃xff0c;但是对于一个节点&＃xff0c;既是父节点又是子节点&＃xff0c;它的子节点还有子节点 &＃xff0c;步骤就上来了&＃xff0c;比如下图的数字4
void heapAdjust(vector & arr, int parent,int N){int largest &＃61; parent;int child&＃61;2*parent&＃43;1;while(childarr[largest]){largest&＃61;child;}if(child&＃43;1arr[largest]){largest&＃61;child&＃43;1;child&＃43;&＃43;;//更新child的值}swap(arr[parent],arr[largest]);//交换parent&＃61;largest;// parent&＃61;child;在没有child大于parent的时候&＃xff0c;largest还是parent&＃xff0c;child是2*parent&＃43;1,所以不能这么写child&＃61;2*child&＃43;1;//child根据child值翻倍&＃xff0c;这样如果么有需要更新的&＃xff0c;parent一直不变&＃xff0c;child一直增大会退出}}void heapSort(vector& nums){for(int i &＃61; nums.size()/2; i >&＃61; 0; i--){//从最后一个非叶子节点开始调整heapAdjust(nums,i,nums.size());}for(int i &＃61; nums.size()-1; i >&＃61; 0; i--){swap(nums[0] , nums[i]);//下标0存放的是调整后最大值&＃xff0c;交换后放到下标 i(当前未排序的最后位置)heapAdjust(nums,0,i);//i表示调整的元素个数&＃xff0c;i从 size()-1 开始}}
堆排序是不稳定的&＃xff0c;看个图&＃xff0c;原先的数组顺序是 1 2 2,调整之后 1 2 2&＃xff0c;黄框是排序一次后的堆结构。
总结
对于这道题&＃xff0c;我把所有排序方法都汇总在一起了
class Solution {
public:
void quickSort(vector&nums,int left,int right){if(left>right){return ;}int i&＃61;left,j&＃61;right,key&＃61;nums[left];while(i&＃61;key){//选出来的nums[j] 小于 keyj--;}nums[i]&＃61;nums[j];while(i&nums){int len&＃61;nums.size();int index&＃61;0;for(int i&＃61;0;i& nums){int len&＃61;nums.size(),tmp&＃61;0,i&＃61;0,j&＃61;0;for(i&＃61;1;i&＃61;0&&tmp& nums,int start,int mid,int last){vector tmp(last-start&＃43;1,0);// vector tmp(nums.size(),0);这一点真的很棒&＃xff0c;考虑数组元素多的时候&＃xff0c;这样初始化很浪费时间&＃xff0c;会超时&＃xff0c;这点leetcode给我上了一课。int i&＃61;start,j&＃61;mid&＃43;1,k&＃61;0;//k记录start位置&＃xff0c;tmp从哪个下标开始while(i<&＃61;mid&&j<&＃61;last){if(nums[i]& nums,int start,int last){if(start & arr, int parent,int N){int largest &＃61; parent;int child&＃61;2*parent&＃43;1;while(childarr[largest]){largest&＃61;child;}if(child&＃43;1arr[largest]){largest&＃61;child&＃43;1;child&＃43;&＃43;;//更新child的值}swap(arr[parent],arr[largest]);//交换parent&＃61;largest;// parent&＃61;child;在没有child大于parent的时候&＃xff0c;largest还是parent&＃xff0c;child是2*parent&＃43;1,所以不能这么写child&＃61;2*child&＃43;1;}// int left &＃61; 2*parent&＃43;1;// int right &＃61; 2*parent&＃43;2;// if(left arr[largest])// largest &＃61; left;// if(right arr[largest])// largest &＃61; right;// if(largest !&＃61; parent){// swap(arr[parent], arr[largest]);// heapAdjust(arr,largest,N);// }}void heapSort(vector& nums){for(int i &＃61; nums.size()/2; i >&＃61; 0; i--){//从最后一个非叶子节点开始调整heapAdjust(nums,i,nums.size());}for(auto it:nums){cout<&＃61; 0; i--){swap(nums[0] , nums[i]);//下标0存放的是调整后最大值&＃xff0c;交换后放到下标 i(当前未排序的最后位置)heapAdjust(nums,0,i);//i表示调整的元素个数&＃xff0c;i从 size()-1 开始}}vector sortArray(vector& nums) {// quickSort(nums,0,nums.size()-1);// selectSort(nums);// insertSort(nums);// mergeSort(nums,0,nums.size()-1);heapSort(nums);return nums;}};
复杂度汇总
京公网安备 11010802041100号