算法基础之快速排序

  算法一直是一块短板，今后会陆续写一些常用算法的实现，希望和大家一起探讨学习。
  快速排序是排序算法中最经典的一个，原理就不再赘述了，直接上代码。欢迎大家拍砖指导。

import java.util.Arrays;

/**
 * 快速排序
 * 
 * @author aaron-han
 * 
 */
public class QuickSort {

	public static void main(String[] args) {
		int[] arr = com.utils.Utils.randomIntArray();
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int low, int high) {
		if (low < high) {
			int mid = partition(arr, low, high);
			quickSort(arr, low, mid - 1);
			quickSort(arr, mid + 1, high);
		}
	}

	private static int partition(int[] arr, int low, int high) {
		int pivot = arr[low];
		int i = low;
		int j = high;
		while (i < j) {
			while (i < j && arr[j] >= pivot) {
				j--;
			}
			while (i < j && arr[i] <= pivot) {
				i++;
			}
			if (i < j) {
				swap(arr, i, j);
			}
		}
		swap(arr, low, j);
		return j;
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[j];
		arr[j] = arr[i];
		arr[i] = temp;
	}

}

评论

2 楼 rexyoung 2012-03-30  

不用多线程也能写出并发的 Quick Sort
http://www.cnblogs.com/rexyoung/archive/2012/03/29/2422955.html

1 楼 rexyoung 2012-03-21  

你的程序有一些小毛病，比如：

1，pivot 在 19 行是一个数组下标，但在 27 却是一个数组元素的值，很误导；
2，swap 在 partition 之外也调用了，这是我第一次看见这样写的 QuickSort；
3，36 行防止越界应该是 high 吧？
4，swap 不应该独立成为函数，一是太简单，二是多少增加了一些开销；
5，总是选第一个数组元素作为 pivot 这有问题。不是说不可以，但当数组本身就接近有序的话，每次 partition 就只能分出个别数组元素，成为了最坏的情况。其他选法也会有最坏的情况出现，但概率小多了。

这些都是小事，最糟糕的是这个程序是错的。你试试这个数组：{ 2, 1, 2, 2 }

原因是对 QuickSort 的精神没有吃透，特别是 pivot，要知道 pivot 可以选不在数组中出现的值。所以 41 行处，如果 arr[i] 和 arr[j] 的值都是 pivot 的话，swap 后又没有调整 i 和 j 的值，于是就死循环了。