Chinaunix首页 | 论坛 | 博客
  • 博客访问: 376782
  • 博文数量: 47
  • 博客积分: 967
  • 博客等级: 准尉
  • 技术积分: 1290
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-25 16:14
文章分类

全部博文(47)

文章存档

2019年(1)

2014年(1)

2013年(9)

2012年(36)

分类: LINUX

2012-10-08 21:15:08

  学数据结构时看过快速排序,但是没有具体去分析,今天静下心来,仔细看了一下这个算法,算是明白了,和大家分享一下,也方面以后查询。
  其实快速排序的核心思想是分治策略,即先分解再递归求解,最后再合并。
  具体来说就是在待排序记录序列中选取一个记录(通常先选取第一个记录)为驱轴,其关键字设为K1,然后将其余关键字小于K1的记录移到前面,而将关键字大于K1的记录移到后面,这样K1就将记录分成了两部分,这有点类似于二分查找。在一次划分之后,对分割后的子表继续按上述原则进行分割,直到所有的子表长不超过1为止,此时待排序记录序列就变成了一个有序表。
 下面是我写的一个测试程序:


  1. #include <stdio.h>
  2. #define N 8

  3. void quicksort(int a[],int m,int n);
  4. int quickpass(int a[],int left,int right);
  5. int main()
  6. {
  7.     int i,m,n;
  8.     int a[N]={48,63,35,76,54,12,35,88};
  9.     m=0;     
  10.     n=N-1;
  11.     quicksort(a,m,n);
  12.     for(i=0;i<N;i++)  //排序后的数据
  13.        printf("%d ",a[i]);
  14.     printf("\n");
  15.     return 0;
  16. }

  17. void quicksort(int a[],int m,int n
  18. //参数m表示每个子表的第一个元素,n表示每个子表的最后一个元素
  19. {
  20.     int p;
  21.     if(m < n)
  22.     {
  23.     p=quickpass(a,m,n); //调用一趟快速排序,寻找枢轴,以轴元素为界限将数组划分成两个子表。
  24.     quicksort(a,m,p-1); //对左部子表快速排序
  25.     quicksort(a,p+1,n)//对右部子表快速排序
  26.     }
  27. }
  28. int quickpass(int a[],int left,int right)
  29. {
  30.     int x,low,high;
  31.     x=a[left];  //记录枢轴元素
  32.     low=left;
  33.     high=right;
  34.     while(low < high)
  35.     {
  36.      while(low < high && a[high] >= x)   high--;
  37.     //high从右向左找小于x的元素    
  38.      if(low < high)//找到小于x的记录则进行交换。
  39.      {a[low] = a[high];low++;}

  40.      while(low < high && a[low] < x) low++;
  41.    //low从左向右找大于x的元素    
  42.      if(low < high)//找到大于x的记录则进行交换。
  43.      {a[high]=a[low];high--;}

  44.     }
  45.     a[low]=x;   //将枢轴元素保存到low=high的位置
  46.     return low; //返回枢轴元素的位置
  47. }
 如果有疑惑的可以提出来。或者自己调试一下可能会理解的更透彻一些。。。
阅读(9964) | 评论(2) | 转发(3) |
给主人留下些什么吧!~~

lwp2252012-10-09 16:08:47

呵呵,

db892012-10-09 14:26:12

嗯,不错,学习了!