ソートアルゴリズムの思想とJavaの実現

import java.util.Arrays;

/**
 *@author 255166
 *@version Feb 27, 2012 10:39:00 AM
 */
public class SortAlgorithm {

	/**
	 *     i，j       
	 * @param inputArray
	 * @param i
	 * @param j
	 * @return
	 */
	public static int[] exchangeValue(int[] inputArray, int i, int j) {
		int temp = inputArray[i];
		inputArray[i] = inputArray[j];
		inputArray[j] = temp;
		return inputArray;
	}

	/**
	 *     
	 *     （BubbleSort）      ：          ，       ，      。     ：     1   2  ，
	 *      ，    。     2    3  ，     ，    ，    ，         ，     ，    。
	 *        ，          。    ：          （       2    3     ，   1       2  ），
	 *      ，    ，           （              ），     ，                  （              ）。
	 *     ，      ，        。 
	 * @param inputArray
	 * @return
	 */
	public static int[] BubbleSort(int[] inputArray) {
		for (int i = 0; i < inputArray.length; i++) {

			for (int j = 0; j < inputArray.length - i - 1; j++) {
				if (inputArray[j] > inputArray[j + 1]) {
					exchangeValue(inputArray, j, j + 1);
				}
			}
		}
		return inputArray;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] sortInt = { 8, 5, 12, 1, 22, 2, 99, 6, 3, 7, 100, 4, 44, 9 ,88};
		//BubbleSort(sortInt);
		//quickSort(sortInt, 0, sortInt.length - 1);
		//selectionSort(sortInt);
		//insertSort(sortInt);
		shellSort(sortInt);
		System.out.println("Sort ASC:" + Arrays.toString(sortInt));
	}
	
	/**
	 *     
	 *     ：
　        *       n   d1       ，          d1  。     dl             。
	 *              ；  ，      d2<d1          ，       dt=1(dt<dt-l<…<d2<d1)，
	 *                      。
	 * @param inputArray
	 */
	public static void shellSort(int[] inputArray){
		//       
		for(int increment=inputArray.length/2;increment>0;increment/=2){
			//              
			for(int i=increment;i<inputArray.length;i++){
				int temp=inputArray[i];
				int j=0;
				for(j=i;j>=increment;j-=increment){
					if(temp<inputArray[j-increment]){
						inputArray[j]=inputArray[j-increment];
					}else{
						break;
					}
				}
				inputArray[j]=temp;
			}
		}
	}
	
	/**
	 *     
	 *  n                  ， 
　　   * {，{a2，a3，a4，…,an}}
　　   * {{a1(1)，a2(1)}，{a3(1)，a4(1) …,an(1)}}
　　   * …
　　   * {{a1(n-1)，a2(n-1) ，…}, {an(n-1)}}
　　   *                                    ，      ，                 。
	 * @param inputArray
	 * @return
	 */
	public static int[] insertSort(int[] inputArray){
		
		for (int i = 1; i < inputArray.length; i++) {// i    ，                
			   //                             
			   for (int j = i; j > 0; j--) {  
			    if (inputArray[j] < inputArray[j - 1]) {  
			     int temp = inputArray[j];  
			     inputArray[j] = inputArray[j - 1];  
			     inputArray[j - 1] = temp;  
			    }  
			   }  
			  }  
		return inputArray;
	}
	
	/**
	 *     
	 * n                n-1             ：
　　   * ①    ：    R[1..n]，     。
　	 * ② 1   
　　    *     R[1..n]           R[k]，        1   R[1]  ， R[1..1] R[2..n]          1             1      。
　　    * ……
　　    * ③ i   
　　    *  i      ，            R[1..i-1] R(1≤i≤n-1)。                      R[k]，        1   R  ，
	 *	 R[1..i] R          1             1      。
　　    *   ，n                n-1             。 
	 * @param inputArray
	 * @return
	 */
	public static int[] selectionSort(int[] inputArray){
		
		for(int i=0;i<inputArray.length;i++){
			int initialIndex=i;
			int initialValue=inputArray[i];
			for(int j=i+1;j<inputArray.length;j++){
				if(inputArray[j]<initialValue){
					initialIndex=j;
					initialValue=inputArray[j];
				}
			}
			int temp=inputArray[i];
			inputArray[i]=initialValue;
			inputArray[initialIndex]=temp;
		}
		
		return inputArray;
	}

	/**
	 *     
	 *           ：
　　   * 1）      I、J，       ：I=0，J=N-1；
　　   * 2）              ，   key，  key=A[0]；
　　  * 3） J      ，         （J=J-1），       key  A[J]，A[j] A[i]  ；
　　  * 4） I      ，         （I=I+1），       key A[I]，A[i] A[j]  ；
　　  * 5）   3、4、5 ，   I=J； (3,4           j=j-1，i=i+1，      。        i， j      。   i=j        i+ j-          。）
　　  *   ：      A     ：（      ：key=49）     key    ，    key    ，       ，        X    ，          。
　　 * A[0] A[1] A[2] A[3] A[4] A[5] A[6]：
	*　49 38 65 97 76 13 27
	*　        ：27 38 65 97 76 13 49
	*　(               ）
	*　        ：27 38 49 97 76 13 65
	*　(               >X  ，65>49,    ，  ：I=3 )
	*　        ：27 38 13 97 76 49 65
	*　(                          
	*　        ：27 38 13 49 76 97 65
	*　(                 X  ，97>49，    ，  ：I=4,J=6 )
	*　              I=J，          ，                ：27 38 13 49 76 97 65，     49     49   ，    49     49   。
	 * @param inputArray
	 * @param left
	 * @param right
	 * @return
	 */
	public static int[] quickSort(int[] inputArray, int left, int right) {
		int middleValue = inputArray[left];
		int i = left;
		int j = right;
		//     
		while (i < j) {
			if (left < right) {
				while (i < j && inputArray[j] > middleValue) {
					j--;
				}
				if (i < j) {
					int temp = inputArray[i];
					inputArray[i] = inputArray[j];
					inputArray[j] = temp;
				}
			}
			if (left < right) {
				while (i < j && inputArray[i] < middleValue) {
					i++;
				}
				if (i < j) {
					int temp = inputArray[i];
					inputArray[i] = inputArray[j];
					inputArray[j] = temp;
				}
			}
		}
		//       
		if(left<j){
			quickSort(inputArray, left, i - 1);
		}  
		//       
		 if(right>i){
			 quickSort(inputArray, i + 1, right);
		 }
		return inputArray;
	}

}