冒泡排序

以升序來講，我們需要把最小的一個(gè)數(shù)通過換位置的方式調(diào)到最第一個(gè)，那么第二小的數(shù)調(diào)到第二個(gè)位置。每次我們都從最后的一個(gè)數(shù)arr.lenth - 1進(jìn)行相鄰比較大小，小的往前調(diào)，調(diào)動(dòng)至位置i, i從0開始

//排序的時(shí)間復(fù)雜度n*n   個(gè)人覺得(n-1)!更為精確
public static void orderByBubble(int a[]) {
            //先把前面的數(shù)排好.
        for(int i = 0 ; i < a.length - 1 ; i++) { 
            //從最后一個(gè)數(shù)開始往前冒泡.
            for(int j = a.length - 1 ; j > i; j--) {
                //每一輪調(diào)換最小的數(shù)到最前面》
                if(a[j] < a[j-1]) {
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
}

選擇排序

選擇排序比較簡單，每次從第arr.lenth - i 個(gè)數(shù)中找到一個(gè)最大或者最小的數(shù)，并把該數(shù)放到第i個(gè)位置

      /**
     * 每次選擇一個(gè)最小的數(shù)放在對(duì)應(yīng)的i位置.
     * 選擇排序.n*n
     * @param a
     */
    public static void orderBySelect(int a[]) {

        //這個(gè)代表第幾個(gè)數(shù)需要排序.最后n - 1(最后一個(gè))個(gè)數(shù)是不需要排序的，
        for(int i = 0 ; i < a.length - 1; i++) {
            int min = a[i];
            for(int j = i + 1 ; j < a.length ; j++ ) {
                if(min > a[j]) {
                    min = a[j];
                }
            }
            a[i] = min; //第i個(gè)數(shù)的序已經(jīng)排好.
        }
    }

直接插入排序

每次將一個(gè)無序的數(shù)a[i + 1]插入到一個(gè)有序的數(shù)組a[0] ~ a[i]之間，并且對(duì)該數(shù)組排序.

     /** 
     * 直接插入排序. n
     * @param a
     */
    public static void orderByDirectInsert(int a[]) {
        for(int i = 1 ; i < a.length ; i++) {
        // 在有序的數(shù)組里互換位置把己調(diào)整到合適的位置.
            for(int j = i; j > 0 ; j--) { 
                
        //if(a[n] > a[n - 1] && a[n] < a[n + 1])達(dá)到這個(gè)條件我們才說OK.終止循環(huán).
                //如果前面一個(gè)數(shù)要大，那么我們跟前面一個(gè)數(shù)換位置
                if(a[j - 1] > a[j]) {
                    int temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                }
            }           
        }
    }

快速排序

快速排序，又名挖坑填數(shù)

/**
     * 時(shí)間復(fù)雜度n*logn, 空間復(fù)雜度logn
     * 快速排序》,這里就以a[0]為參照.任意數(shù)組中的元素為參照. 挖坑填數(shù).
     * @param a
     * @param l 初始值通常為0
     * @param r 初始值通常為a.length 可以針對(duì)某個(gè)區(qū)間排序.
     */
    public static void orderByQuick(int a[],int l,int r) {
        if(a == null) {
            throw new IllegalArgumentException("a[] == null exception");
        }
                
        if( l  < r) {
            //x只是個(gè)參考基數(shù).后面的動(dòng)作中a[l]最終被放在a[i]上.
            int i = l,j = r,x = a[l];
            while(i < j) {
                //這表示有一個(gè)數(shù)比x大了,退出循環(huán)的條件，是找到一個(gè)比X小的數(shù).
                while(i < j && a[j] >= x) { 
                    j--;
                }
將這個(gè)比x小的數(shù)放在左邊的位置
                a[i++] = a[j];
                
                while (i < j && a[i] < x ) {
                    i++;
                };
                a[j--] = a[i];
                
            }
            a[i] = x;
            orderByQuick(a, l, i - 1);//排左邊
            orderByQuick(a, i+1, r);//排右邊.
        }
    }

堆排序

二叉樹
構(gòu)建最大堆，調(diào)整最大堆，堆邏輯結(jié)構(gòu)表示為一個(gè)完全二叉樹，從最后一個(gè)非葉子節(jié)點(diǎn)開始構(gòu)建最大堆，將堆中的最大元素a[0] 和 最后一個(gè)元素互換位置，之后抹去已經(jīng)調(diào)整完成的最后一個(gè)元素，剩余的元素繼續(xù)調(diào)整出最大堆，以此循環(huán)，直至所有元素調(diào)整完畢. 完全二叉樹每個(gè)節(jié)點(diǎn)下標(biāo)滿足公式n = i/2 - 1, n代表節(jié)點(diǎn)，i代表節(jié)點(diǎn)下面的左孩子. 所以二叉樹最后一個(gè)節(jié)點(diǎn)下標(biāo)是lastNode = (a.lenth - 1)/2 - 1。
最大堆：即任何節(jié)點(diǎn)都比自己左右孩子節(jié)點(diǎn)大.由此根節(jié)點(diǎn)顯然最大.

/**
     * 這個(gè)需要構(gòu)建最大堆.
     */
    public static void builMaxHeap(int a[],int begain,int end) {
        int curPointValue = a[begain];
        int leftIndex = 2*begain + 1;
        for(int i = leftIndex; i*2 + 1 < end ;) 
        {
           //意思是右孩子大于左孩子.
            if(i + 1 < end && a[i + 1] > a[i]) {
               如果右孩子i++，那么下一輪循環(huán),將對(duì)該節(jié)點(diǎn)下的孩子進(jìn)行調(diào)整
如果沒有發(fā)生i++,則要調(diào)整的是左孩子下的所有節(jié)點(diǎn).
                i++;
            }
            // 取出左右孩子中最大的孩子
            if(a[i] > curPointValue) { 
                int temp = a[i];
                a[i] = curPointValue;
                a[begain] = temp;
            }else //表示當(dāng)前節(jié)點(diǎn)自己就是最大的,不必重排了.
                break;
            
            begain = i;
            
        }
        
    }
    
    /**
     * 堆排序. 堆是具有某些特性的完全二叉樹.每個(gè)節(jié)點(diǎn)的值要么都大于等于或者小于等于其子節(jié)點(diǎn).
     * @param a
     */
    public static void orderByHead(int a[]) {
        
        //構(gòu)建最大堆
        for(int i = (a.length - 1)/2 ; i >= 0 ; i--) 
        {
            builMaxHeap(a, i, a.length);
        }
        
        //調(diào)整最大堆.
        for(int j = a.length; j > 0 ; j--) {
            
            int temp = a[0];
            a[0] = a[j - 1];
            a[j-1] = temp;
            builMaxHeap(a,0, j);
        }
        
    }