快速排序（2个版本）

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序，是对冒泡排序的改进。平均情况下快速排序的时间复杂度为O(nlogn)，虽然最坏情况时会达到O(n2)，但在大多数情况下，快速排序要比其它O(nlogn)算法要快，被认为是目前最优秀的内部排序算法。快速排序是不稳定的。它采用分治法(Divide　and　Conquer)的策略，把一个串行（list）分为两个子串行（sub-lists）。

步骤为：

• 从数列中挑出一个元素，称为 "基准"（pivot）；
• 分区（partition）：将所有小于基准值的元素放在基准前面，所有大于基准值的元素放在基准的后面（相同的数可以到任一边）。分区结束之后，该基准就处于数列的中间位置；
• 分别对小于基准值元素的子数列和大于基准值元素的子数列进行递归排序。

递归的最底部情形，是数列的大小是零或一，在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

 

１.快速排序算法一

这是在多数的教科书上所提及的版本，容易理解，选第一个元素为基准，*表示要交换的数，一趟排序的过程如下：

 

[41]　24　76*　11　45　64　21　69　19　36* 　

[41]　24　36　11　45*　64　21　69　19*　76

[41]　24　36　11　19　64*　21*　69　45　76

[41]　24　36　11　19　21　64　69　45　76

21　24　36　11　19　[41]　64　69　45　76

 

代码实现：

 

public class QuickSort {
	public static void sort(int[] number) {
		sort(number, 0, number.length - 1);
	}
	
	public static void sort(int[] number, int left, int right) {
		if(left < right) {
			int s = number[left];
			int i = left;
			int j = right + 1;
			while(true) {
				while(i + 1 < number.length && number[++i] < s);//向右找
				while(j - 1 > -1 && number[--j] > s);           //向左找
				if(i >= j)
					break;
				swap(number, i, j);
			}
			number[left] = number[j];
			number[j] = s;
			sort(number, left, j -1);   //对左边进行递归
			sort(number, j + 1, right); //对右边进行递归
		}
	}
	
	public static void swap(int[] number, int i, int j) {
		int t = number[i];
		number[i] = number[j];
		number[j] = t;
		
	}
	
	public static void main(String[] args) {
		int[] number = {49,38,65,97,76,13,27,49};
		sort(number);
		for(int i = 0; i < number.length; i++) {
			System.out.print(number[i] + " ");
		}
	}
}

 

２.快速排序算法二

基准的选择是快速排序法的效率关键之一，下面介绍的快速排序算法来自算法名著 Introduction to Algorithms，算法基本思想如下：

• 它以最右边的值s作比较的标准，将整个数列分为三个部份，一个是小于s的部份，一个是大于s的部份，一个是未处理的部份，如下所示 ：

• 在排序的过程中，i 与 j 都会不断的往右进行比较与交换，最后数列会变为以下的状态：

 

 

• 然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：

 

一个实际例子的演算如下所示：

 

代码实现：

public class QuickSort {
	public static void sort(int[] number) {
		sort(number, 0, number.length - 1);
	}
	
	public static void sort(int[] number, int left, int right) {
		if(left <= right) {
			int q = partition(number, left, right);
			sort(number, left, q - 1);
			sort(number, q + 1, right);
		}
	}
	
	public static int partition(int[] number, int left, int right) {
		int s = number[right];
		int i = left - 1;
		for(int j = left; j < right; j++) {
			if(number[j] < s) {
				i++;
				swap(number, i, j);
			}
		}
		swap(number, i + 1, right);
		return i + 1;
	}
	
	public static void swap(int[] number, int i, int j) {
		int t = number[j];
		number[j] = number[i];
		number[i] = t;
	}
	
	public static void main(String[] args) {
		int[] number = {49,38,65,97,76,13,27,49};
		sort(number);
		for(int i = 0; i < number.length; i++) {
			System.out.print(number[i] + " ");
		}
	}
}