数组排序之快速排序

        据大家所知的，快速排序是目前的一种非常快的排序方法，它是由C. A. R. Hoare在1962年提出。它的基本思想是：选择一个中间key值，作为分蘖点。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比key小，另外一部分的所有数据都要比key大，然后再递归调用按此方法对这两部分数据分别进行快速排序，以此达到整个数据变成有序序列。

      我们先来看一下具体的思路，再根据思路成型代码。

下面是我的程序运行结果截图：

 

        我选择key的方法是（0 + array.length）/2。

    因此，第一次选择“93”作为key所对应的值，第一次排序开始。比93小的四个数到了93的左边，比93大的两个数排到93的右边。

    现在整个数组被分成了三块：比93小、93，比93大。容易想到下面进行递归调用，分别对93前后两大块进行快速排序。此时的93已经到了自己正确的次序位子。这里会有两个递归调用，先左还是先右完全由读者自己定。这里我选择了先左后右。

     于是，第二次排序开始，到了93的左边四个数。选择68作为key对应的值。63,58相应的到了68左边，92到了68的右边。

     第三次排序时到了68的左边，选择第一个元素58作为key对应的值，显然不需要交换任何值。

     第四次排序时转到68的右边，因为只有92一个元素，不再需要排序。因此再继续向右走，来到93的右边。选择这一块中的第一个元素98作为key对应的值，将比98小的95移动到98的左边。

     到这里我们的快速排序结束。

     下面就到了代码部分。快速排序的代码有些技巧，需要我们格外的注意其中变量之间的关系和调用函数时的值传递问题。在上传的代码里我也会尽量多的添加注释，读者想要了解、理解、掌握快速排序，就还需要细细体会了。

package hhf.Sort_1012;

import java.util.Random;

/**
 * 快速排序
 * @author Administrator
 * 2012年11月25日
 */
public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//生成一个随机的数组，它有5~20随机的长度，随机的0~99的值
		Random random = new Random();
		int num = 5 + random.nextInt(16);
		int[] array = new int[num];
		for(int i = 0 ; i < num ; i++)
			array[i] = random.nextInt(100);
		System.out.println("一共有元素   " + num + "  个");
		//打印原来未排序数组
		System.out.println("未排序前");
		print(array);
		//开始排序
		System.out.println("排序中======>>>========>>>>>========>>>");
		quicksort(array,0,array.length - 1);
		//排序后再打印
		System.out.println("已排序后");
		print(array);
	}
	/**
	 * 快速排序的代码实现
	 * @param j 数组的末尾
	 * @param i 数组的起始
	 * @param array数组名
	 */
	private static void quicksort(int[] array, int i, int j) {
		//System.out.println("quicksort中i = " + i);
		//System.out.println("quicksort中j = " + j);
		//这是一个递归函数 首先判断是否递归调用截止(当当前块只有一个元素的时候就不需要再排序了)
		if(j <= i) 
			return;
		//得到一个关键码key
		int key = (j + i) / 2;
		//System.out.println("quicksort中key = " + key);
		//将关键码key与最后一个数array[length - 1]交换，可以使排序变得方便
		swap(array,key,j);
		//将前length-1个数进行分类 ——小于key的在前，大于key的在后，并返回大于key的那一块的第一个元素的地址k
		int k = sort(array,i-1,j,j);
		//System.out.println("quicksort中k = " + k);
		//交换k和key是key到达自己应该到的位置
		swap(array,k,j);
		//递归调用自己 现在已经将原数组分为了两块[0~ key-1]和[key+1 ~ length]因而就要调用两次
		print(array);//打印出来，看一下
		quicksort(array,i,k-1);
		quicksort(array,k+1,j);
	}
	/**
	 * 实现分类的函数，其结果是使得比key小的数放在前面 大于key的数放在后面
	 * @param array数组名
	 * @param i 数组起始的前一个位置
	 * @param j 数组结尾
	 * @param key 关键码
	 * @return大于key的数的第一个元素下标
	 */
	private static int sort(int[] array, int i, int j, int key) {
		//System.out.println("sort中i0 = " + i);
		//System.out.println("sort中j = " + j);
		do{
			//取到应该交换的i j值
			while(array[++i] < array[key]);
			while(j>0 && array[--j] >= array[key]);
			//交换array[i]和array[j]
			swap(array,i,j);
		}while(j>i);
		//因为最后会有一次多余的i,j交换，所以我们要再人为的交换回来
		swap(array,i,j);	
		//System.out.println("sort中i1 = " + i);
		//返回大于key0的第一个元素下标
		return i;
	}
	/**
	 * 交换array里面的array[i]和array[j]
	 * @param array
	 * @param i
	 * @param j
	 */
	private static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
/**
 * 打印数组
 * @param array数组名
 */
	private static void print(int[] array) {
		for(int i = 0 ;i < array.length ; i++)
			System.out.print(array[i]+"\t");
		System.out.println();			
	}

}


//double d = 5 + r.nextInt(5) + r.nextDouble();
//可以得到最小为5，最大为10的浮点数。
//解释：public int nextInt(int n)返回一个伪随机数，它是从此随机数生成器的序列中取出的、
//在 0（包括）和指定值（不包括）之间均匀分布的 int值。
//public double nextDouble()返回下一个伪随机数，
//它是从此随机数生成器的序列中取出的、在0.0d（包括）到 1.0d（包括）范围内均匀选择（大致）的 double 值。 

 

    代码不是很长，就只是有点复杂(⊙o⊙)，理解就好，理解就好。 在结尾的时候我外加了一点关于随机函数的使用技巧。

    最后呢，希望读者自己将代码写一遍，为了更好的掌握与体会。