本文僅作為個人學(xué)習(xí)排序算法的參考筆記，若想詳細(xì)了解學(xué)習(xí)，請前往 http://blog.csdn.net/han_xiaoyang/article/details/12163251

tip：

• 文章中涉及的所有排序均為升序

• 文中會提及穩(wěn)定算法和不穩(wěn)定算法的概念，先貼一下百度的解釋：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

插入排序算法

• 插入排序（Insertion Sort）的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
• 空間代價O(1)
• 平均時間復(fù)雜度為O(n^2)，最好時間復(fù)雜度n-1，最壞時間復(fù)雜度n(n+1)/2
• 穩(wěn)定的排序算法
• 插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。

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

二分插入排序算法

• 二分（折半）插入（Binary insert sort)排序是一種在直接插入排序算法上進(jìn)行小改動的排序算法。其與直接排序算法最大的區(qū)別在于查找插入位置時使用的是二分查找的方式，在速度上有一定提升。
• 穩(wěn)定的排序算法
• 空間代價：O(1)
• 時間代價：插入每個記錄需要O(log i)比較，最多移動i+1次，最少2次。最佳情況O(n log n)，最差和平均情況O(n^2)。
• 當(dāng)n較大時，總排序碼比較次數(shù)比直接插入排序的最差情況好得多，但比最好情況要差，所元素初始序列已經(jīng)按排序碼接近有序時，直接插入排序比二分插入排序比較次數(shù)少。二分插入排序元素移動次數(shù)與直接插入排序相同，依賴于元素初始序列。

void BinInsertSort(int arr[])
{
    for(int i = 1; i < arr.length; i++)
    {
        int left = 0;
        int right = i - 1;
        int temp = arr[i];
        while (left <= right) 
        {
            int middle = (left +right) / 2;
            if(arr[middle] > temp)
            {
                right = middle - 1;
            }
            else 
            {
                left = middle + 1;
            }
        }

        for(int j = i - 1; j >= left; j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }
}

小結(jié)：

• 插入排序：取一個元素，在已排序的元素中一一比較，滿足條件就替換，直至不滿足條件；
• 二分插入排序：取一個元素，在已排序的元素中，找到滿足條件的位置i，讓i + 1往后的元素后退一位，然后將取出的元素插入i位置

希爾排序

• 希爾排序的時間復(fù)雜度與增量序列的選取有關(guān)，例如希爾增量時間復(fù)雜度為O(n^{2)，而Hibbard增量的希爾排序的時間復(fù)雜度為O(N}(5/4))，但是現(xiàn)今仍然沒有人能找出希爾排序的精確下界。
• 不穩(wěn)定排序

void shellSort(int arr[]) 
{
    int gap = arr.length / 2; //在此增量取數(shù)組長度/2
    while(gap > 0)
    {
        for(int i = 0; i < gap; i++)
        {
            int j = i + gap;
            int temp = arr[j];
            while((temp < arr[i]) && (j < arr.length))
            {
                arr[j] = arr[i];
                j += gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}

選擇排序

• 選擇排序(Selection sort)是一種簡單直觀的排序算法。工作原理如下：首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。
• 選擇排序的交換操作介于0和(n-1)次之間
• 選擇排序的比較操作為n(n-1)/2次之間，比較次數(shù)O(n^2)
• 選擇排序的賦值操作介于0和3(n-1)次之間
• 交換次數(shù)O(n),最好情況是，已經(jīng)有序，交換0次；最壞情況是，逆序，交換n-1次
• 交換次數(shù)比冒泡排序少，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快

void selectSort(int arr[]) 
{
    int length = arr.length;
    for(int i = 0; i < length; i++)
    {
        int min = arr[i];
        int index = i;
        int j = i + 1;
        while(j < length)
        {
            if(min > arr[j])
            {
                min = arr[j];
                index = j;
            }
            j++;
        }
        arr[index] = arr[i];
        arr[i] = min;
    }
}

快速排序

• 基本思想:通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序
• 復(fù)雜度: 平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n^2)次比較

• 算法步驟:

1. 從數(shù)列中挑出一個元素，稱為 "基準(zhǔn)"（pivot）;
2. 排序數(shù)組，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)(partition)操作。
3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

function quickSort(first, end, array) {
        var key = array[first];//默認(rèn)選擇第一個為pivot
        var i = first;
        var j = end;
        if (first > end) {
            while (i < j) {
                /**
                 * 以 23 7 36 8 15 9 為例, 第一遍基準(zhǔn)為23
                 */

                // 從數(shù)組最右邊開始遍歷, 如果比基準(zhǔn)大, 則比較下一個; 如果比基準(zhǔn)小, 則賦值到基準(zhǔn)的位置
                while (array[j] > key && j > i) {
                    j--;
                }
                if (i < j) {
                    array[i++] = array[j];
                    // 賦值后, 數(shù)組排列為9 7 36 8 15 9  i=1 j=5
                    // 數(shù)組中有兩個相同的數(shù), 其中賦值到基準(zhǔn)位置的數(shù)才是其正確位置, j位置上的則是可被替換的
                }

                // 從數(shù)組最左邊開始遍歷, 如果比基準(zhǔn)小, 則比較下一個; 如果比基準(zhǔn)大, 則賦值到j(luò)的位置
                while (array[i] < key && j > i) {
                    i++;
                }

                if (i < j) {
                    array[j--] = array[i];
                    // 賦值后, 數(shù)組排列為9 7 36 8 15 36  i=2 j=4
                    // 數(shù)組中有兩個相同的數(shù), 其中賦值到j(luò)位置的數(shù)才是其正確位置, i位置上的則是可被替換的
                }
                array[i] = key;
                // 將基準(zhǔn)賦值到i位置 數(shù)組排序為9 7 23 8 15 36 
                // i=2 j=4 在進(jìn)行一次以23為基準(zhǔn)的循環(huán)
                // 得到 9 7 15 8 23 36  保證在23前的數(shù)都比23小, 在23后的數(shù)都比23大. 則以23為基準(zhǔn)的排序結(jié)束, 跳出循環(huán)
            }

            quickSort(0, i - 1, array);
            quickSort(i + 1, array.length - 1, array);
        }
    }