排序算法

稳定性：

注：相等元素不交换

稳定：冒泡、插入、归并、基数

不稳定：选择、快速、堆、希尔

实现：

希尔排序：

 1 void shellSort(int v[],int n)
 2 {
 3     int gap,i,j,tmp;
 4     for(gap=n/2;gap>0;gap/=2)
 5     {
 6         for(i=gap;i<n;i++)
 7         {
 8             for(j=i-gap;j>=0 && v[j]>v[j+gap];j-=gap)
 9             {
10                 tmp=v[j];
11                 v[j]=v[j+gap];
12                 v[j+gap]=tmp;
13             }
14         }
15     }
16  }

快速排序：

（这里提供四个实现，前两个实现以首元素为枢纽元，后两个实现可以指定枢纽元的位置，前两个实现可以看做是后两个实现的特例）

  1 void swap(int *a,int *b)
  2 {
  3     int tmp=*a;
  4     *a=*b;
  5     *b=tmp;
  6 }
  7 void quickSort1(int a[],int s,int e)//第一个元素作为枢纽元 
  8 {
  9     if(s>=e) return;
 10     int i=s+1;
 11     int j=e;
 12     while(1)
 13     {
 14         //若用do while循环，则  初始i=s;j=t+1;   do{i++;}while(!(a[i]>=a[s] || i==t));   do{j--;}while(!(a[j]<=a[s] || j==s));
 15         while(i<e && a[i]<a[s]) //或i<=e也可 
 16         {
 17             i++;
 18         }
 19         while(j>s && a[j]>a[s])//或j>=s也可 
 20         {
 21             j--;
 22         }
 23         
 24         if(i<j)
 25         {
 26             swap(&a[i],&a[j]);
 27         }
 28         else
 29         {
 30             break;
 31         }
 32     }
 33     swap(&a[s],&a[j]);
 34     quickSort1(a,s,j-1);
 35     quickSort1(a,j+1,e);
 36 }
 37 void quickSort2(int a[],int s,int e)//第一个元素作为枢纽元 
 38 {
 39     if(s>=e) return;
 40     int i=s;
 41     int j=s;
 42     while(++i <= e)
 43     {
 44         if(a[i]<a[s])
 45         {
 46             swap(&a[i],&a[++j]);
 47         }
 48     }
 49     swap(&a[s],&a[j]);
 50     quickSort2(a,s,j-1);
 51     quickSort2(a,j+1,e);
 52 }
 53 void quickSort3(int a[],int s,int e)//可以指定枢纽元 
 54 {
 55     if(s>=e) return;
 56     
 57     int pivot=(s+e)/2;//指定枢纽元
 58     
 59     int i=s;
 60     int j=e;
 61     while(1)
 62     {
 63         //若用do while循环，则  初始i=s-1;j=t+1;   do{i++;}while(!(a[i]>=a[pivot] || i==t));   do{j--;}while(!(a[j]<=a[pivot] || j==s));
 64         while(i<e && a[i]<a[pivot]) //或i<=e也可 
 65         {
 66             i++;
 67         }
 68         while(j>s && a[j]>a[pivot])//或j>=s也可 
 69         {
 70             j--;
 71         }
 72         
 73         if(i<j)
 74         {
 75             swap(&a[i],&a[j]);
 76             if(i==pivot) pivot=j;
 77             else if(j==pivot) pivot=i;
 78         }
 79         else
 80         {
 81             break;
 82         }
 83     }
 84     swap(&a[pivot],&a[i]);
 85     quickSort3(a,s,j-1);
 86     quickSort3(a,j+1,e);
 87 }
 88 
 89 void quickSort4(int a[],int s,int e)//可以指定枢纽元 
 90 {
 91     if(s>=e) return;
 92     
 93     int pivot=(s+e)/2;//指定枢纽元 
 94     
 95     int i=s-1;
 96     int j=s-1;
 97     while(++i <= e)
 98     {
 99         if(a[i]<a[pivot])
100         {
101             swap(&a[i],&a[++j]);
102             if(pivot==j) pivot=i;
103         }
104     }
105     swap(&a[pivot],&a[++j]);
106     quickSort2(a,s,j-1);
107     quickSort2(a,j+1,e);
108 }

View Code