排序算法
以下内容整理自互联网，仅用于个人学习
转载自http://huachao1001.github.io/article.html?qt0GFFFO
1. 插入排序
每次将一个待排序记录按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。
插入排序分为三种：
- 直接插入排序
- 折半插入排序
- 希尔排序
1.1 直接插入排序
思想：
- 查找L(i)在L[1···i-1]中插入位置k
- 将L[k···i-1]中所有元素全部后移一个位置
- 将L(i)复制到L(k)
void InsertSort(ElemType A[] int n){
int i,j;
//依次将A[2]~A[n]插入到前面已经排好序的序列
for(i=2;i<=n;i++){
A[0]=A[i]; //复制为哨兵，A[0]存放的是哨兵
for(j=i-1;A[0].key<A[j].key;--j){ //从后往前，查找待插入的位置
A[j+1]=A[j];
}
A[j+1]=A[0];
}
}
复杂度：
- 空间复杂度：仅用了常数个辅助单元，因此空间复杂度为：O(1)。
- 时间复杂度：在最坏的情况下，每次比较的次数是i次（i=2,3...），每次移动次数为i+1次（i2,3...） O(f(n))=O(n2)。
- 稳定性：每次插入都是从后往前比较再移动，所以不会出现相同的元素相对位置发生变化的情况，即插入是稳定的。
1.2 折半插入排序
相比直接插入排序，折半插入排序主要是在直接插入排序中的查找插入位置进行优化。
思想：
将直接插入排序中的查找过程，替换为折半查找算法。
void InsertSort(ElemType A[] ,int n){
int i,j,low,high,mid;
for(int i=2;i<=n;i++){
A[0]=A[i];
low=1;
high=i-1;
//折半查询，找出第i个元素应该插入的位置
while(low<=heigh){
mid=(low+high)/2;
if(A[mid].key>A[0].key)
high=mid-1;
else
low=mid+1;
}
//high位置右边的元素至i-1都是比第i个元素大
for(j=i-1;j>=high+1;--j){
A[j+1]=A[j];
}
A[high+1]=A[0];
}
}
时间复杂度：
不难看出，在折半查询过程中，复杂度为 O(nlog2n) 而移动次数方面，跟直接插入排序一样都是 O(n2) 因此，时间复杂度还是跟直接插入排序一样，但是在数据量比较小的时候，折半插入排序的性能会比较好。
1.3 希尔排序
思想：
将待排序表分成若干个形如L[i,i+d,i+2d,···，i+kd]的特殊子表，分别进行直接插入排序，当整个表中元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
void ShellSort(ElemType A[] , int n){
//对顺序表做希尔插入排序，相比直接插入排序，做了以下修改：
//1.前后记录位置的整理是dk，而不是1
//2.r[0]只是暂存单元，不是哨兵，当j<0时，插入位置已到
for(dk=len/2;dk>=1;dk=dk/2){ //步长变化
for(i=dk+1;i<=n;++i){//前面dk个元（第0个元素作为缓存）素是dk个分组的第1个元素
if(A[i].key<A[i-dk].key){//如果比本组的前面一个元素小
//本组元素往后移动
A[0]=A[i];
for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk){
A[j+dk]=A[j];
}
A[j+dk]=A[0];
}//if
}
}
}
复杂度：
- 空间复杂度：O(1)。
- 时间复杂度:由于希尔排序时间复杂度依赖于增量序列的函数，这涉及属性上尚未解决的难题，所以其时间复杂度分析比较困难。当n在特定范围时，希尔排序时间复杂约为O(n1.3) 在最坏的情况下时间复杂度为：O(n2)。
- 稳定性：不稳定。因为两个相同的元素，如：3 2 2 ，第二个2会跟3交换，导致第一个2排在第二个2后面。
2. 交换排序
2.1 冒泡排序
思想：
从前往后比较元素的值。每一趟排序把未排序中最大的元素放到最终位置。
for(int i > 0;i < len-1;i++){
for(int j = 0;j < len-i-1;j++){
if(array[i] > array[j+1]){
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
复杂度：
- 空间复杂度：O(1)
- 时间复杂度：第i趟比较n-i次，每次比较需要移动3次来交换元素位置，一共是f(n)=∑i=1 n-1 4(n-i)=4n(n-1)/2所以， O(f(n))=n^2
- 稳定性：如果两个元素相等，是不会交换两个元素，因此，是稳定的。
2.2 快速排序
思想：
快速排序是对冒泡排序的改进。其基本思想是基于分治法：在待排序表L[1···n]中任意选取一个元素pivot作为基准，通过一趟排序将待排序表划分为独立的两部分L[1···k-1]和L[k+1···n],使得L[1···k-1]中的所有元素比pivot小，L[k+1···n]中所有元素大于或等于pivot，即pivot最终放在了其最终的位置L(k)上。
void QuickSort(ElemType A[],int low,int high){
if(low<high){
int pivotPos=Partition(A,low,high);//划分
QuickSort(A,low,pivotPos-1);
QuickSort(A,pivotPos+1,high);
}
}
int Partition(ElemType A[],int low,int high){
ElemType pivot=A[low];
while(low<high){
//从后向前跳过大于基准的数
while(low<high&&A[high]>=pivot) --high;
A[low]=A[high];
//从前往后跳过小于基准的数
while(low<high&&A[low]<=pivot) ++low;
A[high]=A[low];
}
A[low]=pivot;
return low;
}
复杂度：
- 空间复杂度：由于快排是递归的，需要借助递归栈来保存每一层递归调用的必要信息。最好的情况下为：⌈log2(n+1)⌉ 最坏的情况为O(n),平均为log2n
- 时间复杂度：快排的运行时间与划分是否对称有关，最坏的时间复杂度为O(n2) 最好的时间复杂度为：nlog2n。快排的凭据时间与最佳情况下的运行时间很接近，而不是接近最坏的时间复杂度。因此快速排序是所有内部排序算法中平均性能最优的排序算法。
- 稳定性：不稳定。如3 2 2 ，经过一趟排序后，中间的2不变，顺序变为2 2 3，此时排序结束，第一个2和第二个2位置发生变化。
3. 选择排序
思想：每一趟（第i趟）在后面n-i+1(i=1,2，···，n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第i-1趟做完，待排序的元素只剩下1个就不用再选了。
3.1 简单选择排序
思想：
假设排序表为L[1···n]，第i趟排序即从L[i···n]中选择关键字最小的元素与L(i)交换，每一趟可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。
void SelectSort(ElemType A[],int n){
//对表A做简单选择排序，A[]从0开始存放元素
int min;
for(int i=0;i<n-1;i++){
min=i;
for(j=i+1;j<n;j++){
if(A[j]<A[min]){
min=j;
}
}
if(min!=i) swap(A[i],A[min]);
}
}
复杂度：
- 空间复杂度：O(1)
- 时间复杂度：元素之间的比较次数与初始状态无关，始终是n(n-1)/2,所以时间复杂度是O(n^2)
- 稳定性：不稳定。如2 2 1，经过一趟排序后，变成1 2 2 ，两个2相对位置发生了变化。
