Javaソートアルゴリズムの高速ソート

高速ソートは、分割法(Divide and conquer)ポリシーを使用して、1つのシリアル(list)を2つのサブシリアル(sub-lists)に分割します.
手順は次のとおりです.
数列から「基準」(pivot)と呼ばれる要素を選択し、
数列を並べ替え、すべての要素が基準値より小さいものは基準の前に配置され、すべての要素が基準値より大きいものは基準の後ろに配置されます(同じ数は任意の側に配置できます).このパーティションが終了すると、基準は数列の中間位置にあります.これをパーティション操作と呼ぶ.
再帰的に(recursive)基準値要素より小さいサブ数列と基準値要素より大きいサブ数列を並べ替える.
再帰の最も下部の状況は、数列のサイズがゼロまたは1であり、つまり永遠にソートされていることです.ずっと再帰していますが、このアルゴリズムは常に終了します.毎回の反復(iteration)では、少なくとも1つの要素を最後の位置に配置するからです.
この方法の白話の基本思想は:
1.まず、数列から1つの数を基準数として取り出します.
2.パーティション化プロセスでは、この数より大きい数を右に、それより小さい数または等しい数を左にすべて配置します.
3.各区間が1つになるまで、左右の区間について2番目のステップを繰り返す.
次のコードはウィキペディアから
http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

package com.fit.quick.sort;

import java.util.Comparator;
import java.util.Random;

public class QuickSort {

	public static final Random RND = new Random();

	private static void swap(Object[] array, int i, int j) {
		Object tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	private static <E> int partition(E[] array, int begin, int end,
			Comparator<? super E> cmp) {
		int index = begin + RND.nextInt(end - begin + 1);
		E pivot = array[index];
		swap(array, index, end);
		for (int i = index = begin; i < end; ++i) {
			if (cmp.compare(array[i], pivot) <= 0) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		return (index);
	}

	private static <E> void qsort(E[] array, int begin, int end,
			Comparator<? super E> cmp) {
		if (end > begin) {
			int index = partition(array, begin, end, cmp);
			qsort(array, begin, index - 1, cmp);
			qsort(array, index + 1, end, cmp);
		}
	}

	public static <E> void sort(E[] array, Comparator<? super E> cmp) {
		qsort(array, 0, array.length - 1, cmp);
	}

	public static void print(Integer[] array) {
		StringBuffer sb = new StringBuffer("[");
		for (int i = 0; i < array.length; i++) {
			if (i < array.length - 1) {
				sb.append(array[i]).append(",");
			} else {
				sb.append(array[i]);
			}
		}

		sb.append("]");

		System.out.println(sb);
	}

	public static void main(String[] args) {
		
		Integer[] array = new Integer[] { 54, 3, 11, 34, 12, 8, 19 };

		print(array);

		System.out.println("=====================");

		sort(array, new Comparator<Object>() {

			@Override
			public int compare(Object o1, Object o2) {
				//return o1.compareTo(o2);
				if(o1 instanceof Integer && o2 instanceof Integer)
				{
					Integer temp_o1 = (Integer)o1;
					Integer temp_o2 = (Integer)o2;
					return temp_o1.compareTo(temp_o2);
				}
				 return 0;
			}
		});

		print(array);
	}
}

上記のコードを例に挙げて説明します.

package com.fit.quick.sort;

import java.util.Random;

public class GeneralQuickSort {

	public static final Random RND = new Random();

	public static void sort(int[] array) {
		qsort(array, 0, array.length - 1);
	}

	public static void qsort(int[] array, int begin, int end) {
		if (begin < end) {
			int index = partition(array, begin, end);
			qsort(array, begin, index - 1);
			qsort(array, begin + 1, end);
		}
	}

	private static int partition(int[] array, int begin, int end) {
		int index = begin + RND.nextInt(end - begin + 1);
		int pivot = array[index];
		swap(array, index, end);
		for (int i = index = begin; i < end; ++i) {
			if (array[i] < pivot) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		// System.out.println("----"+array[index]+"----");
		// print(array);
		return index;
	}

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

	public static void print(int[] array) {
		StringBuffer sb = new StringBuffer("[");
		for (int i = 0; i < array.length; i++) {
			if (i < array.length - 1) {
				sb.append(array[i]).append(",");
			} else {
				sb.append(array[i]);
			}
		}

		sb.append("]");

		System.out.println(sb);
	}

	public static void main(String[] args) {

		int[] array = new int[] { 54, 3, 11, 34, 12, 8, 19 };

		print(array);

		System.out.println("=====================");

		sort(array);

		print(array);
	}
}

もう一人の仁兄がくれた巧みな解答は、白話でその思想を描き、はっきりしていて、分かりやすく、作者は待ちきれずに回ってきた.

package com.fit.quick.sort;

public class CopyOfGeneralQuickSort {

	public static void print(int[] array) {
		StringBuffer sb = new StringBuffer("[");
		for (int i = 0; i < array.length; i++) {
			if (i < array.length - 1) {
				sb.append(array[i]).append(",");
			} else {
				sb.append(array[i]);
			}
		}

		sb.append("]");

		System.out.println(sb);
	}

	public static void sort1(int[] array) {
		quickSort1(array, 0, array.length - 1);
	}

	/**
	 *          1．i =L; j = R;             a[i]。
	 * 2．j--          ，            a[i] 。 3．i++          ，              a[j] 。
	 * 4．     2，3  ，  i==j，      a[i] 。                   ：
	 * 
	 * @param s
	 * @param l
	 * @param r
	 * @return
	 */
	public static int partition1(int[] s, int l, int r) {
		int x = s[l];// s[l] s[i]      
		int i = l;
		int j = r;

		while (i < j) {

			//        x    s[i]
			while (i < j && s[j] >= x) {
				j--;
			}
			if (i < j) {
				s[i] = s[j]; //  s[j]  s[i] ，s[j]         
				i++;
			}

			//           x    s[j]
			while (i < j && s[i] < x) {
				i++;
			}
			if (i < j) {
				s[j] = s[i]; //  s[i]  s[j] ，s[i]         
				j--;
			}

			s[i] = x;
		}

		return i;
	}

	public static void quickSort1(int[] array, int l, int r) {
		if (l < r) {
			int index = partition1(array, l, r);
			quickSort1(array, l, index - 1);
			quickSort1(array, index + 1, r);
		}
	}

	public static void main(String[] args) {

		int[] array = new int[] { 54, 3, 11, 34, 12, 8, 19 };

		print(array);

		System.out.println("=====================");

		sort1(array);

		print(array);
	}
}

上記のコードのソース:http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html