（高效率排序算法二）快速排序

浏览数：18 / 时间：2015年06月08日

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设用户输入了如下数组：

下标	0	1	2	3	4	5
数据	6	2	7	3	8	9

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：

下标	0	1	2	3	4	5
数据	3	2	7	6	8	9

i=0 j=3 k=6

接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据做交换，数据状态变成下表：

下标	0	1	2	3	4	5
数据	3	2	6	7	8	9

i=2 j=3 k=6

称上面两次比较为一个循环。

接着，再递减变量j，不断重复进行上面的循环比较。

在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：

下标	0	1	2	3	4	5
数据	3	2	6	7	8	9

如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
流程图
技术分享

java代码实现，并与java自带快速排序2000万随机数排序做了比较

package data;

import java.util.Arrays;
import java.util.Random;
/**
 * 快速排序算法
 * @author JYC506
 *
 */
public class QuickSort {

	private static void sort(int[] arr,int left,int right) {
		/*低位置起始点*/
		int low = left;
		/*高位置起始点*/
		int hight = right;
		/*要比较的数据为低位置起始点的值*/
		int data = arr[low];
		while (low < hight) {
			while(low < hight&&arr[hight] >=data){
				hight--;
			}
			/*把比它小的放左边,因为low最终为data*/
			if (low<hight) {
				 arr[low]=arr[hight];
				/*因为我跟你比较过了所以下次不比较了,加一*/
				low++;
			}
			while(low < hight&&arr[low]<= data){
				low++;
			}
			/*把比它大的放右边*/
			if (low<hight) {
				arr[hight] = arr[low];
				/*因为我跟你比较过了所以下次不比较了,减一*/
				hight--;
			}
		}
		/*注意下标为low最终为data*/
		arr[low]=data;
		/*因为在data右边都比data大,所以现有data的右边在下一次排序时候不需要再排了*/
		if(low>left){
			sort(arr,left,hight-1);
		}
		/*因为在data左边都比data小,所以现有data的左边边在下一次排序时候不需要再排了*/
		if(hight<right){
			sort(arr,low+1,right);
		}
	}
	
	public static void sort(int[] arr){
		sort(arr,0,arr.length-1);
	}
	public static void main(String[] args) {
		int[] arr=new int[]{6,2,7,3,8,9};
		System.out.println("快速排序前："+Arrays.toString(arr));
		QuickSort.sort(arr);
		System.out.println("快速排序后："+Arrays.toString(arr));
		int num=10000000;
		Random ran=new Random();
	    int[] arr1=new int[num];
	    int[] arr2=new int[num];
		for(int i=0;i<num;i++){
			int data=ran.nextInt(num);
			arr1[i]=data;
			arr2[i]=data;
		}
		long start=System.currentTimeMillis();
		QuickSort.sort(arr1);
		long end=System.currentTimeMillis();
		Arrays.sort(arr2);
		long end2=System.currentTimeMillis();
		System.out.println("我自己写快速排序算法1000万随机数排序耗时："+(end-start)+"毫秒");
		System.out.println("jdk自带的快速排序算法1000万随机数排序耗时："+(end2-end)+"毫秒");
	}

}

输出结果