作者:李慧芹,华清远见嵌入式学院讲师。
快速排序实质上是对“冒泡排序”的一种改进,整个排序过程可概括为:通过N趟的排序将原本的排序数据分为若干块进行分块排序,而在每趟排序过程中,以指定的关键字将待排数据分别分为比关键字大的部分和比关键字小的部分,反复上述过程,将整个待排数列分散为若干个小数列而分别进行排序操作。假设我们现对一列数进行快速排序,其C语言代码实现如下:
#include <stdio.h> int partition(int *data,int low,int high); void sort(int *data,int low,int high); void quick_sort(int *data,int n); int main() { int i; int data[]={49,38,32,98,65,74,12,8}; quick_sort(data,sizeof(data)/sizeof(int)); for( i = 0 ; i < sizeof(data)/sizeof(int); i++) printf("%d ",data[i]); printf("\n"); return 0; } int partition(int *data,int low,int high) { int t = 0; t = data[low]; while(low < high) { while(low < high && data[high] >= t) high--; data[low] = data[high]; while(low < high && data[low] <= t) low++; data[high] = data[low]; } data[low] = t; return low; } //快排每趟进行时的枢轴要重新确定,由此进 //一步确定每个待排小记录的low及high的值 void sort(int *data,int low,int high) { if(low >= high) return ; int pivotloc = 0; pivotloc = partition(data,low,high); sort(data,low,pivotloc-1); sort(data,pivotloc+1,high); } //该函数进行sort过程的调用 void quick_sort(int *data,int n) { sort(data,0,n-1); }