时间复杂度为O ( n 2 ) O(n^{2})O(n2)
下面是时间复杂度为O ( n 2 ) O(n^{2})O(n2)的排序算法：
冒泡排序
- 冒泡排序的思想非常简单，一开始交换的区间是0 ∼ n − 1 ，之后第一个数和第二个数开始比较，将大的数据放在后面。然后是第二个数和第三个数开始比较，哪个大哪个就放在后面，这样交换过去，最大的数据会放在数组的最后一个位置。此时第一轮排序就完成了。
- 之后把数组的范围从0 ∼ n − 1 变为0 ∼ n − 2 ，重新开始排序。这样开始新的一轮冒泡，这样整个数组倒数第二大的数据会放在数组的倒数第二个位置上面。
依次循环做下去，知道数组的范围变成了只有一个数的时候，整个数组排序完成。
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。比如升序排序中nums[j] < nums[j+1]的话，我们就将其交换，让大的数据放在后面。
class Solution { public: vector<int> sortArray(vector<int>& nums) { for(int i=nums.size()-1; i>0; --i){ for(int j=0; j<i; ++j){ if(nums[j] >nums[j+1]) swap(nums[j], nums[j+1]); } } return nums; } };
冒泡排序的最好情况可以达到O ( n )，就是用一个布尔变量记录是否已经全部排好序了，也就是是否交换过了，如果交换过了则为false，否则为true，这样当数组已经是排好序的情况下，我们就不用再做循环了。
选择排序
- 一开始从数组0 ∼ n − 1 上选择一个最小值，然后将其放在位置
0上。 - 然后在1 ∼ n − 1 范围上选择一个最小值，将其放在位置
1上。
依次进行下去，随着范围的缩小，到最终范围里面只有一个元素的时候，整个数组就变成了一个有序数组。
class Solution { public: vector<int> sortArray(vector<int>& nums) { for(int i=0; i<nums.size();++i){ int min_pos = i; // 最小的数字 for(int j=i+1;j<nums.size();++j){ if(nums[j]<nums[min_pos]) min_pos=j; } swap(nums[min_pos], nums[i]); // 最小值的位置和起始位置交换 } return nums; } };
进一步的优化我们可以一次循环遍历的时候找到一个最小值和一个最大值，最小值放到前面，最大值放到后面。
class Solution { public: vector<int> sortArray(vector<int>& nums) { chose_sort(nums, 0, nums.size()-1); return nums; } void chose_sort(vector<int>& nums, int left, int right){ if(left>right) return; int min_pos=left, max_pos=right; // 初始化最小值和最大值的位置 for(int j=left;j<=right;++j){ // 找小的，交换小的 if(nums[j]<nums[min_pos]) min_pos=j; } swap(nums[left], nums[min_pos]); for(int j=left;j<=right;++j){ // 找大的，交换大的 if(nums[j]>nums[max_pos]) max_pos=j; } swap(nums[max_pos], nums[right]); chose_sort(nums, left+1, right-1); } };
插入排序
插入排序的时间复杂度仍然为O ( n 2 ) 。首先是位置0上的数和位置1上的数开始比较：
- 如果位置
1上的数更小，那么它就和位置0上的数开始交换。 - 接下来考察位置
2上的数，将位置2上的数的值记为a，a就和前面的数进行比较。如果它比位置1上的数更小，那么a就和位置1上的数进行交换，交换之后a再和位置0上的数进行比较，如果它还是变小，就和位置0上的数进行比较。 - 接下来对于位置
k上的数，假设它的位置记为b的话，b就依次和前面的数进行比较，如果b一直小于前面的数，就一直进行这样的交换过程。直到它前面的数小于等于b，那么b就插入当前位置。
class Solution { public: vector<int> sortArray(vector<int>& nums) { for(int i=1; i<nums.size(); ++i){ for(int j=i; j>0; --j){ if(nums[j]<nums[j-1]) swap(nums[j], nums[j-1]); } } return nums; }
我们依次从1位置到n − 1 位置，所有的数都进行这样的插入的话，最终整个数组就变成有序了。
时间复杂度为O ( N ∗ l o g N )
以下是时间复杂度为O ( N ∗ l o g N ) 的排序算法：
归并排序
归并排序的时间复杂度为O ( N ∗ l o g N ) 。归并排序首先要将数组中的每一个数成为长度为1的有序区间，然后把相邻的长度为1的有序区间之间进行合并，得到最大长度为2的有序区间。接下来再把相邻有序区间进行合并，得到最大长度为4的有序区间。依次这样进行下去，4和8，8和16直到数组中所有的数合并到一个有序区间。整个过程结束。
class Solution { public: vector<int> sortArray(vector<int>& nums) { vector<int> tmp(nums.size(),0); merge_sort(nums, tmp, 0, nums.size()-1); return nums; } void merge_sort(vector<int>& nums, vector<int>& tmp, int left, int right){ if(left>=right) return; int mid = left + (right-left)/2; // 找到中间位置就开始一直拆分 merge_sort(nums, tmp, left, mid); merge_sort(nums, tmp, mid+1, right); merge(nums, tmp, left, right); // 拆分到最后将其合并 } void merge(vector<int>& nums, vector<int>& tmp, int left, int right){ int i=left, mid=left+(right-left)/2, j=mid+1, pos=left; while(i<=mid && j<=right){ // 在没有越界的情况下哪个元素小，哪个元素就放入tmp中 if(nums[i]<nums[j]) tmp[pos++]=nums[i++]; else tmp[pos++]=nums[j++]; } while(i<=mid) tmp[pos++]=nums[i++]; // 左半边剩余没有排完的元素依次放进去 while(j<=right) tmp[pos++]=nums[j++]; // 右半边剩余没有排完的元素依次放进去 for(int i=left;i<=right;++i){ // tmp中的元素放回到nums[i]中 nums[i]=tmp[i]; } } };
快速排序
快速排序是随机地从数组中选择一个数，如果一个数小于等于这个被选中的数，统一放在这个数的左边，如果一个数大于这个被选中的数就放在右边。接下来对左右两边分别递归地调用快速排序的过程即可。这样就使得整个数组都有序了。
class Solution { public: vector<int> sortArray(vector<int>& nums) { quick_sort(nums, 0, nums.size()-1); return nums; } void quick_sort(vector<int>& nums, int left, int right){ if(left>=right) return; // 左边的数字大于或等于右边的数字的时候，我们直接返回 int i=left, j=right; while(i<j){ while(i<j && nums[j] >= nums[left]) --j; while(i<j && nums[i] <= nums[left]) ++i; swap(nums[i], nums[j]); } // left与中间元素交换位置，这一步之后才是真正的小的在左边，大的在右边 swap(nums[left], nums[i]); quick_sort(nums, left, i-1); quick_sort(nums, i+1, right); } };
堆排序
希尔排序
希尔排序实际上是插入排序的一个改良算法。在插入排序中，一个数想插入到前面的有序的序列中的话，每次是和前面的一个数进行比较。希尔排序的步长是逐渐调整的，准确来说是从大到小逐渐调整的。
假设初始数组为【6，5，3，1，8，7，2，4】。
- 当初始步长为
3的情况下，【6，5，3】作为前3个数，是不需要调整的。从1开始，向前跳3位，来与6进行比较，发现1比6小，于是1与6进行交换，此时数组变为：【1，5，3，6，8，7，2，4】。 - 之后再处理下一个数据
8，8向前跳3位，与5进行比较。与5比较发现比5要大，所以直接停止交换过程，进行下一个数的调整。 - 之后再处理下一个数，来到7这个数，7向前跳3位，发现7又是大于3的。所以7这一步也不需要进行交换。
- 接下来又来到2这个位置，
2向前跳3位，与6进行比较，2比6小，所以2和6之间进行交换。此时数组变为：【1，5，3，2，8，7，6，4】，2再向前跳3位，此时发现2应该与1进行比较，它比1要大，所以2停在原位置。整个交换过程停止。 - 接下来处理4这个数，4向前跳3位，来到8这个数，4与8比，4比8小，所以4与8互换位置，此时数组变为：
【1，5，3，2，4，7，6，8】。接下来4再向前跳3个位置，发现其小于5，所以4和5之间进行交换，此时数组变为：【1，4，3，2，5，7，6，8】，此时4来到了位置1，再向前跳3位的话就越接了。此时整个步长为3的插入排序就结束了。
接下来还有步长为2，步长为1的插入排序过程。希尔排序完全取决于步长的选择，步长越优，时间复杂度就会越低。步长选择越劣的话，时间复杂度就越趋近于O ( N 2 ) 级别。
class Solution { public: vector<int> sortArray(vector<int>& nums) { for(int gap=nums.size()/2; gap>0; gap/=2){ for(int i=gap; i<nums.size(); ++i){ for(int j=i; j>gap-1; j-=gap){ // 每次跳跃gap间隔 if(nums[j]<nums[j-gap]) swap(nums[j], nums[j-gap]); } } } return nums; } };
时间复杂度为O ( N )
以下是时间复杂度为O ( N ) 的排序算法。这里的排序算法不是基于比较的排序算法，它思想的原型都来自于桶排序。桶排序不是具体的实现，它只是一种思想。比较常规的有计数排序和基数排序。
计数排序
比如现在需要把员工按照身高来进行排序。我们知道一个成年人的身高基本是在1米到3米之间。对应的厘米数就是100到300。所以依据厘米数依次建立从100到300号桶。然后把所有的员工按照他们对应的各自的身高，把它放到相对应的桶里面。当所有员工都进入桶之后，从100号桶开始，依次倒出员工。此时员工被倒出的顺序就是按照身高排序的顺序。
基数排序
假设我们要排序的数都是十进制的，然后我们准备从0-9这样十个桶。然后将每位数依据个位上的数值选择进入几号桶。当所有的数都进入桶之后，我们再从0号桶到9号桶依次倒出所有的数，组成了一个序列。
接下来依据这个序列的顺序，按照十位上的数值选择进入0号桶到9号桶中的一个。当所有的数再次进入桶中之后，我再把从0号桶到9号桶中的数据依次倒出。再组成一个新的序列，下一轮依据这样一个序列的顺序依次考察每一个数它百位上的数值进入0号桶到9号桶中的一个。
依次这样迭代下去，最后是依据最高位的数值选择进入0号桶还是9号桶。最后一次倒出的序列就是整个数排序的序列了。
经典排序算法的空间复杂度
- 时间复杂度为O ( n 2 ) 的插入排序、选择排序、冒泡排序的空间复杂度都是O ( 1 ) )的。
- O ( N ∗ l o g N ) 的排序算法中，堆排序、希尔排序的空间复杂度都是O ( 1 ) 。
- 快速排序的空间复杂度为O ( l o g N ) ∼ O ( N ) ，这完全取决于它划分的情况。
- 归并排序它的空间复杂度为O ( N ) 。虽然很多书上写过他的空间复杂度可以优化到O ( 1 ) ，通过手调算法。但是手调算法时间复杂度就会上升。
- 对于时间复杂度为O ( N ) 的不基于比较的排序算法来说，他的空间复杂度是O ( M ) ，这个M 是选择桶的数量。
经典排序算法的稳定性
稳定性的概念说的是，假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否者称为不稳定的。
稳定的排序算法：
冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序。
不稳定的排序算法：
选择排序、快速排序、希尔排序、堆排序
