Zack Blog

快速排序

快速排序

    快速排序(以下简称快排)是一种排序算法,有C.A.R.Hoare所发展的,就如同他的名字一样,它的特点就是快。以平均效能来说,排序n个项目有O(n log n)次比较。在最差的效能下它需要O(n^2)次比较,所以它是一种不稳定排序法。


思路:
    快排使用的分治(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。令其中一个子序列的元素小于另一个子序列,在对两个子序列采取同样递归操作。

    (顺序排列)步骤为:
    1.在数列中挑出一个元素作为"基准"(pivot)。
    2.将比基准小的移到基准前面,比基准大的移到基准后面(相同的可以不必理会)。
    3.递归(recursive)地对两个子序列排序。

    C代码实现如下:

 1 #include<stdio.h>
 2 #define swap(x,y) {int t;t = x;x = y;y = t;} /*用于交换x和y的值*/
 3 
 4 void quicksort(int *a,int left,int right)
 5 {
 6   int i=left,j=right+1,pivot=a[left]; /*以最左边的元素为“基准”*/
 7   while(1)
 8     {
 9       while(++i<=right&&a[i]<pivot); /*从左边逐个找,直到找到比“基准”大的元素*/
10       while(--j>=left&&a[j]>pivot); /*从右边逐个找,直到找到比“基准”小的元素*/
11       if(i>=j) break;
12       swap(a[i],a[j]);
13     }
14   swap(a[j],a[left]); /*执行完上面的循环,j必定在i的位置活i的左边,且a[j]小于"基准",所以交换a[j]和“基准”*/
15   if(left<j) quicksort(a,left,j); /*对“基准”左边排序*/
16   if(i<right) quicksort(a,i,right); /*对“基准”右边排序*/
17 }
18 
19 int main()
20 {
21   int D[10]={9,8,7,6,5,4,3,2,1,0};
22   int i=0;
23   /* 输出排序前的数组 */
24   while(i<10)
25     printf("%d ",D[i++]);
26   putchar('\n');
27 
28   quicksort(D,0,9);
29 
30   i=0;
31   /* 输出排序后的数组 */
32   while(i<10)
33     printf("%d ",D[i++]);
34   putchar('\n');
35 
36   return 0;
37 }
38 
     其实在C下对于快排可以直接使用qsort()(在stdlib.h有文件下),C++下可以使用sort()(在algorithm头文件下)。现在对C++的sort()掌握的还不是非常彻底,有机会再好好整理一下。

posted on 2009-08-18 13:22 Zack Chen 阅读(195) 评论(0)  编辑 收藏 引用 所属分类: 常见算法


只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理