摘要：對(duì)于不穩(wěn)定的排序算法，只需要舉出實(shí)例，就能證明其不穩(wěn)定性。而對(duì)穩(wěn)定排序算法，必須對(duì)算法進(jìn)行分析才能判斷其是否穩(wěn)定排序算法是否穩(wěn)定是由具體算法決定的，穩(wěn)定算法也可以在某種條件下變?yōu)椴环€(wěn)定算法。

排序算法主要分為兩大類(lèi)

比較排序，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等

非比較排序，主要有：計(jì)數(shù)排序，基數(shù)排序，桶排序等

排序算法的穩(wěn)定性定義：
如果序列中有a=b，排序前a在b之前，排序后a還在b之前，則稱(chēng)這種排序算法是穩(wěn)定的。

對(duì)于不穩(wěn)定的排序算法，只需要舉出實(shí)例，就能證明其不穩(wěn)定性。而對(duì)穩(wěn)定排序算法，必須對(duì)算法進(jìn)行分析才能判斷其是否穩(wěn)定

排序算法是否穩(wěn)定是由具體算法決定的，穩(wěn)定算法也可以在某種條件下變?yōu)椴环€(wěn)定算法。例如冒泡排序中，把交換兩數(shù)的條件變?yōu)锳[i]>=A[i+1]（原本是>號(hào)）

上例告訴我們，算法是由具體的人來(lái)寫(xiě)的，寫(xiě)的垃圾，穩(wěn)定算法也能寫(xiě)的不穩(wěn)定

重復(fù)地走訪過(guò)要排序的元素，依次比較相鄰兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們調(diào)換過(guò)來(lái)，直到?jīng)]有元素再需要交換，排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫?或越大)的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

比較相鄰的元素，如果前一個(gè)比后一個(gè)大，就把它們兩個(gè)調(diào)換位置

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)

針對(duì)所有的元素重復(fù)以上的步驟，除了已經(jīng)排序完成的數(shù)

給一組整數(shù)，按照升序排序，使用選擇排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法

對(duì)于數(shù)組 [3, 2, 1, 4, 5], 排序后為：[1, 2, 3, 4, 5]

無(wú)需分析

fun sortInteger(a : IntArray)
{
    val len = a.size - 1
    var alreadyNum =  0
    var sortFinish = false

    while (alreadyNum <= len - 1 && !sortFinish)
    {
        var perSortFinish = true

        for (i in 1..(len - alreadyNum))
        {
            if (a[i-1] > a[i])
            {
                val temp = a[i-1]
                a[i-1] = a[i]
                a[i] = temp
                perSortFinish = false
            }
        }

        sortFinish = perSortFinish
        alreadyNum += 1
    }
}

public void sortIntegers(int[] A) {
    int len = A.length - 1;
    int alreadyNum = 0;
    boolean sortFinish = false;

    while (alreadyNum <= len - 1 && !sortFinish)
    {
        boolean perSortFinish = true;

        for (int i=1; i <= len-alreadyNum; i++)
        {
            if (A[i-1] > A[i])
            {
                int temp = A[i-1];
                A[i-1] = A[i];
                A[i] = temp;
                perSortFinish = false;
            }
        }

        sortFinish = perSortFinish;
        alreadyNum += 1;
    }
}

通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

先從數(shù)列中取出一個(gè)數(shù)（為方便通常會(huì)選第一個(gè)數(shù)）作為基準(zhǔn)數(shù)

逐個(gè)比較，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊

再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)

直接沿用上一題的實(shí)例，為便于閱讀，將該例子再寫(xiě)一遍

給一組整數(shù)，按照升序排序，使用選擇排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法

對(duì)于數(shù)組 [3, 2, 1, 4, 5], 排序后為：[1, 2, 3, 4, 5]

無(wú)需分析