冒泡排序

思想就是小的數(shù)不停地往上（前）冒，程序?qū)崿F(xiàn)是第i輪從后往前依次比較相鄰兩數(shù)大小，如果小的數(shù)在靠后位置就交換兩數(shù)，這樣這一輪最小的數(shù)就冒泡到了i的位置。

    public static void bubbleSort(int[] a){
        for(int i = 0; i < a.length - 1; ++i){
            for(int j = a.length - 1; j > i; --j){
                if(a[j] < a[j-1]){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }
            }
        }
    }

開始我對(duì)冒泡排序的理解其實(shí)是下沉排序的思想，于是順手寫了個(gè)下沉排序：

    public static void sinkSort(int[] a){
        for(int i = 0; i < a.length - 1; ++i){
            for(int j = 0; j < a.length - i - 1; ++j){
                if(a[j] > a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }

選擇排序

我個(gè)人認(rèn)為最好理解最好實(shí)現(xiàn)的一種排序算法，思想就是第i輪從未排序的序列中找到最小的，跟第i個(gè)數(shù)交換。

public static void selectSort(int[] a){
        for(int i = 0; i < a.length - 1; ++i){
            int min = a[i], minIndex = i;   
            for(int j = i+1; j < a.length; ++j){
                if(a[j] < min){
                    min = a[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){
                int temp = a[i];
                a[i] = min;
                a[minIndex] = temp;
            }
        }
    }

插入排序

思想就是對(duì)前面已排好序的序列，尋找合適的位置插入進(jìn)去。程序怎么實(shí)現(xiàn)插入呢？就是想象把待插入的數(shù)挖出來，從后往前尋找，每發(fā)現(xiàn)當(dāng)前位置不是合適的位置就把當(dāng)前位置的數(shù)往后挪一個(gè)位置，最后發(fā)現(xiàn)合適的位置把待插入的數(shù)塞進(jìn)去。要注意的是j開始的位置就是待插入數(shù)位置的前一個(gè)，并且每次發(fā)現(xiàn)不合適要減一，所以最后發(fā)現(xiàn)合適位置時(shí)應(yīng)該+1回到當(dāng)前位置。

public static void insertSort(int[] a){
        for(int i = 1; i < a.length; ++i){      
            int j = i - 1;
            int temp = a[i];
            while(j >= 0 && temp < a[j]){
                a[j+1] = a[j--];
            }
            a[++j] = temp;
        }
    }

歸并排序

（二路歸并）就是（遞歸）將數(shù)組平分成兩部分，每部分實(shí)現(xiàn)有序，再把兩數(shù)組合并。在合并時(shí)需要用一個(gè)新數(shù)組來存儲(chǔ)合并結(jié)果，所以需要額外O(n)空間。

public static void merge(int[] a, int start, int mid, int end){
        int[] temp = new int[end - start + 1];
        
        int i = start, j = mid+1, k = 0;
        while(i <= mid && j <= end){
            if(a[i] < a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        
        
        while(i <= mid){
            temp[k++] = a[i++];
        }
        while(j <= end){
            temp[k++] = a[j++];
        }
        
        for(i = start; i <= end; ++i){
            a[i] = temp[i-start];
        }
    }
    
    
    public static void mergeSort(int[] a, int start, int end){
        if(start < end){
            int mid = (end - start)/2 + start;
            mergeSort(a,start,mid);
            mergeSort(a,mid+1,end);
            merge(a,start,mid,end);
        }
    }

快速排序

思想是取一個(gè)pivot，讓待排序數(shù)組變成所有小于pivot的數(shù)放pivot左邊，其他放右邊。程序怎樣實(shí)現(xiàn)呢？假設(shè)pivot是待排序的第一個(gè)數(shù)，想象給它挖一個(gè)坑，從后往前找一個(gè)比pivot小的數(shù)來填前面這個(gè)坑，再從前往后找一個(gè)比pivot大于等于的數(shù)來填后面的坑；循環(huán)進(jìn)行，最后剩下的一個(gè)坑就是pivot位置。

    public static void quickSort(int[] a, int start, int end){
        
        if(start < end){
            int pivot = a[start];
            int left = start, right = end;
            
            
            while(left < right){
                while(left < right && a[right] >= pivot){
                    --right;
                }
                if(left < right && a[right] < pivot){
                    a[left++] = a[right];
                }
                
                while(left < right && a[left] < pivot){
                    ++left;
                }
                if(left < right && a[left] >= pivot){
                    a[right--] = a[left];
                }
            }
            
            a[left] = pivot;
            
            quickSort(a,start,left-1);
            quickSort(a,left+1,end);
        }
    }
    
}

還差一個(gè)對(duì)我來說比較難的堆排序，抽時(shí)間一定要寫出來?。。。。。。?！