想想写代码也3年多了,虽然能够理解快速排序的思想,但是从来没有写过一次标准版的快速排序代码,因此今天准备写下。
快排的思想可以简单说明为:首选在数组中选取一个数,比这个数小的全部放到左边,比这个数大的全部放到右边,然后在递归左边和右边重复该过程,就能将数组排序了。
快速排序的Partition过程如下:
int partition(int a[],int l,int r) { swap(a[(l+r)>>1],a[r]);//取中间值下标的值为分界线 int x = a[r]; int i = l - 1;//i用来记录比x小的数下标 for(int j = l ; j < r ; j ++) { if(a[j] < x)//比x小的数放到左边 { i ++; swap(a[i],a[j]);//交换 } } swap(a[i+1],a[r]);//由于从l到i都是比x小的数,那么下标i+1就应该是分界的x即a[r] return i + 1; }//这里从l到i都比i+1小,i+2到r都比i+1大
快排函数:
void qsort(int a[],int l,int r) { int q; if(l < r) { q = partition(a,l,r); qsort(a,l,q-1);//对左边进行排序 qsort(a,q+1,r);//对右边进行排序 } }
快速排序算法就介绍完了,很简单啦。
下面介绍线性时间求解数组第K小数
对Partition函数分析我们可以知道从l到i都比i+1小,i+2到r都比i+1大。
因此求解第k小数可以这样来写:
int select(int a[],int k,int l,int r)//找出数组中第K小元素 { if(l == r) return a[l];//数组中只有一个数 int q = partition(a,l,r); int t = q - l + 1;//左边数的个数 if(k == t) return a[q];//k==t那么a[q]就是答案 else if(k < t) return select(a,k,l,q-1);//在左边进行查找 else return select(a,k-t,q+1,r);//在右边进行查找,注意这里就需要查找第k-t小数了 }
这里的时间复杂度是O(n)
求解第k小数其实还有另外一种方法,那就是运用堆,建立一个K大的最大顶堆即可,数组遍历完,在堆顶的元素就是第K小数。
由于每次都需要调整最大顶堆,所以该算法的时间复杂度是O(klogk)。
后记:我平时所写的qsort
void qsort(int l,int r) { int i = l , j = r , x = a[(l+r)>>1]; while(i < j) { while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) { swap(a[i],a[j]); i++,j--; } } if(l < j) qsort(l,j); if(i < r) qsort(i,r); }