Chinaunix首页 | 论坛 | 博客
  • 博客访问: 601444
  • 博文数量: 68
  • 博客积分: 2621
  • 博客等级: 少校
  • 技术积分: 1498
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-23 21:04
文章分类

全部博文(68)

文章存档

2013年(8)

2012年(52)

2010年(8)

分类:

2012-09-11 09:38:50

原文地址:快速排序浅谈 作者:雨天搁浅

          快速排序作为分治法的一种,也同样遵循分治法的基本步骤---分解、治之、合并。我们在分解之前得选一个元素元素作为分解的依据,相当于一个基本点。
          分解:以支点为界将序列分解为两个子序列,其中一个子序列里的元素小于等于支点,另一个子序列的元素大于支点。
          治之:对两个子序列进行快速排序(递归)。
          合并:将排好序的两个子序列合并成一个大序列。
例如有一个数组A[p,r],p代表数组首元素的下标,而r则代表数组末元素的下标。则对其进行快速排序的过程为:

  1. quick(A,p,r)
  2. {
  3.    if(p<r)
  4.    {
  5.       q = partition(A,p,r);
  6.       quick(A,p,q-1);
  7.       quick(A,q+1,r);
  8.    }
  9. }
上面这个排序过程的关键就是partion这个过程,它对数组A进行就地重排。下面我们来看看partion这个过程的实现::

点击(此处)折叠或打开

  1. partition(A,p,r)
  2. {
  3.     x = A[r];
  4.     i = p-1;     //i初始化为子序列第一个元素的下标减1
  5.      for(j=p;j<r;j++)
  6.      {
  7.         if(A[j]<=x)
  8.         {
  9.           i++;
  10.           exchange A[i]<-->A[j]
  11.         }
  12.      }
  13.      exchange A[i+1]<-->A[r]
  14.     return i+1;
  15. }
在这里我们取子序列中最后一个元素作为支点元素:下面的图为上面算法过程的图示


在执行到 h 的时候循环已跳出,交换A[i+1] 与A[r] 。至此所有比支点小的元素都已放在了支点的左边,而所有比支点元素大的数也都放在了其右边,将i+1返回,partition函数的功能完成。则第一个子序列为 (2,1,3) 第二个子序列为(7,5,6,8)。下面对这两个子序列分别进行quick(),当p不小于 r 时递归结束,下面进行合并,由于我们这儿排序
是就地排序所以合并这个环节也就可以省去了。。



阅读(1019) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~