冒泡排序：稳定，时间复杂度O(n2)，空间复杂度O(1)
//bubble void bubblesort(int *a, int n) { int hig=n-1; int i; while(hig) { for(i=0;i<=hig-1;i++) { if(a[i]>a[i+1]) swap(&a[i],&a[i+1]); } hig--; } }
鸡尾酒排序：稳定，时间复杂度O(n2)，空间复杂度O(1)。冒泡排序的变形。
//cocktail void cocktailsort(int *a ,int n) { int low=0,hig=n-1; int i; while(low<hig) { for(i=low;i<=hig-1;i++) { if(a[i]>a[i+1]) swap(&a[i],&a[i+1]); } hig--; for(i=hig;i>=low+1;i--) { if(a[i]<a[i-1]) swap(&a[i],&a[i-1]); } low++; } }
插入排序：稳定，时间复杂度O(n2)，空间复杂度O(1)
//insert void insertsort(int *a, int n) { int i,j; for(i=1;i<n;i++) { j=i; while(j>=1&&a[j]<a[j-1]) { swap(&a[j],&a[j-1]); j--; } } }
快速排序：不稳定，时间复杂度平均O(nlogn)，最坏O(n2)，空间复杂度O(logn)。
三种实现：前两种两个指针一前一后，后一种指针都在前。第二种不使用交换。
//qsort void quicksort1(int *a, int low, int hig) { int key=a[low]; int i=low, j=hig; while(i<j) { while(i<j) { if(a[j]<key) { swap(&a[i],&a[j]); i++; break; } else j--; } while(i<j) { if(a[i]>key) { swap(&a[i],&a[j]); j--; break; } else i++; } } if(i-1>=low) quicksort1(a,low,i-1); if(i+1<=hig) quicksort1(a,i+1,hig); } void quicksort2(int *a, int low, int hig) { int key=a[low]; int i=low, j=hig; while(i<j) { while(i<j&&a[j]>=key) j--; if(i<j) a[i++]=a[j]; while(i<j&&a[i]<=key) i++; if(i<j) a[j--]=a[i]; } a[i]=key; if(i-1>=low) quicksort2(a,low,i-1); if(i+1<=hig) quicksort2(a,i+1,hig); } void quicksort3(int *a, int low, int hig) { int key=a[hig]; int i=low-1, j=low; while(j<hig) { if(a[j]<a[hig]) { i++; swap(&a[i],&a[j]); j++; } else j++; } swap(&a[++i],&a[hig]); if(i-1>=low) quicksort3(a,low,i-1); if(i+1<=hig) quicksort3(a,i+1,hig); }
原文：http://www.cnblogs.com/mr-redrum/p/3494511.html