【排序算法】快速排序算法 Java实现

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

  1. 基本思想

    1. 先从数组中找出一个数作为基准数
    2. 分区过程,将比这个数小的数全部放到它的左边,大于它的数全部放到右边
    3. 再对左右区间重复第二步,直到各区间都只有一个数
  2. 排序过程

    一篇博客上看到一个很有趣的讲解方法:叫做 挖坑填数+分治法

    假如有一个10个数的数组:i=0,j=9,pivot=array[i]=x

    由于已经array[0]中的数保存到pivot中,可以理解成在数组array[0]上挖了个坑,可以将其他数据填充到这里来。

    然后j向前找比当前基准数pivot小的数,当符合条件时(比如是第8个参数),那么将array[8]挖出填充到array[0]这个坑。这时就多出了array[8]这个坑,于是从i开始向后找大于pivot的数,填充array[8]这个坑。

    重复操作。

    最后i==j时会退出循环,这时多出了array[i]这个坑,怎么办呢?将pivot填充到array[i]。这时对左右两个区间继续进行排序就好了。

  3. 算法实现

    /**
* 快速排序
*/
public class QuickSort {
public void sort(int[] array) {
quickSort(array, 0, array.length - 1);
} /**
* 通过划分,基于分治思想,递归执行子任务排序最后合并
* @param low 数组首位索引
* @param high 数组末尾索引
*/
private void quickSort(int[] array, int low, int high) {
int pivotPos;
if (low < high) {
pivotPos = partition(array, low, high);
quickSort(array, low, pivotPos - 1);
quickSort(array, pivotPos + 1, high);
}
} /**
* 简单划分方法
*/
private int partition(int[] array, int i, int j) {
int pivot = array[i]; // array[i] 就是 第一个坑 while (i < j) {
while (i < j && array[j] >= pivot) {
j--; // 从右向左找出小于基准数pivot的数来填充array[i]
} if (i < j) {
array[i] = array[j]; // 将array[j]填充到array[i]中,array[j]就形成了一个新的坑
i++;
} while (i < j && array[i] <= pivot) {
i++; // 从左向右找出大于基准数pivot的数来填充array[j]
} if (i < j) {
array[j] = array[i]; // 将array[i]填充到array[j]中,array[i]就形成了一个新的坑
j--;
}
} array[i] = pivot; // 退出时,i等于j。将pivot填到这个坑中。
return i;
}
}

参考文章:

1. http://blog.csdn.net/morewindows/article/details/6684558

2. http://shiyanjun.cn/archives/800.html

上一篇:HDU 2.1.7 (求定积分公式)


下一篇:java操作excel常用的两种方式