数据结构与算法分析--快速排序

   关于快速排序的描述，网上有很多的资料， 我这里引用wiki上的解释来说明一下：

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

从数列中挑出一个元素，称为 "基准"（pivot）， 
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 
递回的最底部情形，
是数列的大小是零或一，也就是永远都已经被排序好了。
虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

 

   而学习这个算法的时候，我发现网上有很多资料，但是唯独很少有图解的部分，对于我这样的算法新手来说，理解起来要费点劲。 OK， 现在我把我自己学习这个算法的一些东西，做个图解发上来， 希望能减少新手的学习成本，能对算法的执行过程有个直观的认识，那样的话，就会提高不少效率。（本人学习的时候，效率比较低。） 

    

     我们以java语言为例， wiki上有相关的示例：

 

package com.bbs;

import java.util.Comparator;
import java.util.Random;

/**
 * 快速排序使用分治法（Divide and conquer）策略
 * 来把一个序列（list）
 * 分为两个子序列（sub-lists）。
步骤为：
	1.从数列中挑出一个元素，称为 "基准"（pivot）， 
	2.重新排序数列，
		所有元素比基准值小的摆放在基准前面，
		所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
		在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 
	3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 

 * @author google
 */
public class QuickSort {
		public static void main(String[] args) {
			int[] intt={5,7,9,3,14};
			qsort(intt,0,intt.length-1);
			for (Integer i:intt) {
				System.out.println(i);
			}
		}
		public static final Random RND=new Random();
		
		/**
		 * 交换指定元素
		 * @param ary
		 * @param i
		 * @param j
		 */
		public static void swap(int[] ary,int i,int j){
			int tmp=ary[i];
			ary[i]=ary[j];
			ary[j]=tmp;
		}
		
		/**
		 * 获取枢纽元素
		 * @param ary
		 * @param begin
		 * @param end
		 * @param cmp
		 * @return
		 */
		private static int partition(int[] ary,int begin,int end){
			//随即定位枢纽的位置
			int index=begin+RND.nextInt(end-begin+1);
//			int index=0;
			//获取枢纽的值
			int pivot=ary[index];
			//获取枢纽后， 将其置放到数组的最后一个位置
			swap(ary,index,end);
			//之后循环数组， 与曲扭进行比较, 相当于重新排数组
			for(int i=index=begin;i<end;i++){
				//如果当前元素小于枢纽,则交换位置
				if(ary[i]<pivot){
					swap(ary, index++, i);
				}
			}
			swap(ary, index, end);
			return index;
		}

		/**
		 * 执行快速排序的方法
		 * @param ary
		 * @param begin
		 * @param end
		 * @param cmp
		 */
		public static void qsort(int[] ary,int begin,int end){
			if(end>begin){
				//找到枢纽
				int index=partition(ary, begin, end);
				
				qsort(ary, begin, index-1);
				qsort(ary, index+1, end);
			}
		}
		
		public static void sort(int[] ary){
			qsort(ary, 0,ary.length-1);
		}
}

 

  下面，我以一个上述main方法中的调用为例，来把每一步算法执行过程图解一下。 当然，这个算法最核心的部分就是查找枢纽的方法。 也就是

/**
		 * 获取枢纽元素
		 * @param ary
		 * @param begin
		 * @param end
		 * @param cmp
		 * @return
		 */
		private static int partition(int[] ary,int begin,int end){
			//随即定位枢纽的位置
			int index=begin+RND.nextInt(end-begin+1);
//			int index=0;
			//获取枢纽的值
			int pivot=ary[index];
			//获取枢纽后， 将其置放到数组的最后一个位置
			swap(ary,index,end);
			//之后循环数组， 与曲扭进行比较, 相当于重新排数组
			for(int i=index=begin;i<end;i++){
				//如果当前元素小于枢纽,则交换位置
				if(ary[i]<pivot){
					swap(ary, index++, i);
				}
			}
			swap(ary, index, end);
			return index;
		}

 

  OK, 开始。  我们输入数组

int[] intt={5,4,7,10,3};

 

  调用qsort方法， 其首先会要去查找枢纽位置。

public static void qsort(int[] ary,int begin,int end){
			if(end>begin){
				//找到枢纽
				int index=partition(ary, begin, end);
				qsort(ary, begin, index-1);
				qsort(ary, index+1, end);
			}
		}
		

    

    直接进入这个方法。

