本文为原创,欢迎转载,转载请注明出处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 = { 4, 2, 1, 7, 5, 3, 8, 6 };
QuickSort qs = new QuickSort();
qs.sort(array);
for (int i = 0; i < array.length - 1; i++) {
Assert.assertTrue(array[i] <= array[i + 1]);
}
}
}
注:此代码只为 演示 排序过程。