排序总结
本文主要介绍了直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和并归排序八种排序方法。并使用C++分别实现了这8中排序算法，测试没有错误。
全部代码的文件我放在github上了：https://github.com/shinepengwei/Gallery/blob/master/sortAlgm.cpp
1插入排序
插入排序是从未排序序列中找到一个元素，然后插入到已排序的序列中的合适位置。插入排序分为3步：
- 定位：确定待排序元素放入已排序序列中的合适位置。
- 移位：将已排序序列中从插入位置到最后的元素依次向后移动一个位置，从而腾出位置。
- 插入：将这个元素插入到这个位置。
直接插入排序
在直接插入排序中，定位是将这个元素按顺序与已排序序列进行比较从而找到合适位置。
[cpp]
//直接插入排序，其中list[0]作为哨兵，并不参与排序，排序后的序列为list[1~n-1]
// int n=10,list[11]={-1,4,1,3,2,16,9,10,14,8,7}, InsertSort(list,11);
void InsertSort(int *list,int n){
for(int i=2;ilist[0]){
list[j+1]=list[j];
j--;
}
list[j+1]=list[0];
}
}
[/cpp]
其平均时间复杂度为O(n^2)
折半插入排序
在定位的时候，因为已排序序列具有有序的特性，因此可以使用折半查找的方法更快的找到需要插入的位置。
[cpp]
//折半插入int n=10,list[11]={-1,4,1,3,2,16,9,10,14,8,7}，BInsertSort(list,11);
void BInsertSort(int *list,int n){
int low,high,mid;
for(int i=2;i=low){
mid=(high+low)/2;
if(list[mid]>list[0]) high=mid-1;
else low=mid+1;
}
for(int j=i-1;j>high;j--) list[j+1]=list[j];
list[high+1]=list[0];
}
}
[/cpp]
希尔排序
思想：选择一个增量，然后将间隔为增量的元素作为一组进行排序（直接插入），增量不断减小至1，则全部元素排序结束。
[cpp]
//shell排序
//int int list[11]={-1,4,1,3,2,16,9,10,14,8,7}; ShellSort(list,10);
void ShellPass(int *list, int n, int d){
for(int i=1+d;i<=n;i++){
if(list[i]0&&list[j]>list[0]);
list[j+d]=list[0];
}
}
}
void ShellSort(int *list,int n){
cout<<"before:"<<endl;
printlist(list,11);
int increment=n;//增量初值
do{
increment=increment/3+1;
ShellPass(list,n,increment);
cout<<increment<<":"<1);
}
[/cpp]
直接插入排序的平均时间复杂度为O(n^2)，随着n的增加复杂度迅速增加。同时，若排序记录为正序，时间复杂度可减小到O(N)因此，希尔排序希望基于以上思路，先对小部分元素进行排序，使其基本有序，然后不断对扩大元素集合，从而获得最终的排序。
时间复杂度不容易分析，当n较大是，比较和移动次数大概在n^1.25~1.6n^1.25之间。
2交换排序
交换排序是在排序过程中不断的交换元素的位置。其中，冒泡排序相对来说是最简单的、最容易实现的排序算法，但是效率较差，比直接插入排序还差。快速排序恰恰相反，从名字可以看出，他是最快的排序算法，算法相对复杂。
冒泡排序
冒泡排序的意思就是不断的将两个相邻元素比较，让更大的元素上移，每一趟就能找到最大的一个元素放在最后面。
[cpp]
//冒泡排序int list[10]={4,1,3,2,16,9,10,14,8,7}; BubbleSort(list,10);
void BubbleSort(int *list,int n){
for(int i=1;i<n;i++){
bool exchange=false;
for(int j=0;jlist[j+1]){
int tmp=list[j];
list[j]=list[j+1];
list[j+1]=tmp;
exchange=true;
}
}
if(!exchange){
return;
}
}
}
[/cpp]
快速排序
快速排序使用分治发的思想，每次在待排序队列中选择一个元素作为基准（pivot，为了方便通常选择第一个元素），然后将待排序序列分为两个自序列，小于基准元素的自序列和大于基准元素的子序列，然后再对自序列进行排序。
快速排序更适合于无序的序列，若是待排序序列基本有序，快速排序则变为冒泡排序，其复杂度为O(n^2)。因为对无序的元素进行块排时，其pivot元素一般可以选为序列的中间值，对于有序的序列，pivot元素无法平均分割子区间，造成效率下降。
[cpp]
//快速排序
int Partition(int *list,int low,int high){
int pivot=list[low];
while(lowpivot&&lowlow){
//交换high和low的元素
//swap(list,high,low);
//将pivot存储在变量中，应该存放PIVOT的元素一直为NULL
list[low]=list[high];
low++;
}
while(list[low]<pivot&&lowlow){
// swap(list,high,low);
list[high]=list[low];
high--;
}
}
//最后high=low
list[low]=pivot;//最后将这个一直为NULL的元素放入pivot
return low;
}
//int list[11]={4,1,3,2,16,9,10,14,8,7};QuickSort(list,0,9);
void QuickSort(int *list,int low,int high){
int pivotpos;
if(low<high){
pivotpos=Partition(list,low,high);
//printlist(list,10);
QuickSort(list,low,pivotpos-1);
QuickSort(list,pivotpos+1,high);
}
}
[/cpp]
快排当每次选到中间值作为pivot，最好的时间复杂度为O(nlogn)，每次选到最大或最小元素，则造成最坏的时间复杂度O(n^2)。
空间复杂度：每次均匀分割，空间复杂度为S(n)=O(logn)。最坏情况则为O(n)。
快排是一个不稳定的排序方法。
3选择排序
选择排序的基本思想是将序列分为已排序序列和待排序序列，每次从待排序序列中选取最小的作为已排序序列中最大的放在最右边。
简单选择排序
就是简单的从待排序序列中找到最小的，然后和待排序序列中的第一个元素交换，使其成为已排序序列中的最后一个。
[cpp]
// int list[10]={4,1,3,2,16,9,10,14,8,7}; SelectSort(list,10);
void SelectSort(int *list,int n){
for(int i=0;i<n;i++){
int min=i;
for(int j=i+1;j<n;j++){
if(list[j]<list[min]){
min=j;
}
}
if(i!=min)
swap(list,i,min);
}
}
[/cpp]
堆排序
堆排序属于选择排序，但是选择元素的方法与简单选择排序完全不同。下面介绍的方法是选择一个最大的元素，放到序列的最右边。选择方法是将待排序序列以最大堆的数据结构存储，因此每次选择根节点就是最大的未排序元素。然后对破坏后的最大堆进行调整，使其重新成为最大堆。
可分为以下步骤：
- 建立最大堆。
- 找出最大元素（最大堆根元素）。
- 修复最大堆。
[cpp]
//Heap Sort
//从数组索引为1的地方开始排序，为了计算方便
int left(int i){
return 2*i;
}
int right(int i){
return 2*i+1;
}
int parent(int i){
return i/2;
}
void maxHeapify(int *list,int i,int size){
int l=left(i);
int r=right(i);
int largest=i;
if(llist[i]){
largest=l;
}
if(rlist[largest]){
largest=r;
}
if(i!=largest){
swap(list,i,largest);
maxHeapify(list,largest,size);
}
}
void BuidHeap(int *list,int size){
for(int i=size/2;i>=1;i--){
maxHeapify(list,i,size);
}
}
//size=list.length()-1, don't consider the first element of list,list[0]
//int list[11]={-1,4,1,3,2,16,9,10,14,8,7};HeapSort(list,10);
void HeapSort(int *list,int size){
BuidHeap(list,size);
while(size>0){
swap(list,1,size);
maxHeapify(list,1,size);
size--;
}
}
[/cpp]
4归并排序
归并表示将两个或者两个以上的有序序列合并成一个有序序列。方法是通过三个游标I,j,k，其中i和j分别指向待排序的起始位置，k指向排序后放入序列的位置。比较i和j指向元素的大小，将小的放入k指向的位置，然后将k和指向小元素的i或j都加1，重复以上过程直至全部记录复制到有序序列表。
[cpp]
//并归排序
void Merge(int *list,int *tmp,int begin,int mid,int end){
int i=begin,j=mid+1,k=begin;
while(i<=mid&&jlist[j]){
tmp[k]=list[j];
j++;
}else{
tmp[k]=list[i];
i++;
}
k++;
}
while(i<=mid){
tmp[k]=list[i];
k++;
i++;
}
while(j<=end){
tmp[k]=list[j];
k++;
j++;
}
for(i=begin;i<=end;i++){
list[i]=tmp[i];
}
}
void MSort(int *list,int begin,int end,int *tmp){
if(begin<end){
int mid=(begin+end)/2;
MSort(list,begin,mid,tmp);
MSort(list,mid+1,end,tmp);
Merge(list,tmp,begin,mid,end);
}
}
//int list[11]={-1,4,1,3,2,16,9,10,14,8,7};MergeSort(list,10);
void MergeSort(int *list,int n){
int *p=new int[n+1];
for(int i=0;i<n+1;i++)
p[i]=-1;
MSort(list,1,n,p);
delete []p;
}
[/cpp]
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
书中说：因为并归排序使用的是递归算法，实用性差，较少使用。但是快速排序也是递归算法。这里有点不理解。
5各种排序方法的比较
按平均时间可以将分类分为以下四类：
- 平方阶排序（O(n^2)）：一般称为简单排序，如直接插入，直接选择和冒泡
- 线性对数阶（O(nlgn)）：如快速、并归和堆排序。
- O(n^1+x):x节欲0~1之间，如希尔排序
- 线性排序（O(n)）：桶、箱和基数排序。
不同的排序方法适用于不同的应用背景，选择合适的排序方法需要考虑以下因素：
- 待排序记录数n
- 记录的大小和规模
- 稳定性要求
- 存储结构
- 时空复杂度等
不同条件下选择排序的方法：
- 若n较小，一般可以选择直接插入或者直接选择。若记录规模较小，直接插入排序较好。但是如果记录规模较大，记录的移动成本较大，应选择直接选择排序，因为直接选择排序移动的记录数少于直接插入。
- 若文件初始状态基本有序，可以选择直接插入排序、冒泡排序或者随机的快速排序。
-
若n较大，应采用时间复杂度为线性对数阶的排序方法，如快速、堆或并归排序。
- 快速排序被认为目前最好的排序方法，当待排序的关键字随机分布时，他的平均时间最短。
- 堆排序辅助空间少于快速排序，而且不会出现快速排序可能出现的最坏情况。
- 若要求排序稳定，可选用并归排序。