private static int partition(int[] ary,int begin,int end){
			//随即定位枢纽的位置 这里假设index为 0 既以第一个元素 5 为枢纽值
			int index=begin+RND.nextInt(end-begin+1);
			//获取枢纽的值
			int pivot=ary[index];
			//获取枢纽后， 将其置放到数组的最后一个位置
			swap(ary,index,end);
			//之后循环数组， 与曲扭进行比较, 相当于重新排数组
			for(int i=index=begin;i<end;i++){
				//如果当前元素小于枢纽,则交换位置
				if(ary[i]<pivot){
					swap(ary, index++, i);
				}
			}
			swap(ary, index, end);
			return index;
		}

    

   那数组的初始图为：
         

     在获取枢纽值后，我们将枢纽值与最后一元素交换， 则存储图为：        
        

     

       ok, 现在我们要做的事情就是要重排数组

     既：

   

2.重新排序数列，
		所有元素比基准值小的摆放在基准前面，
		所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
		在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 

（代码中体现在for循环中， for(int i=index=begin;i<end;i++）  

当然，这里有个值得注意的地方， index=begin. index由原来指向枢纽的位置，被重新定位到了数组的开始位置

    则进行for循环的次数为end,  这里我们要注意的是 end的实际参数值为 数组的.length-1. 这里既是4 

    每次循环中，数组的变化如下图，  注意， 小于枢纽5的只有 数组的第4个元素 3哦， 执行到这里，程序会有变化，注意看图：

     第一次循环
 

 

       第2次循环

 

 

     第3次循环：

  
  

 

    第4次循环(3<5)： 交换小于枢纽的值到数组的第一位，同时index也++操作。

     可以理解为记录小于枢纽的数的数量，同时也是下一个小于枢纽数的存储位置。

   （如果还有小于枢纽值的话，就把它存放到ary[index++]位置上，既ary[1]上。）    
  

 

最后，在for循环结束后， 需要将枢纽数放到数组的分界处，并返回枢纽的位置。return index.

（个人这样理解，因为之前说过，index代表着所有小于枢纽数数量，也是下一个小于枢纽数的位置。

  那么当数组中再没有小于枢纽数的时候， index就标识枢纽值自己本身应该去的地方， 如图中的

  3,5,9,14,7 这里index就是1。那么index左边的都是小于枢纽的数.）

    
 
 
 OK,这样，快速排序就把第一次的枢纽位置找到了,然后，将数组按枢纽位置划分为2部分。

 既 所有小于枢纽值的部分 ary[begin,index-1] 

     所有大于枢纽值的部分  ary[index+1,end]

 

  再利用递归，分别对两部分进行再一次的quicksort.

 最后，将所有的部分合并起来，就可以得到一个最后有序的数组了。

  最后发一张快速排序执行的动态图， 你也可以从WIKI上找得到。

  

 

 

 

   这里就快速排序的执行做了一个简单的介绍，希望对刚学快排的朋友有帮助，由于自身水平的有限，所以文章水平也很有限，希望各位拍拍砖。

 

    

评论

5 楼 gogole_09 2010-01-16  

yymt 写道

LZ 算法好象略有不同;感觉还有改进的地方
没仔细看,但看里面有for循环,感觉不怎么完美,因为快速排序里用的不是for循环..
假设有数据: 5 8 10 16 12 14 8 20 22 记为a[i]
使用两个计数 forword(从前往后走),back(从后往前走),选定的基数为temp
forword=1;
back=9;
temp=12;
while(forword<back)
{
  while(a[forword]<=temp) forword++;
  while(a[back]>temp) back --;
  a[forword] <-> a[back]; //交换数
  forword++;
}

  呵呵，兄弟说得是， 确实没注意， 可能是当时写代码的时候 ，过多的关注于算法的实现原理，而忽略了算法的性能因素了。 看来还是只学到形似，惭愧，惭愧……

4 楼 yymt 2010-01-15  

LZ 算法好象略有不同;感觉还有改进的地方
没仔细看,但看里面有for循环,感觉不怎么完美,因为快速排序里用的不是for循环..
假设有数据: 5 8 10 16 12 14 8 20 22 记为a[i]
使用两个计数 forword(从前往后走),back(从后往前走),选定的基数为temp
forword=1;
back=9;
temp=12;
while(forword<back)
{
  while(a[forword]<=temp) forword++;
  while(a[back]>temp) back --;
  a[forword] <-> a[back]; //交换数
  forword++;
}

3 楼 yymt 2010-01-15  

动态图做的很好哦...

2 楼 xiaoxinfq8 2010-01-14  

很详细，呵呵

1 楼 luffyke 2010-01-13  

不错不错！！学习了