단순 알고리즘 9 가지 정렬 (1)

package com.css.java.learning.massbag;
import java.util.Arrays;
/**  ：
 *       
 * @author Red_ant
 * 20181119
 */
public class OrderMethod {
    /*1、    
     *              ，           
     *     i 。
     */
    public static int[] bubbleSort(int[] nums){
        int num = 0;
        for (int i = 0; i < nums.length -1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {//    ，           
                if(nums[j] > nums[j + 1]){
                    num = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = num;
                }
            }
        }
        return nums;
    }
    /*2、    
     *         ，                  ，         ，
     *       ，    。
     */
    public static int[] selectSort(int[] nums){
        int num = 0;
        for (int i = 0; i < nums.length -1; i++) {
            int index = i;
            for (int j = i + 1; j < nums.length; j++) {//       ，        i 
                if(nums[index] > nums[j]){
                    index = j;
                }
                if(index != i){
                    num = nums[i];
                    nums[i] = nums[index];
                    nums[index] = num;
                }
            }
        }
        return nums;
    }
    /*3、    ：   
     *               
     *          ，   ，              。            ：
     *    ***  ，    ***         
     *     ：
     *         ，               
     *             ，           
     *       ，       ，                 ，      +    ，        。
     */
    public static int[] HeapSorts(int[] nums){
        //    
        for (int i = nums.length/2 - 1; i >= 0; i--) {
            //             ，        
            suitHeap(nums, i, nums.length);
        }
        //     ，            
        for (int j = nums.length - 1; j > 0; j--) {
            exchangeNum(nums, 0, j);//           
            suitHeap(nums, 0, j);
        }
        return nums;
    }

    private static void exchangeNum(int[] nums, int i, int i2) {
        int index = nums[i];
        nums[i] = nums[i2];
        nums[i2] = index;
    }
    private static void suitHeap(int[] nums, int i, int length) {
        int index = nums[i];//      
        for (int j = i*2 + 1; j < length; j = j*2+1) {
            // i        ， 2i+1 
            if(j+1 < length && nums[j] < nums[j+1]){
                //  ，          ，j      
                j++;
            }
            if(nums[j] > index){
                //          ，          
                nums[i] = nums[j];
                i = j;
            }else{
                break;
            }
        }
        nums[i] = index;// index       
    }

    /*4、java Arrays  
     *     Arrays      ，           ，    
     */
    public static int[] ArraySort(int[] nums){
        Arrays.sort(nums);
        return nums;
    }
    /*5、    ：      
     *         ，                
     *               
     */
    public static int[] insertSort(int[] nums){
        //              ，                     
        for (int i = 1; i < nums.length; i++) {
            int j;
            int index = nums[i];//index       
            for (j = i; j > 0 && index < nums[j - 1]; j--) {
                nums[j] = nums[j -1];
            }
            nums[j] = index;
        }
        return nums;
    }

