所有排序都是从小到大进行排序

1插入排序

　　插入排序的思想主要是,将[a1,a2,a3,a4….ai…….an]前ai-1个序列看成有序的,然后用第ai个数与前面的数进行比较,找到位置进行插入

  1.     int i,j,temp;//a[len]
  2.     for(i=1;i<len;i++){//假设a[0]一个数为有序数列,从a[1]开始,依次进行比较
  3.         if(a[i]<a[i-1]){//满足条件
  4.             temp = a[i];//暂时存放a[i]
  5.             a[i] = a[i-1];
  6.         for(j=i-2;temp<a[j];j--)//继续与前面的数进行比较
  7.             a[j+1] = a[j];
  8.         a[j+1] = temp; //将a[i]这个数放到对应的位置上
  9.          }
  10.     }

2.折半插入排序

　　在插入排序的基础上,将序列分为两部分(低半区,高半区)

  1.     int i,j,temp;
  2.     for(i=1;i<len;i++){
  3.         temp = a[i];
  4.         int low=0,high=i-1;
  5.         while(low<=high){
  6.             int m = (low+high)/2;
  7.             if(temp<a[m])
  8.                 high = m - 1;//插入点在低半区
  9.             else
  10.                 low = m + 1;//插入点在高半区 
  11.         }
  12.         for(j=i-1;j>=high+1;j--)//从插入点到i这个位置,进行位置交换
  13.         //1 2 4 5 i=3排列后high=2;4 5要一次后移为3腾出位置 
  14.             a[j+1] = a[j];
  15.         a[high+1] = temp; //当low>high是,插入点就在high+1位置 
  16.     }

3.希尔排序

　　希尔排序又称缩小增量排序,它也属于插入排序

　　基本思想是:将整个代排记录分割成若干个子序列分别进行直接插入排序,待整个序列中的记录”基本有序”时,再对全体记录进行一次直接插入排序

　　最后一个增量一定是1

  1. //希尔排序 
  2. void shellInsert(int dk){
  3.     int i,j;
  4.     for(i=dk;i<len;i++){
  5.         if(a[i]<a[i-dk]){
  6.             int temp = a[i];
  7.             for(j=i-dk;j>=0&&temp<a[j];j-=dk){//当前小组内进行移动 
  8.                 a[j+dk] = a[j];
  9.             }
  10.             a[j+dk] = temp;
  11.         }
  12.     }
  13. } 
  14. void sort3(){
  15.     int dlta[] = {5,3,1};//增量序列 
  16.     for(int k=0;k<3;k++)
  17.         shellInsert(dlta[k]);
  18. }

4.快速排序

　　快速排序是冒泡排序的升级,将任务一分为二,

　　基本思想是:通过一趟排序,将待排记录分割成独立的两部分,(低半区,高半区),然后再分别对分隔出的两部分进行排序

　　通过基本思想,我们可以用递归来写

  1. //快速排序 
  2. int Partition(int a[],int low,int high){
  3.     int pivokey;
  4.     //a[n] = a[low];//用a[n+1]存放枢轴 
  5.     pivokey = a[low];
  6.     while(low<high){
  7.         while(low<high&&pivokey<=a[high])
  8.             high--;
  9.         a[low] = a[high];//将比中间值小的数移到低端 
  10.         
  11.         while(low<high&&pivokey>=a[low])
  12.              low++;
  13.         a[high] = a[low];//将比中间值大的数移到高端 
  14.     }
  15.     a[low] = pivokey;
  16.     return low;//返回枢纽位置 
  17. }
  18. void sort4(int low,int high){
  19.     //int low=0,high=len-1;
  20.     if(low<high){
  21.         int pivotloc = Partition(a,low,high);
  22.         sort4(low,pivotloc-1);
  23.         sort4(pivotloc+1,high);
  24.     }
  25.      
  26. }

5.简单选择排序

  1. //选择排序
  2. void sort5(){
  3.     int i,j;
  4.     for(i=0;i<len;i++){
  5.         int min = i;
  6.         for(j=i+1;j<len;j++){
  7.             if(a[min]>a[j])
  8.                 min=j;
  9.         }
  10.         if(min!=i){
  11.             int temp = a[min];
  12.             a[min] = a[i];
  13.             a[i] = temp;
  14.         }
  15.     }
  16. }

……

版权声明：本文为Tisou1原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Tisou1/p/12837733.html