快排：
思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码：
1 #include <iostream> 2 using namespace std; 3 void partition(short a[],int s,int t,int &k); 4 void qksort(int a[],int i,int j); 5 int main() 6 { 7 int n,i; 8 cin>>n; 9 int a[n]; 10 for(i=0;i<n;i++) cin>>a[i]; 11 qksort(a,0,n-1); 12 for(i=0;i<n;i++) cout<<a[i]<<' '; 13 system("pause"); 14 return 0; 15 } 16 void partition(int a[],int s,int t,int &k) 17 { 18 int x,i,j; 19 x=a[s]; 20 i=s; 21 j=t; 22 while(i<j) 23 { 24 while(i<j&&a[j]<=x) 25 j--; 26 if(i<j) 27 a[i++]=a[j]; 28 while(i<j&&a[i]>x) 29 i++; 30 if(i<j) 31 a[j--]=a[i]; 32 } 33 a[i]=x; 34 k=i; 35 } 36 void qksort(int a[],int i,int j) 37 { 38 int k; 39 if(i<j) 40 { 41 partition(a,i,j,k); 42 qksort(a,i,k-1); 43 qksort(a,k+1,j); 44 } 45 }
归并排序：
思想：
归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时， 在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在 归并排序中的合并过程中计算逆序数.
代码：//比较经典的一个归并排序求逆序对
1 //给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列. 2 #include <iostream> 3 #include <string.h> 4 #include <stdio.h> 5 6 using namespace std; 7 const int N = 1005; 8 9 int a[N],tmp[N]; 10 int ans; 11 12 void Merge(int l,int m,int r) 13 { 14 int i = l; 15 int j = m + 1; 16 int k = l; 17 while(i <= m && j <= r) 18 { 19 if(a[i] > a[j]) 20 { 21 tmp[k++] = a[j++]; 22 ans += m - i + 1; 23 } 24 else 25 { 26 tmp[k++] = a[i++]; 27 } 28 } 29 while(i <= m) tmp[k++] = a[i++]; 30 while(j <= r) tmp[k++] = a[j++]; 31 for(int i=l;i<=r;i++) 32 a[i] = tmp[i]; 33 } 34 35 void Merge_sort(int l,int r) 36 { 37 if(l < r) 38 { 39 int m = (l + r) >> 1; 40 Merge_sort(l,m); 41 Merge_sort(m+1,r); 42 Merge(l,m,r); 43 } 44 } 45 46 int main() 47 { 48 int n,T,tt=1; 49 scanf("%d",&T); 50 while(T--) 51 { 52 scanf("%d",&n); 53 for(int i=0;i<n;i++) 54 scanf("%d",&a[i]); 55 ans = 0; 56 Merge_sort(0,n-1); 57 printf("Scenario #%d: %d ",tt++,ans); 58 } 59 return 0; 60 }
计数排序（桶排，鸽巢排序）：
鸽巢排序：
1 public void pigeonSort(int[] array, int max) { 2 int[] c = new int[max];//max是array数组中的最大值 3 for(int i=0; i<array.length; i++) 4 c[array[i]]++; 5 //c数组只是统计元素出现次数 6 int k = 0; 7 for(int i=0; i<max; i++) 8 for(int j=1; j<=c[i]; j++) 9 array[k++] = i; 10 }
摘自百度百科里的c++实现方法：
1 #include<iostream> 2 usingnamespace std; 3 int a[]= {1,255,8,6,25,47,14,35,58,75,96,158,657}; 4 const int len=sizeof(a)/sizeof(int); 5 int b[10][len+1]= {0}; //将b全部置0 6 void bucketSort(int a[]);//桶排序函数 7 void distribute Elments(int a[],int b[10][len+1],int digits); 8 void collectElments(int a[],int b[10][len+1]); 9 int numOfDigits(int a[]); 10 void zeroBucket(int b[10][len+1]);//将b数组中的全部元素置0 11 int main() 12 { 13 cout<<"原始数组："; 14 for(int i=0; i<len; i++) 15 cout<<a[i]<<","; 16 cout<<endl; 17 bucketSort(a); 18 cout<<"排序后数组："; 19 for(int i=0; i<len; i++) 20 cout<<a[i]<<","; 21 cout<<endl; 22 return 0; 23 } 24 void bucketSort(int a[]) 25 { 26 int digits=numOfDigits(a); 27 for(int i=1; i<=digits; i++) 28 { 29 distributeElments(a,b,i); 30 collectElments(a,b); 31 if(i!=digits) 32 zeroBucket(b); 33 } 34 } 35 int numOfDigits(int a[]) 36 { 37 int largest=0; 38 for(int i=0; i<len; i++) //获取最大值 39 if(a[i]>largest) 40 largest=a[i]; 41 int digits=0;//digits为最大值的位数 42 while(largest) 43 { 44 digits++; 45 largest/=10; 46 } 47 return digits; 48 } 49 void distributeElments(int a[],int b[10][len+1],int digits) 50 { 51 int divisor=10;//除数 52 for(int i=1; i<digits; i++) 53 divisor*=10; 54 for(int j=0; j<len; j++) 55 { 56 int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10); 57 //numOfDigits为相应的(divisor/10)位的值,如当divisor=10时,求的是个位数 58 int num=++b[numOfDigist][0];//用b中第一列的元素来储存每行中元素的个数 59 b[numOfDigist][num]=a[j]; 60 } 61 } 62 void collectElments(int a[],int b[10][len+1]) 63 { 64 int k=0; 65 for(int i=0; i<10; i++) 66 for(int j=1; j<=b[i][0]; j++) 67 a[k++]=b[i][j]; 68 } 69 void zeroBucket(int b[][len+1]) 70 { 71 for(int i=0; i<10; i++) 72 for(int j=0; j<len+1; j++) 73 b[i][j]=0; 74 }
待续。