    /*6、    ：    
     *   ，               
     *             ，      n          ，          。
     *      d1             ，             。               。
     */
    public static int[] shellSrot(int[] nums){
        int index = nums.length/2;
        while (index >= 1) {
            for (int i = index; i < nums.length; i++) {
                if(nums[i] < nums[i - index]){
                    int j;
                    int x = nums[i];//        
                    nums[i] = nums[i - index];
                    for (j = i - index; j >= 0 && x < nums[j]; j = j-index) {
                        nums[j + index] = nums[j];
                    }
                    nums[j + index] = x;//    
                }
            }
            index = index/2;
        }
        return nums;
    }
    /*7、    ：    
     *     ：
     * A        ，                
     * B                      ：           ，          
     * C               
     * D         ，            ，        。
     */
    public static int[] quickSort(int[] nums, int...is){
        int low,hight;
        if(is.length == 0){
            low = 0;
            hight = nums.length - 1;
        }else{
            low = is[0];
            hight = is[1];
        }
        if(low < hight){//  ，       ，      
            int middle = getMiddle(nums, low, hight);
            quickSort(nums, 0, middle - 1);//     
            quickSort(nums, middle + 1, hight);//      
        }
        return nums;
    }
    //  ，  
    private static int getMiddle(int[] nums, int low, int hight) {
        int index = nums[low];//      
        while (low < hight) {
            // hight  ，       ， low   
            while (low < hight && nums[hight] >= index) {
                hight--;
            }
            nums[low] = nums[hight];
            // low       ，    hight       
            while (low < hight && nums[low] <= index) {
                low++;
            }
            nums[hight] = nums[low];
        }
        //  low = hight        ，       
        nums[low] = index;
        return low;
    }
    /*
     * 8、    
     *     ：
     *      ，                     。
     *                 ，         ，                 
     */
    public static int[] mergeSort(int[] nums){
        sortmerge(nums, 0, nums.length - 1);
        return nums;
    }
    private static void sortmerge(int[] nums, int i, int j) {
        if(i >= j){
            return;
        }
        //      
        int middle = (i + j)/2;
        //         
        sortmerge(nums, i, middle);
        //         
        sortmerge(nums, middle + 1, j);
        //    
        merge(nums, i, middle, j);
    }
    private static void merge(int[] nums, int i, int middle, int j) {
        //         
        int[] tmpArr = new int[nums.length];
        //          
        int mid = middle + 1;
        //        
        int second = i;
        //              
        int tmp = i;
        while (i <= middle && mid <= j) {
            //                  
            if(nums[i] <= nums[mid]){
                tmpArr[second++] = nums[i++];
            }else{
                tmpArr[second++] = nums[mid++];
            }
        }
        //            
        while (mid <= j) {
            tmpArr[second++] = nums[mid++];
        }
        while (i <= middle) {
            tmpArr[second++] = nums[i++];
        }
        //        ，       
        while (tmp <= j) {
            nums[tmp] = tmpArr[tmp++];
        }
    }
    /*9、    （ ）
     *                          ，         0
     *   ，          ，         
     *     ：
     * A        （        ）
     * B      ，         
     * C   count           (        )          ；
     * D   start           (          )         ；
     * E                  ；
     * F  (3)(4)(5)             ，         ；
     * G            ；
     */
    public static int[] radixSort(int[] nums) {
                int exp;    //   。            ，exp=1；        ，exp=10；...
                int max = getMax(nums);    //   a     
                //      ，   a "  "    
                for (exp = 1; max/exp > 0; exp *= 10) {
                    countSort(nums, exp);
                }
                return nums;
        }
    //          
    private static int getMax(int[] nums) {
        int i, max;
            max = nums[0];
            for (i = 1; i < nums.length; i++)
                    if (nums[i] > max)
                            max = nums[i];
            return max;
    }
    /*
     *      "    "    (   )
     *     ：
     * exp --   。   a         。
     * (01)  exp=1    "  "   a    
     * (02)  exp=10    "  "   a    
     * (03)  exp=100    "  "   a    
     */
    private static void countSort(int[] a, int exp) {
        int[] output = new int[a.length]; //   "     "     
        int[] buckets = new int[10];
        //            buckets[] 
        for (int i = 0; i < a.length; i++)
            buckets[(a[i] / exp) % 10]++;
        //   buckets[i]。        buckets[i]  ，     output[]    。
        for (int i = 1; i < 10; i++)
            buckets[i] += buckets[i - 1];
        //           output[] 
        for (int i = a.length - 1; i >= 0; i--) {
            output[buckets[(a[i] / exp) % 10] - 1] = a[i];
            buckets[(a[i] / exp) % 10]--;
        }
        //           a[]
        for (int i = 0; i < a.length; i++) {
            a[i] = output[i];
        }
        //     
        output = null;
        buckets = null;
    }

    public static void main(String[] args) {
        int[] nums = {1221,232,1242,24,12,4,1,43,14,4,21,4,14,4,1,41,2};
        //nums = bubbleSort(nums);  
        //nums = selectSort(nums);  
        //nums = ArraySort(nums);  
        //nums = insertSort(nums);  
        //nums = shellSrot(nums);  
        //nums = HeapSorts(nums);    ：   
        //nums = quickSort(nums);  
        //nums = mergeSort(nums);  
        nums = radixSort(nums);
        for (int k = 0; k < nums.length; k++) {
            System.err.println("     "+nums[k]);
        }
    }
}