並べ替えアルゴリズム(4)--クイックソート

package sort;

import java.util.Arrays;
import java.util.Random;

/**
 *     
 *    ：N^2
 *   ：1.        key,     key       ，  key        
 *       2. key                ，    1     ，  ，          
 *     ：
 *       1.      t[i]    key，       ,i=0     
 *       
 *       2.        j = t.length -1   key    ，     ( )    ，  i<j
 *         2.1   t[j] >= key,          （      ( ) ），    , j--.
 *         2.2   t[j] <  key, t[i]           t[j],t[i] = t[j].    i ++.
 *         
 *       3.      t[i], key    ，     （ ）    ，  i<j
 *         3.1   t[i] <= key,          ，     ,i++
 *         3.2   t[i] > key,        ，t[j] = t[i],   j--;
 * 
 *         ：2 3         ，      ，i++,j--,     ，      
 *       4. i<j    ，  2 3  ，   i = j.
 *       5.         ，    ，    ，key      i      
 *           i      ，               ，    ，    
 *        ：   a b c d e f g 7   。 a   ，  key      
 *      1. g       ，     a    ， a      。      f  a  ，
 *            f  a       。(a      f    )
 *           ：g b c d e (a) g
 *      2.       ，  g   a   ，   b     。      a   。
 *          c   a  ，  c      a      。
 *           :g b (a)  d e c g
 *      3.        ，         。      
 * @author @Ran
 * 
 */
public class Quick<T> extends AbstractSort<T> {

	/**
	 *      ，       t[i]                      t[i],
	 *          t[i]
	 */
	public <T extends Comparable<? super T>> int dichotomieSwap(T[] t, int i,int j) {
		T key = t[i];
		//          
		while (i < j) {
			//        ,         key,     ，      key                        //      
			while (i < j && t[j].compareTo(key) >= 0) {
				j--;
			}
			//       key     ，   
			if (i < j) {
				setValue(t, i, j);
				i++;
			}
			while (i < j && t[i].compareTo(key) <= 0) {
				//       ，            key,    ，                                  //     key     
				i++;
			}
			if (i < j) {
				setValue(t, j, i);
				j--;
			}
		}
		setValue(t, i, key);
		//               
		return i;
	}
	
    //     
	public <T extends Comparable<? super T>> T[] swap(T[] t, int i, int j) {
		if (i < j) {
			//   
			int mid = dichotomieSwap(t, i, j);
			//           
			swap(t, i, mid - 1);
			//   ，      
			swap(t, mid + 1, j);
		}
		return t;
	}

	//     
	public <T extends Comparable<? super T>> T[] sort(T[] t) {
		return swap(t, 0, t.length - 1);
	}

	public static void main(String[] args) {
		int a = 30000;
		Integer[] t = new Integer[a];
		Random r = new Random();
		for (int i = 0; i < a; i++) {
			t[i] = r.nextInt(a);
		}
		Integer[] t2 = t.clone();
		System.out.println("     ：" + Arrays.toString(t));
		//              
		Sort s1 = new Quick();
		Sort s2 = new Insertion();
		s1.sort(s1, t);
		s2.sort(s2, t2);
		System.out.println("     ：" + Arrays.toString(t));
		System.out.println(s1);
		System.out.println(s2);
	}

}

 
 
凡例参考：http://blog.csdn.net/wxwzy738/article/details/7832737
結び：この計算アルゴリズムは多くの改善点があり、また各種の効率的な状況が違っています。
          個人は小さいデータに対して意味がないと思っています。大量のデータで効果が分かります。データによって違う順序で並べ替えられます。