快速排序(1)

快速排序

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

思路:

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

(顺序排列)步骤为:

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

C代码实现如下:

#include<stdio.h>
#define swap(x,y) {int t;t = x;x = y;y = t;} /*用于交换x和y的值*/
 
void quicksort(int *a,int left,int right)
{
  int i=left,j=right+1,pivot=a[left]; /*以最左边的元素为“基准”*/
  while(1)
    {
      while(++i<=right&&a[i]<=pivot); /*从左边逐个找,直到找到比“基准”大的元素*/
      while(--j>left&&a[j]>=pivot); /*从右边逐个找,直到找到比“基准”小的元素*/
      if(i>=j) break;
      swap(a[i],a[j]);
    }
  swap(a[j],a[left]); /*执行完上面的循环,j必定在i的位置活i的左边,且a[j]小于"基准",所以交换a[j]和“基准”*/
  if(left<j) quicksort(a,left,j); /*对“基准”左边排序*/
  if(i<right) quicksort(a,i,right); /*对“基准”右边排序*/
}
 
int main()
{
  int D[10]={9,8,7,6,5,4,3,2,1,0};
  int i=0;
  /* 输出排序前的数组 */
  while(i<10)
    printf("%d ",D[i++]);
  putchar('n');
 
  quicksort(D,0,9);
 
  i=0;
  /* 输出排序后的数组 */
  while(i<10)
    printf("%d ",D[i++]);
  putchar('n');
 
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>