基本概念
内部和外部排序
内部排序在这里指的是只用到了电脑内存而不使用外存的排序方式。相对的，外部排序就是同时动用了电脑内存和外存的排序方式。本文在这里只讨论内部排序。
分类
比较和非比较排序
比较在这里指的是需要比较两个元素的大小(前后)才能进行的排序。难道有排序算法不需要比较吗？的确有，但是不多。常见的有三种：计数排序，桶排序，基数排序。它们用统计的方法规避了比较，详细的可查看之后讲到的这些算法。
转换
每次只调换两个元素之间的位置。
插入
遍历到的元素放入之前维护的已完成排序的序列中。
选择
选择剩余元素中最大或最小的元素。
知道了以上概念后，就能更好的看懂分类了（建议先略看，看完所有排序算法后再回看）
稳定度 (Stability)
定义：如果排序算法并不改变两个相同值的元素的相对位置，则此算法稳定度高。
这张图十分形象地解释了以上定义：
冒泡排序 (Bubble Sort)
1 算法
从第一个元素开始遍历，比较当前元素跟下一个元素的大小，如果不符合排序，交换位置。结束最后一个元素后，再从头开始不断遍历，直到完成排序。
剖析：每遍历完一次，最小数前进一位，但是最大数到达最终位；末尾已经是最终排序。
2 代码
基本
void bubble(vector<int>& arr){
for(int i=0;i<arr.size()-1;i++){ //only need n-1 swaps to move the smallest to the front
for(int j=0;j<arr.size()-1;j++){
if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]);
//arr[j]>arr[j+1] stable
//arr[j]>=arr[j+1] unstable
}
}
}
优化1: 每遍历完一遍，看是否已经提前完成排序(用 hasSorted)。如是，提早结束。
void bubble1(vector<int>& arr){
bool hasSorted = false;
for(int i=0;i<arr.size()-1&&!hasSorted;i++){
hasSorted=true;
for(int j=0;j<arr.size()-1;j++){
if(arr[j]>arr[j+1]){
hasSorted = false;
swap(arr[j],arr[j+1]);
}
}
}
}
优化2: 根据“剖析：每遍历完一次，最小数前进一位，但是最大数到达最终位；末尾已经是最终排序。”，每遍历完一次，里面的loop就可以少遍历一个元素。但其实由此我们可以推论，最后一个swap的j和j+1, j之后的元素(不包括j)都已经完成排序了。
void bubble2(vector<int>& arr){
int n = arr.size()-1;
for(int i=0;i<arr.size()-1;i++){
int upto = 0;
for(int j=0;j<n;j++){ //j小于不定排序的最后一位
if(arr[j]>arr[j+1]){
upto = j; //upto=j不定大小的最后一位, j+1 已经完成排序（最后一个if）
swap(arr[j],arr[j+1]);
}
}
n=upto;
if(n==0) break;
}
}
优化3: 可以进行双向的循环，正向循环把最大元素移动到末尾，逆向循环把最小元素移动到最前，这种优化过的冒泡排序，被称为鸡尾酒排序(Cocktail Sort)
void bubble4(vector<int>& arr){
int beg = 0;
int end = arr.size()-1;
while(beg<end){
int nbeg = beg, nend = end;
//正向循环
for(int i=beg;i<end;i++){
if(arr[i]>arr[i+1]){
nend=i;
swap(arr[i],arr[i+1]);
}
}
if(nend==end) break;
end = nend;
//逆向循环
for(int i=end; i>beg;i--){
if(arr[i]<arr[i-1]){
nbeg=i;
swap(arr[i], arr[i-1]);
}
}
if(nbeg==beg) break;
beg = nbeg;
}
}
3 分析
3.1 稳定度
决定于比较的时候用的是大于等于(小于等于)还是大于(小于)
arr[i]>arr[i+1] --> 稳定
arr[i]>=arr[i+1] --> 不稳定
3.2 时间
逆向排序时是最差的情况，O(n^2)
3.3 空间
需要O(1)来完成swap等
快速排序 (Quicksort)
1 算法
利用了 divide & conquer 的思想。
在序列中任意选择一个数，然后把序列分成比这个数大的和比这个数小的两个子序列。不断重复以上步骤完成排序。
2 代码
int partition1(vector<int>& arr, int beg, int end){
int pivot = arr[beg];
int l=beg+1, r=end;
while(l<=r){
if(arr[l]<pivot) l++;
else if(arr[r]>pivot) r--;
else if(arr[l]>=pivot && arr[r]<=pivot){
swap(arr[l++], arr[r--]);
}
}
swap(arr[r], arr[beg]);
return r;
}
int partition2(vector<int>& arr, int beg, int end){
int pivot = arr[beg];
int index = beg+1;
for(int i=index;i<=end;i++){
if(arr[i]<pivot){
swap(arr[i], arr[index++]);
}
}
swap(arr[beg],arr[index-1]);
return index-1;
}
void quick(vector<int>& arr, int beg, int end){
if(beg<end){
int pivot = partition1(arr,beg,end);
// int pivot = partition2(arr,beg,end);
quick(arr, beg, pivot-1);
quick(arr, pivot+1, end);
}
}
优化1 切换到插入排序
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
优化2 三数取中
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。人们发现取 3 个元素并将大小居中的元素作为切分元素的效果最好。
优化3 三向切分
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
等之后review的时候再贴code吧～ 写这个太烧脑了～
3 分析
3.1 稳定度
3.2 时间
最好的情况是pivot都是中点 -- O(n log n) (平均情况也是如此，所以有些快排算法会在一开始随意打乱数列)
最差的情况是本来就是有序数列 -- O(n^2)
3.3 空间
尽管没有用另外的数据结构，但是不是O(1)哦～ 因为recursion需要在stack frames里面重新建array。我上面的code需要O(n) extra space, 最优的话，可以达到O(log n)
4 变形
LeetCode - Top K Frequent Elements
插入排序 (Insertion Sort)
1 算法
维护一段有序数列，同时遍历待排序的数列，在有序数列里找到合适的位置，插入元素。
2 代码
void insertion(vector<int>& arr){
for(int i=1;i<arr.size();i++){
int temp=i;
for(int j=i-1;j>=0;j--){
if(arr[temp]<arr[j]) swap(arr[temp--],arr[j]);
}
}
}
优化1 找到当前元素该插入的位置后，再插入
void insertion1(vector<int>& arr){
for(int i=1;i<arr.size();i++){
int temp=arr[i];
int j=i-1;
for(;j>=0 && temp<arr[j];j--){
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
3 分析
3.1 稳定度
arr[temp]<arr[j], 只有小于的时候swap，等于的时候保持先前的相对位置，所以是稳定的。
3.2 时间
最优情况是正向排序 -- O(n)
最差是逆向排序，每次插入都需要比较已完成数列元素的个数 -- O(n^2)
3.3 空间
O(1) - 如上code -> temp
原文链接：https://blog.csdn.net/real_lisa/article/details/82685407
