希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
1. #include <iostream> 2. using namespace std; 3. int arr[]={9,1,2,5,7,4,8,6,3,5}; 4. int length=10; 5. void swap(int &a,int &b){a+=b;b=a-b;a-=b;} 6. void prin_() 7. { 8. for(int i=0;i<length;i++) cout<<arr[i]<<" "; 9. cout<<endl; 10. } 11. int main() 12. { 13. prin_(); 14. for(int gap=length/2;gap>0;gap/=2){ 15. for(int i=gap;i<length;i++){ 16. int j=i; 17. while(j-gap>=0 && arr[j]<arr[j-gap]){ 18. swap(arr[j],arr[j-gap]); 19. j-=gap; 20. } 21. } 22. prin_(); 23. } 24. return 0; 25. }
五.快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。
一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。
快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法
由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。
1. //快速排序<1> ：10 20 40 32 67 40 20 89 300 400 15 2. #include<iostream> 3. using namespace std; 4. void qsort(int,int); 5. int a[101]; 6. int main() 7. { 8. int n,i; 9. cin>>n; 10. for(i=1;i<=n;i++) cin>>a[i]; 11. qsort(1,n); 12. for(i=1;i<=n;i++) cout<<a[i]<<" "; 13. cout<<endl; 14. return 0; 15. } 16. void qsort(int l,int r){ 17. int i,j,mid,p; 18. i=l;j=r; 19. mid=a[(l+r)/2]; 20. do{ 21. while(a[i]<mid) i++; 22. while(a[j]>mid) j--; 23. if(i<=j){ 24. p=a[i];a[i]=a[j];a[j]=p; 25. i++;j--; 26. } 27. }while(i<=j); 28. if(l<j) qsort(l,j); 29. if(i<r) qsort(i,r); 30. }
1. //快速排序<1> ：10 20 40 32 67 40 20 89 300 400 15 2. #include <stdio.h> 3. #include<iostream> 4. using namespace std; 5. int a[101]; 6. void sort(int *a,int left,int right){ 7. if(left>=right) return; 8. int i,j,key; 9. i=left;j=right;key=a[left]; 10. while(i<j){ 11. while(i<j && key<=a[j]) j--; 12. a[i]=a[j]; 13. while(i<j && key>=a[i]) i++; 14. a[j]=a[i]; 15. } 16. a[i]=key; 17. sort(a,left,i-1); 18. sort(a,i+1,right); 19. } 20. int main() 21. { 22. int a[]={57,68,59,52,72,28,96,33,24}; 23. sort(a,0,sizeof(a)/sizeof(a[0])-1);/*这里第三个参数要减1否则内存越界*/ 24. for(int i=0;i<sizeof(a)/sizeof(a[0]);i++){ 25. cout<<a[i]<<""; 26. } 27. return 0; 28. }
六.归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
例如有8个数据需要排序：10 4 6 3 8 2 5 7
归并排序主要分两大步：分解、合并。
合并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
1. #include <stdio.h> 2. #include<iostream> 3. using namespace std; 4. int a[]={57,68,59,52,72,28,96,33,24}; 5. int r[101]; 6. void msort(int s,int t){ 7. if(s==t) return;//只有一个数字无需排序 8. int mid=(s+t)/2; 9. msort(s,mid);//分解左序列 10. msort(mid+1,t);//分解右序列 11. int i=s,j=mid+1,k=s; 12. while(i<=mid && j<=t){ 13. if(a[i]<=a[j]){ 14. r[k]=a[i];k++;i++; 15. } 16. else{ 17. r[k]=a[j];k++;j++; 18. } 19. } 20. while(i<=mid){//复制左序列剩余 21. r[k]=a[i];k++;i++; 22. } 23. while(j<=t){//复制右序列剩余 24. r[k]=a[j];k++;j++; 25. } 26. for(int i=s;i<=t;i++) a[i]=r[i];//更新数组 a 27. } 28. int main() 29. { 30. msort(0,sizeof(a)/sizeof(a[0]-1));/*这里第三个参数要减1否则内存越界*/ 31. for(int i=0;i<sizeof(a)/sizeof(a[0]);i++) cout<<a[i]<<" "; 32. return 0; 33. }
1311：【例2.5】求逆序对
【题目描述】
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
【输入】
第一个数为n，表示序列长度，接下来的n个数，第n+1个数表示序列中的第n个数。
【输出】
所有逆序对总数。
【输入样例】
4 3 2 3 2
【输出样例】
3
【提示】
N≤10^5，Ai≤10^5。
【来源】
1. #include <iostream> 2. using namespace std; 3. long long a[100001]; 4. long long r[100001]; 5. long long ans=0; 6. void msort(long long s,long long t){ 7. if(s==t) return; 8. long long mid=(s+t)/2; 9. msort(s,mid); 10. msort(mid+1,t); 11. long long i=s,j=mid+1,k=s; 12. while(i<=mid && j<=t){ 13. if(a[i]<=a[j]){ 14. r[k]=a[i];k++;i++; 15. } 16. else{ 17. r[k]=a[j];k++;j++; 18. ans+=mid-i+1; 19. } 20. } 21. while(i<=mid) { 22. r[k]=a[i];k++;i++; 23. } 24. while(j<=t){ 25. r[k]=a[j];k++;j++; 26. } 27. for(i=s;i<=t;i++) a[i]=r[i]; 28. } 29. int main(int argc,char* argv[]) 30. { 31. long long n,i; 32. cin>>n; 33. for(i=0;i<n;i++) cin>>a[i]; 34. msort(0,n-1); 35. cout<<ans<<endl; 36. return 0; 37. }
其中ans+=mid-i+1这句代码统计新增逆序对的数量，ans作为全局变量，用于统计逆序对的数量，此时ans要增加左边区间剩余元素的个数。当归并排序结束后，逆序对问题也得到解决，ans即为逆序对的数量。
各种排序算法的比较
1.稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
选择排序、希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n^2)；
快速排序、堆排序、归并排序的时间复杂性为O(nlogn)；
桶排序的时间复杂性为O(n);
若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为O(n^2)，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。
由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。
3.辅助空间的比较
桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为O(logn)，最坏情况为O(n)，其它排序的辅助空间为O(1);
4.其它比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
