快速排序不会写?很简单,其实就是一种优化后的冒泡排序。

思路

快速排序讲的是一种分而治之的策略。

  1. 首先,在要排序的列表中,找一个项,比如第一项或者最后一项。

这里可以用到随机数,而且可以提高效率

  1. 然后把要排序的列表分成两个部分,一部分是比这个项小的,都给他撇到当前项的左边去;一部分是比这个项大的,都给放到当前项的右边去。

这样操作一次之后,你会发现列表分成了三部分,比它小的,它自己和比他大的。

  1. 然后继续对它左边列表和右边的列表继续进行1、2两个步骤,相应的范围变成左右两侧列表。没错,就是递归。

直到当前需要进行排序的子列表只有一个元素的时候,则停止递归。

实现

直接上代码QuickSort.java

public void sort(ArrayList<Integer> array) {
	if (null != array && array.size() > 0) {
		sort(array, 0, array.size() - 1);
	}
}

// quick sort
public void sort(ArrayList<Integer> array, int start, int end) {
	if (null == array || array.size() <= 0) {
		return;
	}
	if (end - start <= 0) {
		return;
	}
	int index = random(start, end);
//		int index = start;
	index = splitList(array, start, end, index);
	if (index == -1 || index < start || index > end) {
	} else {
		sort(array, start, index - 1);
		sort(array, index + 1, end);
	}
}

/**
 * 把列表以index的值作区分,小的放到start位置,大的全部放到index项后,同时index可能会一直变化,最后返回index
 *
 * @param array
 * @param start
 * @param end
 * @param index
 * @return
 */
private int splitList(ArrayList<Integer> array, int start, int end, int index) {
	for (int i = start; i <= end; i++) {
		if (array.get(i) > array.get(index)) {
			if (i < index) {
				swap(array, i, index);
				index = i;
			}
		} else {
			if (array.get(index).intValue() != array.get(i).intValue()) {
				int tmp = array.remove(i);
				array.add(start, tmp);
				if (i > index) {
					index++;
				}
			}
		}
	}
	return index;
}

/**
 * 数据项交换位置
 *
 * @param array
 * @param first
 * @param second
 */
private void swap(ArrayList<Integer> array, int first, int second) {
	int len = array.size();
	if (first >= 0 && first < len && second >= 0 && second < len) {
		int tmp = array.get(first);
		array.set(first, array.get(second));
		array.set(second, tmp);
	}
}

/**
 * 范围内随机,范围必须大于0
 *
 * @param min
 * @param max
 * @return
 */
private int random(int min, int max) {
	if (max <= 0) {
		return 0;
	}
	if (min <= 0) {
		min = 1;
	}
	int result = random.nextInt(max) % (max - min + 1) + min;
	return result;
}

排序整个列表直接调用sort(ArrayList<Integer> array),如果需要对列表中特定区域排序,可以用sort(ArrayList<Integer> array, int start, int end),注意这里面的两侧区间都是闭合的,也就是说end位置的项也会被排序。

其实再要扩展的话,可以泛型化,新增一个比较接口实现具体对比操作。

实测

调用如下代码实测10000条随即整数排序:

public static void main(String... args) {
	ArrayList<Integer> array = new ArrayList<Integer>();
	int size = 10000;
	for (int i = 1; i < size; i++) {
		array.add(random.nextInt(size) * random.nextInt(i) - random.nextInt(size));
	}
	System.out.println(array.toString());
	QuickSort quickSort = new QuickSort();
	long start = System.currentTimeMillis();
	// quickSort.sort(array, 5, 14);
	quickSort.sort(array);
	System.out.println("final cost " + (System.currentTimeMillis() - start) + " ms");
	System.out.println(array.toString());
}

输出:

final cost 166 ms

看起来好像是挺快的,不过设备是13年mbp。