【排序】快速排序

前言

快速排序（Quick Sort）算法是 “递归+分治”算法一个很好的应用。

算法思想

     快速排序是找出一个元素（理论上可以随便找一个 注1）作为基准值(pivot)，然后对数组进行分区操作：找到基准点——使基准点左边元素的值都不大于基准值，基准点右边的元素值都不小于基准值，找到基准点后就可以将基准值放到基准点上，这样在该基准点左边的值都小于右边的值，基准点两边为两个分区。递归体现为，对前个阶段产生的分区再找基准点产生了分区再找基准点...直到分区中只有一个元素为止或者说所有元素都排好序为止。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

 

注1 基准位置不同的影响？

名词：基准值和基准点

基准值一般选择某partition的第一个元素。

该partition的基准点是这样一个点：在该partition中，该点左边的所有元素不大于点右边的元素。

基准点是分区的依据。

 

算法演示

 

   2  8  7  1  3  5  6  4
  i->                     <-j
   (找大)                (找小)

这里找大和找小都是与i和j位置上的数与基准值比较
一、j
j找第一个小于2的元素1,1赋给(覆盖重置)i所指元素2
得到：
   1  8  7     3  5  6  4
      i       j       
      
二、i
i找到第一个大于2的元素8,8赋给(覆盖重置)j所指元素(NULL<-8)
   1     7  8  3  5  6  4
      i   <-j

三、j
j继续左移，在与i碰头之前，没有找到比2小的元素，结束。
最后，主元2补上。
第一趟快排结束之后，数组变成：
  1  2  7  8  3  5  6  4

第二趟，
        7  8  3  5  6  4
        i->             <-j
         (找大)        (找小)
  
一、j
j找到4，比主元7小，4赋给7所处位置
得到：
        4  8  3  5  6   
        i->                j
二、i
i找比7大的第一个元素8,8覆盖j所指元素(NULL)
        4     3  5  6  8
            i          j
        4  6  3  5     8
            i->       j
                 i与j碰头，结束。
第三趟：
        4  6  3  5  7  8
......
以下，分析原理，一致，略过。
最后的结果，如下图所示：
  1  2  3  4  5  6  7  8

算法实现

两个函数Partition和QuickSort。Partition负责分区（或者说寻找某分区的基准点）。QuickSort负责递归，将某个区再分区，直到一个分区只有一个元素为止。

 

在某个分区中找基准点过程中，分别有指针从分区头和尾向中间移动，R指针向左移动，寻找小于基准值的位置，如果小于基准值则停止左移，将该位置上的值赋给L指针所在位置。然后，L指针右移，寻找大于基准值的位置，如果大于基准值则停止右移，将该位置上的值赋给R指针所在位置，然后再由R指针左移。。直达R指针遇到L 指针为止。此时L指针所指位置即为要寻找的基准点。

 

//begin :一个parttition的起始点，end ：partition的结束点
//return :该partition的基准点
int Partition(int array[],int begin,int end){
  int privot = array[begin]//基准值
  int L = begin;
  int R = end;
  while(L < R){
     while(R > L && array[R] > privot)
        R--;
     array[L] = array[R];
     while(R > L && array[L] < privot)
        L++;
     array[R] = array[L];
  }
  array[L] = privot;//将基准值放到基准点
  return L;
}

 void QuickSort(int array[],int begin,int end){
  int privot;
  while(begin < end){
     privot = Partition(array,begin,end);
     QuickSort(array,privot+1,end); //递归
     QuickSort(array,begin,privot-1);
  }
}

 

性能分析

 

相关应用

 

参考阅读

1. http://www.cnblogs.com/zabery/archive/2011/07/27/2118353.html

再研究下性能分析部分

 

2. http://jsdo.it/norahiko/oxIy/fullscreen

多个排序算法的演示

 

3.JDK Arrays.sort(int[])对快排的优化

http://hxraid.iteye.com/blog/665095

 

4.完整的文章

http://blog.csdn.net/v_JULY_v/article/details/6116297