快速排序法基本思想:
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
程序代码:
#include <stdio.h> void print(int a[], int n) { int j; for(j=0; j < n; j++) printf("%d ", a[j]); printf("\n"); } void quick_sort(int num[], int left, int right) { int tmp, low = left, high = right; int privotKey = num[low]; /*假定阈值为a[low]*/ static count = 0; if(low >= high) /*结束条件*/ return; while(low < high) { while(low<high && num[high]>privotKey) --high; /*从高到低找出一个不大于阈值的值*/ while(low<high && num[low]<privotKey ) ++low; /*从低到高找出一个不小于阈值的值*/ tmp = num[low]; /*交换找到的两个值*/ num[low] = num[high]; num[high] = tmp; } printf("第%d趟: ", ++count); print(num, 10); quick_sort(num, left, low-1); quick_sort(num, low+1, right); } int main() { int num[10] = {5, 1, 3, 7, 2, 4, 9, 6, 10, 8}; printf("原始值:"); print(num, 10); quick_sort(num, 0, 9); printf("排序后:"); print(num, 10); return 0; }程序运行截图:
快速排序法的特点:
时间复杂度:最差为O(n^2),最好为nlog(2^n)
空间复杂度:O(log(2^n))
稳定性:不稳定
原文:http://blog.csdn.net/laoniu_c/article/details/38586723