ALL is Well!

敏捷是一条很长的路,摸索着前进着

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  30 随笔 :: 23 文章 :: 71 评论 :: 0 Trackbacks

本文为原创,欢迎转载,转载请注明出处BlogJava
快速排序的算法思想:
快速排序采用了分治的策略,将原问题分解为若干个规模更小但结构与原问题相似的子问题。用递归方法解决子问题,然后将这些子问题的解组合为原问题的解。

快速排序的程序的一般过程可简单描述为:
1.用统一的方法取得 pivot(轴)。
2.根据pivot 对已有数组进行排序
    1) 将array[pivot]存储在tmp变量中,作为比较基准。
    以low、high分别从前向后、从后向前遍历数组
    2) 从后向前遍历,找到第一个小于tmp的数,将其移动到low的位置。
    3) 从前向后遍历,找到第一个大于tmp的数,将其移动到high的位置。
    4) 循环2、3步,直到两指针重叠(即退出循环的条件是 low >= high),将tmp移动到low(此时low与high重合)的位置,并将low返回成为新的pivot。
    5) 根据4步返回的pivot,对已有数组进行划分,0~pivot-1 和 pivot+1 ~ array.lenght,递归1~5步。直到调用退出。

相信对于以上理论大家一定是耳熟能详了,但理解起来还是比较抽象,下面我就用Excel画图简单的描述一下 快速排序 的过程。

假设我们要写一个程序对已有数组进行排序,简单起见,设定待排序数组为 int[] array = { 4, 2, 1, 7, 5, 3, 8, 6 }。对其用快速排序算法进行排序,过程描述如下:
1.根据已有待排序数组,取得pivot,我在这里取得pivot的策略就是 取 数组的第一个数,这里即为 4。
   tmp = 4;

待排序数组:黄色底色表示pivot。



2.从后向前移动high,找到第一个小于tmp的数,则将该数移动到low的位置。



3.从前向后移动low,找到第一个大于tmp(4)的数,将其移动到high的位置。


4.然后再向前移动high,试图找到第一个小于tmp(4)的数,但没有找到,此时low与high重叠,将tmp的值放入low的位置,并将low作为pivot返回。




  根据新的pivot进行递归调用,将原待排序数组 分解为两块,index区间分别为0~2,4~7,即以下两个子数组
  (并未新建数组,只是只关注这个区间的数据,对其进行排序,也就是将问题分解为两个小的子问题,但问题很类似。)
 

这两个数组的排序过程这里就不画了,一样的过程。

下面来看看实现的代码,与刚刚的过程描述是符合的:

package com.bz.sort.algorithm;

public class QuickSort {
    
/**
     * 对外调用的方法入口。
     * 
@param array 待排序数组
     
*/

    
public void sort(int[] array) {
        
if (array == null || array.length < 0{
            
throw new RuntimeException("待排序数组中无数据。");
        }


        
// 排序
        sort(array, 0, array.length - 1);
    }


    
/**
     * 快速排序。
     * 
@param arr 待排序数组
     * 
@param left 关注的区间
     * 
@param right 关注的区间
     
*/

    
private void sort(int[] arr, int left, int right) {
        
if (left >= right) {
            
return;
        }

        
// 取得pivot位置,这里的策略是取得最小的index,即返回left
        int pivot = findPivot(arr, left, right);
        
// 排序并重新计算出pivot
        pivot = partion(arr, left, right, pivot);

        
// 以pivot为中心将原数组分解成两块,递归排序
        sort(arr, left, pivot - 1);
        sort(arr, pivot 
+ 1, right);
    }


    
/**
     * 排序并返回新的pivot
     * 
@param arr 待排序数组
     * 
@param left 区间
     * 
@param right 区间
     * 
@param pivot 轴
     * 
@return 
     
*/

    
private int partion(int[] arr, int left, int right, int pivot) {
        
int tmp = arr[pivot];
        
int low = left;
        
int high = right;
        
while (low < high) {
            
// 从后向前遍历数组,找到第一个小于arr[pivot]的数
            while (low < high && tmp < arr[high]) {
                high
--;
            }

            arr[low] 
= arr[high];

            
// 从前向后遍历数组,找到第一个大于arr[pivot]的数
            while (low < high && tmp >= arr[low]) {
                low
++;
            }

            arr[high] 
= arr[low];
        }


        
// 此时low与high重合,将tmp的值移动到low的位置
        arr[low] = tmp;
        
// 将low当作新的pivot返回
        return low;
    }


    
/**
     * 取得排序的轴
     * 
@param array
     * 
@return
     
*/

    
protected int findPivot(int[] array, int left, int right) {
        
if (array == null || array.length < 0{
            
throw new RuntimeException("待排序数组中无数据。");
        }

        
// 选择第一个元素为轴
        return left;
    }

}

 


测试代码如下:

package com.bz.sort.algorithm;

import org.junit.Test;

import junit.framework.Assert;

public class QuickSortTest {
    @Test
    
public void testSort() {
        
int[] array = 42175386 };
        QuickSort qs 
= new QuickSort();
        qs.sort(array);
        
for (int i = 0; i < array.length - 1; i++{
            Assert.assertTrue(array[i] 
<= array[i + 1]);
        }

    }

}


注:此代码只为 演示 排序过程。
posted on 2011-04-09 17:37 李 明 阅读(2057) 评论(1)  编辑  收藏 所属分类: Java

评论

# re: 详细描述 快速排序 的过程 附Java实现 2016-03-17 14:07 哥哥
误人子弟啊!  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: