排序算法

binaryTree 發布于2019-07-31 11:11 / 1082人閱讀

摘要：排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了，重復，，的操作，直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。

排序

代碼實現：Java 和 Python

一、概念 1.1 排序算法的穩定性

穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序算法是穩定的，當有兩個相等鍵值的紀錄R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

采用Python說明

原有的序列：

(4, 1)  (3, 1)  (3, 7)（5, 6）

按照元組第一個元素，排序后的情況

(3, 1)  (3, 7)  (4, 1)  (5, 6)  (維持次序:穩定）
(3, 7)  (3, 1)  (4, 1)  (5, 6) （次序被改變）

1.2 常見排序算法效率比較

二、排序算法 2.1 冒泡排序 代碼實現

Python實現：

def bubble_sort(alist):
    """
        冒泡排序
    """
    n = len(alist)
    for j in range(n-1):
        count = 0 # 引入來優化冒泡排序
        for i in range(n-j-1):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if count == 0: #沒發生交換，說明已經有序
            break

Java實現：

public class Bubble {
    public void bubble_sort(int[] alist){
        System.out.print("Bubble Sort:");
        for (int j = 0; j < alist.length; j++) {
            for (int i = 0;  i < alist.length-j-1; i++) {
                if(alist[i] > alist[i+1]){
                    alist[i] = alist[i] + alist[i+1];
                    alist[i+1] = alist[i] - alist[i+1];
                    alist[i] = alist[i] - alist[i+1];
                }
            }
        }

    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Bubble sort = new Bubble();
        sort.bubble_sort(alist);
        //打印排序結果
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}

時間復雜度：

最壞時間復雜度：O(n^2)

最優時間復雜度O(1)

穩定性：穩定

2.2 選擇排序 代碼實現

Python:

def select_sort(alist):
    n = len(alist)
    for j in range(n-1):
        min_index = j 
        for i in range(j+1,n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

復雜度分析：外層循環執行n-1次，內層循環執行 n-1, n-2, n-3, … 1次
所以算法復雜度為：O(n^2),最優最壞都是O(n^2)
Java:

public class Select {
    public void select(int[] alist){
        System.out.print("Select Sort:");
        int min;
        for (int j = 0; j < alist.length-1; j++) {
            min = j;
            for (int i = j+1; i < alist.length; i++) {
                if(alist[i] < alist[min]){
                    min = i;
                }
            }
            //記得加判斷條件 或者 用另一個變量來進行交換
            if(min!=j){
                alist[j] = alist[j] + alist[min];
                alist[min] = alist[j] - alist[min];
                alist[j] = alist[j] - alist[min];
            }
        }

    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Select sort = new Select();
        sort.select(alist);
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}

時間復雜度

最優時間復雜度：O(n2)
最壞時間復雜度：O(n2)
穩定性：不穩定

算法不穩定：舉例子[3,2,3,1],第一次進行選擇排序，下標為0的3和最后一位數交換，此時兩個3的順序變了

2.3 插入排序

代碼實現

Python:

def insert_sort(alist):
    n = len(alist)
    for j in range(1,n):        
        for i in range(j,0,-1):
            if alist[i] < alist[i-1]:
                alist[i-1], alist[i] = alist[i], alist[i-1]
            else:
                break

Java:

public class Insert {

    public void insert(int[] alist){
        System.out.println("Insert Sort");
        for (int j = 1; j < alist.length; j++) {
            for (int i = j-1; i >= 0 ; i--) {
                if(alist[i+1] < alist[i]){
                    alist[i] = alist[i] + alist[i+1];
                    alist[i+1] = alist[i] - alist[i+1];
                    alist[i] = alist[i] - alist[i+1];
                }
                //已經是有序了，不用插入交換，跳出
                else{
                    break;
                }
            }
        }

    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Insert sort = new Insert();
        sort.insert(alist);
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }

    }
}

時間復雜度

最優時間復雜度：O(n) （升序排列，序列已經處于升序狀態）
最壞時間復雜度：O(n2)
穩定性：穩定

2.4 希爾排序

希爾排序(Shell Sort)是插入排序的一種，也稱縮小增量排序，把一個序列按照一定增量分組，對每組使用直接插入排序算法排序；增量逐漸減少，當增量減至1時，整個文件恰好被分成一組，算法終止

舉例：
例如，假設有這樣一組數組[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣(豎著的元素是步長組成)：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我們對每列進行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

將上述四行數字，依序接在一起時我們得到：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。這時10已經移至正確位置了，然后再以3為步長進行排序：

排序之后變為：

最后以1步長進行排序（此時就是簡單的插入排序了）

代碼實現

Python:

def shell_sort(alist):
    n = len(alist)
    gap = n//2 # python3
    while gap > 0:
        for j in range(gap, n)
            i = j
            # 注意判斷條件，不能寫i>0，否則會越界
            while i>= gap and alist[i] < alist[i-gap]:
                alist[i],alist[i-gap] = alist[i-gap],alist[i]
                i -= gap
        gap = gap//2

Java:

public class Shell {
    public void shell(int[] alist){
        System.out.println("Shell Sort:");
        int gap = alist.length/2;
        while(gap>0){
            for (int j = gap; j < alist.length; j++) {
                for (int i = j; i >= gap; i -= gap) {
                    if(alist[i] < alist[i-gap]){
                        alist[i] = alist[i] + alist[i-gap];
                        alist[i-gap] = alist[i] - alist[i-gap];
                        alist[i] = alist[i] - alist[i-gap];
                    }
                    else{
                        break;
                    }
                }
            }
            gap /= 2;
        }

    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Shell sort  = new Shell();
        sort.shell(alist);
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}

時間復雜度

最優時間復雜度：根據步長序列的不同而不同,最好的情況O(n^1.3)
最壞時間復雜度：O(n2)
穩定想：不穩定

最優的情況不如插入排序的好

2.5 快速排序

快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

步驟為：

從數列中挑出一個元素，稱為"基準"（pivot），

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

代碼實現

兩個定界實現(Python):

def quick_sort(alist, start, end):
    if start >= end;
        return
    privot = alist[start]
    left = start
    right = end
    while left < right:
        while left < right and alist[right] > privot:
            right -= 1
        alist[left] = alist[right]
        while left < right and alist[left] <= privot:
            left += 1
        alist[right] = alist[left]
    alist[low] = privot
    quick_sort(alist, start, low-1)
    quick_sort(alist, low+1, end)

兩個游標實現(Java):

public class Quick {
    public void quick(int[] alist, int start, int end){
        if(start >= end){
            return;
        }
        int privot = alist[start];
        int low = start;
        int high = end;
        while(lowprivot){
                high--;
            }
            alist[low] = alist[high];
            while(low
一個小于區域small實現(Java):
public class Quick {
    public void quick(int[] alist, int start, int end){
        if(start >= end){
            return;
        }
        int privot = alist[start];
        int small = start - 1;
        for (int i = start; i < end; i++) {
            if (alist[i] <= privot){
                swap(alist, i, ++small);
            }
        }
        swap(alist, start, small);
        quick(alist, start, small-1);
        quick(alist, small+1,end);

    }
    public void swap(int[] alist, int x, int y){
        if(x==y){
            return;
        }
        alist[x] = alist[x] + alist[y];
        alist[y] = alist[x] - alist[y];
        alist[x] = alist[x] - alist[y];
    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Quick sort = new Quick();
        System.out.println("Quick Sort:");
        sort.quick(alist,0,alist.length);
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}
利用荷蘭國旗提升快排速度(java):
為什么能提速？
相比經典快排(定一個數字privot的位置，拆分按照該位置的左右)，每次找到小于privot定界small和大于privot的定界big，按照值privot來進行劃分，可以減少劃分次數。
public class Quick {
    public void quick(int[] alist, int start, int end){
        if(start >= end){
            return;
        }
        int privot = alist[start];
        int small = start - 1;
        int big = end + 1;
        for (int i = start; i < big; i++) {
            if (alist[i] < privot){
                swap(alist, i, ++small);
            }
            else if (alist[i] > privot){
                swap(alist, i, --big);
                i--;
            }
        }
        quick(alist, start, small);
        quick(alist, big, end);

    }
    public void swap(int[] alist, int x, int y){
        if(x==y){
            return;
        }
        alist[x] = alist[x] + alist[y];
        alist[y] = alist[x] - alist[y];
        alist[x] = alist[x] - alist[y];
    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Quick sort = new Quick();
        System.out.println("Quick Sort:");
        sort.quick(alist,0,alist.length-1);
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}
如果還要提升效率呢？
隨機快排：
只要把privot在區間內獲取下標的值即可實現：
int privot = alist(int)(start+Math.random()*(end-start+1));
public class Quick {
    public void quick(int[] alist, int start, int end){
        if(start >= end){
            return;
        }
        int privot = alist[(int)(start+Math.random()*(end-start+1))];
        int small = start - 1;
        int big = end + 1;
        for (int i = start; i < big; i++) {
            if (alist[i] < privot){
                swap(alist, i, ++small);
            }
            else if (alist[i] > privot){
                swap(alist, i, --big);
                i--;
            }
        }
        quick(alist, start, small);
        quick(alist, big, end);

    }
    public void swap(int[] alist, int x, int y){
        if(x==y){
            return;
        }
        alist[x] = alist[x] + alist[y];
        alist[y] = alist[x] - alist[y];
        alist[x] = alist[x] - alist[y];
    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        Quick sort = new Quick();
        System.out.println("Quick Sort:");
        sort.quick(alist,0,alist.length-1);
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}
時間復雜度

最優時間復雜度：O(nlogn)
最壞時間復雜度：O(n^2)
穩定性：不穩定

復雜度分析：

最優：每次拆分的位置都是中間的位置，2*2*2... = n, 次數的時間復雜度是logn
最壞：如果每次都是最右邊或者最左邊，就會分n次，次數的時間復雜度是n

2.6 歸并排序
歸并排序是采用分治法的一個非常典型的應用。歸并排序的思想就是先遞歸分解數組，再合并數組。
將數組分解最小之后，然后合并兩個有序數組，基本思路是比較兩個數組的最前面的數，誰小就先取誰，取了后相應的指針就往后移一位。然后再比較，直至一個數組為空，最后把另一個數組的剩余部分復制過來即可。

代碼實現
寫兩個方法：

遞歸拆分(條件：小于等于1，直接返回傳入的表）
合并(需要兩個游標)

Python實現：
def merge_sort(alist):
    if len(alist) == 1:
        return alist
    mid = len(alist)//2
    left = merge_sort(alist[:mid])
    right = merge_sort(alist[mid:])
    return merge(left,right)

def merge(left,right):
    result = []
    L_point = 0
    R_point = 0
    while L_point < len(left) and R_point < len(right):
        if left[L_point] <= right[R_point]:
            result.append(left[L_point])
            L_point += 1
        else:
            result.append(right[R_point])
            R_point += 1
    result += left[L_point:]
    result += right[R_point:]
每個遞歸拿一個表來存儲一個合并結果
Java實現：
時間復雜度

最優時間復雜度:O(nlogn)
最壞時間復雜度:O(nlogn)
穩定性：穩定(注意合并時候的比較，小于和小于等于可能影響穩定性)

時間復雜度分析：縱向拆分O(logn)，橫向O(n)
時間復雜度是小的，但是需要一個和原來一樣大的數組來存儲，空間復雜度高
2.8 堆排序
堆排序引入的好處
簡單選擇排序，在待排序的n個記錄中選擇最小的記錄需要比較n-1次。(這可以理解：查找第一個數據需要比較這么多次是正常的，否則如何知道它是最小的記錄)
可惜的是：選擇排序沒有把每一趟的比較結果保存下來，在后一趟的比較中，有許多比較在前一趟就已經做過了，但是由于前一趟排序未保存這些比較結果，所以以后一趟排序又重復執行了這些比較操作，因此記錄的比較次數較多。
如果可以做到每次在選擇到最小記錄的同時，根據比較結果對其他記錄做出相應的調整，那樣排序的總體效率就會非常高了。堆排序(Heap Sort)，就是對簡單選擇排序進行的一種改進。
堆結構
堆結構具有的性質

完全二叉樹
大頂堆：每個結點大于等于它的左右孩子
小頂堆：每個結點小于等于它的左右孩子

大頂堆滿足的位置關系(限制條件：1<=i<=「n/2」  「」我表示為：取整)：

i(父) >= 2i(左孩子)
i(父) >= 2i+1(右孩子)

小頂堆滿足的位置關系(限制條件：1<=i<=「n/2」  「」我表示為：取整)：

i(父) <= 2i(左孩子)
i(父) <= 2i+1(右孩子)

如果知道位置i(i>1)，可以得到其雙親結點「i/2」;由此可推得,上式n個結點的二叉樹，那么其i自然就得約束小于等于「n/2」。注意：以上說明的位置是從1開始的，即根節點是1。如果你是用數組存儲一個完全二叉樹，那么，根節點應該是0，左孩子是2i+1,右孩子是2i+2。一個結點的父節點是(i-1)/2。我們來看特殊點，0結點，父節點(0-1)/2 結果是0，所以0的父節點是自己，符合。

如何無序序列構建成一個堆
堆結構非常重要的操作

堆結構的heapInsert和heapify
堆結構的增大和減少
如果只是建立堆的過程，時間復雜度為O(N)
優先級隊列結構，就是堆結構

構建一個大頂堆的時間復雜度分析
一個堆(如大頂堆)，新增一個數，復雜度只跟樹的高度有關系，因為只要往上的父節點依次比較即可，跟其他結點無關。
i結點加入的調整代價為log(i-1)，i+1結點加入的調整代價為logi，所以n個結點的調整代價為：log1+log2+log3+…+log(n-1), 復雜度為O(n)，所以建立一個大根堆的復雜度就是O(n)
heapInsert
已經建立好一個堆，新增一個結點，要依次向上進行比較。什么時候停止？知道不比父節點大的時候
heapify （需要傳入heapsize表示堆的大小，注意：heapsize不一定是數組大小，可能數組的前半部分是堆，例如堆排序，堆頂放到數組后的這個過程，堆的heapsize減一）
應用：數組的一個值變化了，假如變小了，從這個位置往下進行heapify過程重新調整為大根堆。
方法：

假設值變化的結點下標為i，找左右孩子(2i+1,2i+2)，獲取到最大的那個的下標j(2i+1 or 2i+2)。
結點i的值與結點j比較，如果結點i值較大或者等于(break:不用往下沉了)，如果小于，交換。
交換的結果導致結點j的值變化了，重復1，2，3的操作，直到沒有孩子(lchild = index*2+ 1 >= heapsize 時跳出)

代碼實現：
public void heapIfy(int[] alist, int location, int heapsize){
        for (int j = location*2+1; j < heapsize; j = 2*j +1){
            j = ((j + 1) < heapsize && alist[j] < alist[j + 1]) ? j+1 : j;
            if (alist[location] >= alist[j]) {
                break;
            }
            swap(alist, location, j);
            location = j;
        }
    }
構建初始堆：
for (int i = (alist.length-1-1)/2; i >= 0 ; i--) {
            heapIfy(alist, i, alist.length);
        }
堆排序算法
思想(大頂堆舉例)：將待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆頂的根節點。將它移走(把它和堆數組尾部元素交換，此時末尾就是最大值)，然后將剩余n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次大值。如此反復執行，就能得到一個有序序列。
堆的復雜度分析：
運行時間主要是消耗在初始構建堆和重建堆時的反復篩選上。
構建堆從非終端節點開始構建，將它與其孩子進行比較和若有必要的呼喚，對于每個非終端節點來說，其實最多進行兩次比較和互換操作，因此構建堆的時間復雜度：O(n)。
正式排序時，第i次取棧頂記錄重建堆需要用O(logi)的時間(完全二叉樹的某個節點到根結點距離為「logi」+1)，并且需要取n-1此堆頂記錄，因此，重建堆的時間復雜度為O(nlogn)
總體來說，堆排序的時間復雜度為O(nlogn)，由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞和平均時間復雜度均為O(nlogn)。性能上要遠遠好過于冒泡、簡單選擇、直接插入的O(n^2)的時間復雜度。
空間復雜度上，只有一個用來交換的暫存單元，不過由于記錄的比較與交換是跳躍式進行，因此堆排序也是一種不穩定的排序方法。由于初始構建堆所需的比較次數較多，因此，它并不適合排序序列個數較少的情況。

堆排序的Java代碼實現：
public class HeapSort {
    public void heapIfy(int[] alist, int location, int heapsize){
        for (int j = location*2+1; j < heapsize; j = 2*j +1){
            j = ((j + 1) < heapsize && alist[j] < alist[j + 1]) ? j+1 : j;
            if (alist[location] >= alist[j]) {
                break;
            }
            swap(alist, location, j);
            location = j;
        }
    }
    public void swap(int[] alist, int x, int y){
        int temp;
        temp = alist[x];
        alist[x] = alist[y];
        alist[y] = temp;
    }
    public void heapSort(int[] alist){
        for (int i = (alist.length-1-1)/2; i >= 0 ; i--) {
            heapIfy(alist, i, alist.length);
        }
        //構建玩大頂堆的結果
        System.out.println("構建大頂堆的結果:");
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        for (int i = 1; i < alist.length; i++) {

            swap(alist, 0, alist.length-i);

            heapIfy(alist, 0, alist.length-i);
            System.out.println("交換堆頂，重新調整為大頂堆");
            for (int j = 0; j < alist.length; j++) {
                System.out.print(alist[j]);
                System.out.print(" ");
            }
            System.out.println(" ");
        }

    }
    public static void main(String[] args) {
        int[] alist = {54,26,93,17,77,31,44,55,20};
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
        System.out.println(" ");
        HeapSort sort = new HeapSort();
        sort.heapSort(alist);
        System.out.println("Heap Sort 最終結果:");
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}
掌握了堆好處案例：
案例：一個流不斷吐出數，隨時能找到中位數：
解決方法：
1. 笨方法
一個大數組存進去，要中位數的時候，要先排序，存入是O(1)代價，排序又是O(N*logN),每次來一個數都要排序，如果調用中位數次數很多，代價很大。
2. 采取堆結構
準備兩個1000的數組，一個做一個大根堆，另一個叫小根堆。如果新來一個數比大根堆頭部小，進入大根堆。做到吐出的數，較小的放到大根堆，較大的放到小根堆。如果大根堆的數目比小根堆的多2，彈出大根堆堆頂，放到小根堆，同理，小根堆比大根堆多的，丟到大根堆去。
最后結果：N個數，N/2存放到大根堆，N/2存放到小根堆，大根堆堆頂是較小的N/2的最大值，小根堆堆頂是較大的N/2個數字的最小值，這樣隨時能找到中位數。
優先級隊列不是雙向鏈表，而是堆
三、補充
3.1 拓撲排序
AOV網：在一個表示工程的有向圖，用頂點表示活動，用弧表示活動之間的優先關系，這樣的有向圖為頂點表示活動的網，我們稱之為AOV網(Activity On Vertex Network)
拓撲序列
設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列v1,v2,…,vn,滿足若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前（描述的是拓撲圖的前后關系）。則我們稱這樣的頂點序列尾一個拓撲序列。
拓撲排序
對一個有向圖構造拓撲序列的過程
構造時有兩個結果：

全部節點被輸出：說明不存在環的AOV網
如果輸出頂點數少了，哪怕一個，說明這個網存在環，不是AOV網。

算法思想：從AOV網中選擇一個入度為0的頂點輸出，然后刪去此頂點，并刪除此頂點為尾的弧，繼續重復此步驟，直到輸出全部頂點或者AOV網中不存在入度為0的頂點為止
需要由棧來實現
3.2 基數排序(Radix Sort)
基本思想：  
將整數按位數切割成不同的數字，然后按每個位數分別比較
具體做法：  
將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。
基數排序圖文說明：

3.3 計數排序
計數排序的核心思想：我們對一個整數數組進行排序時，可以創建一個輔助數組，大小為待排序數組最大元素和最小元素的差值(時間復雜度O(n+k))，根據待排序數組元素的值，直接確定位置。
例子：排序的數為 7 4 2 1 5 3 1 5；則比7小的有7個數，所有7應該在排序好的數列的第八位，同理3在第四位，對于重復的數字，1在1位和2位（暫且認為第一個1比第二個1小），5和1一樣位于6位和7位。
小學生站隊問題
　　假設有一個班級的小學生去操場上體育課，體育老師要求他們按照身高次序站成一隊。每個小學生都知道自己的具體身高是多少厘米（假設每個小學生身高都不一樣，否則就會為爭執位置打架），但每個小學生都不承認別人比自己高，非得互相詢問身高比較才能承認，大多數小學生在經過很多次詢問和被詢問后才能老老實實站在自己的位置上。場面嘰嘰喳喳混亂不已，快下課才排好隊。 
　　體育老師十分頭疼，（于是，以后每次要上體育課，英語老師都會進班級說：體育老師請假了，這節課我來上。）于是想到了一個好辦法。他先得到班級最高和最矮學生的身高，假定是１１１ｃｍ到１７０ｃｍ，然后在操場上，每隔半步距離用樹粉筆寫上一個數字，數字從最矮的身高１１１開始，１１２，１１３，．．．一直寫到１７０。上課的時候，老師要求同學們根據自己的身高，站到相應的位置，然后大叫一聲：向右看齊！所有的小學生都有序站成一隊了！

GPU云服務器云服務器排序算法圖解排序算法總結桶排序算法學習排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44756.html

Github標星2w+，熱榜第一，如何用Python實現所有算法

摘要：歸并排序歸并排序，或，是創建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚學會了Python基礎知識，想進階一下，那就來點算法吧！畢竟編程語言只...

zxhaaa 2019-07-31 10:23 評論0 收藏0
JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
排序算法（Java）——那些年面試常見的排序算法

摘要：下面會介紹的一種排序算法快速排序甚至被譽為世紀科學和工程領域的十大算法之一。我們將討論比較排序算法的理論基礎并中借若干排序算法和優先隊列的應用。為了展示初級排序算法性質的價值，我們來看一下基于插入排序的快速的排序算法希爾排序。前言　　排序就是將一組對象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期，大家普遍...

Harpsichord1207 2019-08-15 14:50 評論0 收藏0
JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0
Java面試題：穩定和不穩定排序算法之間的區別-MergeSort與QuickSort

摘要：穩定與不穩定算法示例以下圖片解釋了穩定和不穩定的排序是如何工作的這就是穩定和不穩定排序算法之間的區別。穩定排序算法的一些常見示例是合并排序，插入排序和冒泡排序。 showImg(https://segmentfault.com/img/remote/1460000018913243); 來源 | 愿碼(ChainDesk.CN)內容編輯愿碼Slogan | 連接每個程序員的故事網...

wanghui 2019-08-16 16:46 評論0 收藏0
常用排序算法之JavaScript實現

摘要：代碼實現六堆排序算法簡介堆排序是指利用堆這種數據結構所設計的一種排序算法。九計數排序算法簡介計數排序是一種穩定的排序算法。計數排序不是比較排序，排序的速度快于任何比較排序算法。贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

jerry 2019-08-21 12:27 評論0 收藏0