【快速排序法】

【快速排序法】
也是一种交换排序法，实际上它是冒泡法的改进。

【算法】
思想是：一次划分使整个元素部分有序，即从序列中任选一个元素，然后对其它元素进行这样的划分，使得所有比它小（大）的元素在左侧而所有比它大（小）的元素在右侧，然后用分治的思想对左右侧的序列同样的处理，直到只有一个元素为止。

 

 

/**
 * 
 */
package com.dianzi.arith;

/**
 * 快速排序，整个过程用递归算法设计，思想是分治的思想
 * @author 点子二木
 * @date 2009-5-12
 * @version 1.0
 */
public class Quick {
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int list_length = 10;
		InitList list = new InitList(list_length);
		Quick quick = new Quick();

		int[] tempArray = list.toArrayInt();

		int[] resultArray = quick.quicksort(tempArray, 0, list_length - 1);

		System.out.println("");
		System.out.print("快速排序：");
		for (int i = 0; i < resultArray.length; i++) {
			System.out.print(resultArray[i] + " ");
		}

	}

	/**
	 * 整个快速排序的过程用递归算法设计，思想当然是分治的思想：
	 * 
	 * @param tempArray
	 * @param low
	 * @param high
	 * @return
	 */
	public int[] quicksort(int[] tempArray, int low, int high) {
		// 对r[low]，r[low+1],...r[high]进行快速排序
		if (low < high) {
			int k;
			k = quickpass(tempArray, low, high);// 一次划分
			quicksort(tempArray, low, k - 1);// 对左侧元素以同样的方法对待
			quicksort(tempArray, k + 1, high);// 对右侧元素以同样的方法对待
		}
		return tempArray;
	}

	/**
	 * 一次划分的算法如下：
	 * 
	 * @param tempArray
	 * @param low
	 * @param high
	 * @return
	 */
	public int quickpass(int[] tempArray, int low, int high) {
		int i = low, j = high, x = tempArray[i]; // 置初值，i指最左端，j指最右端，选第i个元素为划分比较元素x
		while (i < j) {
			while ((tempArray[j] >= x) && (i < j))
				--j;
			// 自尾端进行比较，因为i处为空
			if (i < j) {
				tempArray[i] = tempArray[j];
				i++;// 填入i处
				while (tempArray[i] <= x && (i < j)) {
					++i;
				}
				// 自首端进行比较，j处已空
				if (i < j) {
					tempArray[j] = tempArray[i];
					j--;
				}
			}
		}
		tempArray[i] = x;// 一趟快速排序结束，将x移至正确位置
		return i;// 返回划分比较元素的位置
	}

}

 

 

初始化数组：

/**
 * 
 */
package com.dianzi.arith;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 初始化数组
 * @author 点子二木
 * @date 2009-5-12
 * @version 1.0
 */
public class InitList {
	private static int INIT_LIST_LENGTH = 1;
	public  List global_List = null;

	public InitList(int length) {
		initIntArrayList_falseRandom(length);
		//initIntArrayList(length);
		printList();
	}
	
	/**
	 * 产生伪随机列表
	 * @param length
	 */
	public void initIntArrayList_falseRandom(int length) {
		global_List = new ArrayList(length);
		INIT_LIST_LENGTH = length;
		Random rd = new Random(20);
		for (int i = 0; i < length; i++) {
			int newNum =  rd.nextInt(100);
			global_List.add(newNum);
			//System.out.print(newNum + " ");
		}

	}
	

	/**
	 * 产生随机列表
	 * @param length
	 */
	public void initIntArrayList(int length) {
		global_List = new ArrayList(length);
		INIT_LIST_LENGTH = length;
		
		for (int i = 0; i < length; i++) {
			Integer newNum = Integer.valueOf((int) (Math.random() * 100)) ;
			global_List.add(newNum);
			//System.out.print(newNum + " ");
		}

	}

	public void printList() {
		if (global_List != null) {
			System.out.println("");
			System.out.print("打印列表：");
			for (int i = 0; i < global_List.size(); i++) {
				System.out.print(global_List.get(i) + " ");
			}
		}

	}
	
	public int[] toArrayInt() {
		int[] result = new int[INIT_LIST_LENGTH];
		if (global_List != null) {
			for (int i = 0; i < global_List.size(); i++) {
				result[i] = (Integer) global_List.get(i);
			}
		}
		return result;
	}

}