八大排序算法之快速排序

排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是：先选一个“标尺”， 用它把整个队列过一遍筛子， 以保证：其左边的元素都不大于它，其右边的元素都不小于它。 这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。 #include <cstdio> void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } int partition(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p]; while(1) { while(i<r && a[++i]<x);//小于找的那个数左边就往右移动 while(a[--j]>x);//大于就往左移动 if(i>=j) break; swap(a,i,j);//如果i<j并且满足上面条件，进行交换 } swap(a, p, j);//如果找到比标尺小的进行交换，换成小的那个 return j;//并返回找到的那个标尺 } void quicksort(int a[], int p, int r) { if(p<r){ int q = partition(a,p,r); quicksort(a,p,q-1);//前一半进行快排 quicksort(a,q+1,r);//后一半进行排序 } } int main() { int i; int a[] = {5,13,6,24,2,8,19,27,6,12,1,17}; int N = 12; quicksort(a, 0, N-1); for(i=0; i<N; i++) printf("%d ", a[i]); printf("\n"); return 0; }