排序算法

binaryTree 發(fā)布于2019-07-31 11:11 / 1091人閱讀

摘要：排序代碼實(shí)現(xiàn)和一概念排序算法的穩(wěn)定性穩(wěn)定性穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。交換的結(jié)果導(dǎo)致結(jié)點(diǎn)的值變化了，重復(fù)，，的操作，直到?jīng)]有孩子時(shí)跳出代碼實(shí)現(xiàn)構(gòu)建初始堆堆排序算法思想大頂堆舉例將待排序的序列構(gòu)造成一個(gè)大頂堆。

排序

代碼實(shí)現(xiàn)：Java 和 Python

一、概念 1.1 排序算法的穩(wěn)定性

穩(wěn)定性：穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。也就是如果一個(gè)排序算法是穩(wěn)定的，當(dāng)有兩個(gè)相等鍵值的紀(jì)錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過的列表中R也將會(huì)是在S之前。

采用Python說明

原有的序列：

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

按照元組第一個(gè)元素，排序后的情況

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

1.2 常見排序算法效率比較

二、排序算法 2.1 冒泡排序 代碼實(shí)現(xiàn)

Python實(shí)現(xiàn)：

def bubble_sort(alist):
    """
        冒泡排序
    """
    n = len(alist)
    for j in range(n-1):
        count = 0 # 引入來優(yōu)化冒泡排序
        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: #沒發(fā)生交換，說明已經(jīng)有序
            break

Java實(shí)現(xiàn)：

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);
        //打印排序結(jié)果
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}

時(shí)間復(fù)雜度：

最壞時(shí)間復(fù)雜度：O(n^2)

最優(yōu)時(shí)間復(fù)雜度O(1)

穩(wěn)定性：穩(wěn)定

2.2 選擇排序 代碼實(shí)現(xiàn)

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]

復(fù)雜度分析：外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)執(zhí)行 n-1, n-2, n-3, … 1次
所以算法復(fù)雜度為：O(n^2),最優(yōu)最壞都是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;
                }
            }
            //記得加判斷條件 或者 用另一個(gè)變量來進(jìn)行交換
            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(" ");
        }
    }
}

時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：O(n2)
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定

算法不穩(wěn)定：舉例子[3,2,3,1],第一次進(jìn)行選擇排序，下標(biāo)為0的3和最后一位數(shù)交換，此時(shí)兩個(gè)3的順序變了

2.3 插入排序

代碼實(shí)現(xiàn)

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];
                }
                //已經(jīng)是有序了，不用插入交換，跳出
                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(" ");
        }

    }
}

時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：穩(wěn)定

2.4 希爾排序

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

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

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

然后我們對(duì)每列進(jìn)行排序：

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

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

排序之后變?yōu)椋?/p>

最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）

代碼實(shí)現(xiàn)

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，否則會(huì)越界
            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(" ");
        }
    }
}

時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長(zhǎng)序列的不同而不同,最好的情況O(n^1.3)
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定想：不穩(wěn)定

最優(yōu)的情況不如插入排序的好

2.5 快速排序

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

步驟為：

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），

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

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

代碼實(shí)現(xiàn)

兩個(gè)定界實(shí)現(xiàn)(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)

兩個(gè)游標(biāo)實(shí)現(xiàn)(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
一個(gè)小于區(qū)域small實(shí)現(xiàn)(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(" ");
        }
    }
}
利用荷蘭國(guó)旗提升快排速度(java):
為什么能提速？
相比經(jīng)典快排(定一個(gè)數(shù)字privot的位置，拆分按照該位置的左右)，每次找到小于privot定界small和大于privot的定界big，按照值privot來進(jìn)行劃分，可以減少劃分次數(shù)。
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(" ");
        }
    }
}
如果還要提升效率呢？
隨機(jī)快排：
只要把privot在區(qū)間內(nèi)獲取下標(biāo)的值即可實(shí)現(xiàn)：
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(" ");
        }
    }
}
時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(n^2)
穩(wěn)定性：不穩(wěn)定

復(fù)雜度分析：

最優(yōu)：每次拆分的位置都是中間的位置，2*2*2... = n, 次數(shù)的時(shí)間復(fù)雜度是logn
最壞：如果每次都是最右邊或者最左邊，就會(huì)分n次，次數(shù)的時(shí)間復(fù)雜度是n

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

代碼實(shí)現(xiàn)
寫兩個(gè)方法：

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

Python實(shí)現(xiàn)：
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:]
每個(gè)遞歸拿一個(gè)表來存儲(chǔ)一個(gè)合并結(jié)果
Java實(shí)現(xiàn)：
時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度:O(nlogn)
最壞時(shí)間復(fù)雜度:O(nlogn)
穩(wěn)定性：穩(wěn)定(注意合并時(shí)候的比較，小于和小于等于可能影響穩(wěn)定性)

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

完全二叉樹
大頂堆：每個(gè)結(jié)點(diǎn)大于等于它的左右孩子
小頂堆：每個(gè)結(jié)點(diǎn)小于等于它的左右孩子

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

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

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

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

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

如何無序序列構(gòu)建成一個(gè)堆
堆結(jié)構(gòu)非常重要的操作

堆結(jié)構(gòu)的heapInsert和heapify
堆結(jié)構(gòu)的增大和減少
如果只是建立堆的過程，時(shí)間復(fù)雜度為O(N)
優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)，就是堆結(jié)構(gòu)

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

假設(shè)值變化的結(jié)點(diǎn)下標(biāo)為i，找左右孩子(2i+1,2i+2)，獲取到最大的那個(gè)的下標(biāo)j(2i+1 or 2i+2)。
結(jié)點(diǎn)i的值與結(jié)點(diǎn)j比較，如果結(jié)點(diǎn)i值較大或者等于(break:不用往下沉了)，如果小于，交換。
交換的結(jié)果導(dǎo)致結(jié)點(diǎn)j的值變化了，重復(fù)1，2，3的操作，直到?jīng)]有孩子(lchild = index*2+ 1 >= heapsize 時(shí)跳出)

代碼實(shí)現(xiàn)：
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;
        }
    }
構(gòu)建初始堆：
for (int i = (alist.length-1-1)/2; i >= 0 ; i--) {
            heapIfy(alist, i, alist.length);
        }
堆排序算法
思想(大頂堆舉例)：將待排序的序列構(gòu)造成一個(gè)大頂堆。此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將它移走(把它和堆數(shù)組尾部元素交換，此時(shí)末尾就是最大值)，然后將剩余n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到n個(gè)元素中的次大值。如此反復(fù)執(zhí)行，就能得到一個(gè)有序序列。
堆的復(fù)雜度分析：
運(yùn)行時(shí)間主要是消耗在初始構(gòu)建堆和重建堆時(shí)的反復(fù)篩選上。
構(gòu)建堆從非終端節(jié)點(diǎn)開始構(gòu)建，將它與其孩子進(jìn)行比較和若有必要的呼喚，對(duì)于每個(gè)非終端節(jié)點(diǎn)來說，其實(shí)最多進(jìn)行兩次比較和互換操作，因此構(gòu)建堆的時(shí)間復(fù)雜度：O(n)。
正式排序時(shí)，第i次取棧頂記錄重建堆需要用O(logi)的時(shí)間(完全二叉樹的某個(gè)節(jié)點(diǎn)到根結(jié)點(diǎn)距離為「logi」+1)，并且需要取n-1此堆頂記錄，因此，重建堆的時(shí)間復(fù)雜度為O(nlogn)
總體來說，堆排序的時(shí)間復(fù)雜度為O(nlogn)，由于堆排序?qū)υ加涗浀呐判驙顟B(tài)并不敏感，因此它無論是最好、最壞和平均時(shí)間復(fù)雜度均為O(nlogn)。性能上要遠(yuǎn)遠(yuǎn)好過于冒泡、簡(jiǎn)單選擇、直接插入的O(n^2)的時(shí)間復(fù)雜度。
空間復(fù)雜度上，只有一個(gè)用來交換的暫存單元，不過由于記錄的比較與交換是跳躍式進(jìn)行，因此堆排序也是一種不穩(wěn)定的排序方法。由于初始構(gòu)建堆所需的比較次數(shù)較多，因此，它并不適合排序序列個(gè)數(shù)較少的情況。

堆排序的Java代碼實(shí)現(xiàn)：
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);
        }
        //構(gòu)建玩大頂堆的結(jié)果
        System.out.println("構(gòu)建大頂堆的結(jié)果:");
        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("交換堆頂，重新調(diào)整為大頂堆");
            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 最終結(jié)果:");
        for (int i = 0; i < alist.length; i++) {
            System.out.print(alist[i]);
            System.out.print(" ");
        }
    }
}
掌握了堆好處案例：
案例：一個(gè)流不斷吐出數(shù)，隨時(shí)能找到中位數(shù)：
解決方法：
1. 笨方法
一個(gè)大數(shù)組存進(jìn)去，要中位數(shù)的時(shí)候，要先排序，存入是O(1)代價(jià)，排序又是O(N*logN),每次來一個(gè)數(shù)都要排序，如果調(diào)用中位數(shù)次數(shù)很多，代價(jià)很大。
2. 采取堆結(jié)構(gòu)
準(zhǔn)備兩個(gè)1000的數(shù)組，一個(gè)做一個(gè)大根堆，另一個(gè)叫小根堆。如果新來一個(gè)數(shù)比大根堆頭部小，進(jìn)入大根堆。做到吐出的數(shù)，較小的放到大根堆，較大的放到小根堆。如果大根堆的數(shù)目比小根堆的多2，彈出大根堆堆頂，放到小根堆，同理，小根堆比大根堆多的，丟到大根堆去。
最后結(jié)果：N個(gè)數(shù)，N/2存放到大根堆，N/2存放到小根堆，大根堆堆頂是較小的N/2的最大值，小根堆堆頂是較大的N/2個(gè)數(shù)字的最小值，這樣隨時(shí)能找到中位數(shù)。
優(yōu)先級(jí)隊(duì)列不是雙向鏈表，而是堆
三、補(bǔ)充
3.1 拓?fù)渑判?/b>
AOV網(wǎng)：在一個(gè)表示工程的有向圖，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，我們稱之為AOV網(wǎng)(Activity On Vertex Network)
拓?fù)湫蛄?/b>
設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1,v2,…,vn,滿足若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前（描述的是拓?fù)鋱D的前后關(guān)系）。則我們稱這樣的頂點(diǎn)序列尾一個(gè)拓?fù)湫蛄小?/p>
拓?fù)渑判?/b>
對(duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程
構(gòu)造時(shí)有兩個(gè)結(jié)果：


全部節(jié)點(diǎn)被輸出：說明不存在環(huán)的AOV網(wǎng)
如果輸出頂點(diǎn)數(shù)少了，哪怕一個(gè)，說明這個(gè)網(wǎng)存在環(huán)，不是AOV網(wǎng)。

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

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

GPU云服務(wù)器云服務(wù)器排序算法圖解排序算法總結(jié) 桶排序算法學(xué)習(xí)排序算法

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/44756.html

上一篇：python學(xué)習(xí)筆記

下一篇：Python文件夾處理

相關(guān)文章

Github標(biāo)星2w+，熱榜第一，如何用Python實(shí)現(xiàn)所有算法

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

zxhaaa 2019-07-31 10:23 評(píng)論0 收藏0

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學(xué)好前端，先練好內(nèi)功，...

canger 2019-08-26 10:15 評(píng)論0 收藏0

排序算法（Java）——那些年面試常見的排序算法

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

Harpsichord1207 2019-08-15 14:50 評(píng)論0 收藏0

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總

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

zsy888 2019-08-26 10:27 評(píng)論0 收藏0

Java面試題：穩(wěn)定和不穩(wěn)定排序算法之間的區(qū)別-MergeSort與QuickSort

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

wanghui 2019-08-16 16:46 評(píng)論0 收藏0

常用排序算法之JavaScript實(shí)現(xiàn)

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

jerry 2019-08-21 12:27 評(píng)論0 收藏0

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

binaryTree

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章
閱讀更多

VMware虛擬機(jī)安裝黑群暉7.0教程

閱讀 2764·2021-09-24 09:47

搬瓦工申請(qǐng)退款的條件和方法教程

閱讀 4384·2021-08-27 13:10

第八集: 從零開始實(shí)現(xiàn)一套pc端vue的ui組件庫(input, textarea組件)

閱讀 3036·2019-08-30 15:44

前端開發(fā)必備調(diào)試技巧

閱讀 1303·2019-08-29 12:56

關(guān)于彈幕的制作第一篇一樣式

閱讀 2609·2019-08-28 18:07

從零開始實(shí)現(xiàn)一個(gè)Vue級(jí)聯(lián)組件

閱讀 2627·2019-08-26 14:05

JavaScript 事件冒泡和捕獲模式

閱讀 2593·2019-08-26 13:41

在NPM發(fā)布自己造的輪子

閱讀 1279·2019-08-26 13:33

最新活動(dòng)

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

排序算法

構(gòu)建一個(gè)大頂堆的時(shí)間復(fù)雜度分析

heapInsert

heapify （需要傳入heapsize表示堆的大小，注意：heapsize不一定是數(shù)組大小，可能數(shù)組的前半部分是堆，例如堆排序，堆頂放到數(shù)組后的這個(gè)過程，堆的heapsize減一）

1. 笨方法

2. 采取堆結(jié)構(gòu)

相關(guān)文章

Github標(biāo)星2w+，熱榜第一，如何用Python實(shí)現(xiàn)所有算法

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

排序算法（Java）——那些年面試常見的排序算法

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總

Java面試題：穩(wěn)定和不穩(wěn)定排序算法之間的區(qū)別-MergeSort與QuickSort

常用排序算法之JavaScript實(shí)現(xiàn)

發(fā)表評(píng)論

0條評(píng)論

binaryTree

男|高級(jí)講師

TA的文章

VMware虛擬機(jī)安裝黑群暉7.0教程

搬瓦工申請(qǐng)退款的條件和方法教程

第八集: 從零開始實(shí)現(xiàn)一套pc端vue的ui組件庫(input, textarea組件)

前端開發(fā)必備調(diào)試技巧

關(guān)于彈幕的制作第一篇一樣式

從零開始實(shí)現(xiàn)一個(gè)Vue級(jí)聯(lián)組件

JavaScript 事件冒泡和捕獲模式

在NPM發(fā)布自己造的輪子

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

排序算法

構(gòu)建一個(gè)大頂堆的時(shí)間復(fù)雜度分析

heapInsert

heapify （需要傳入heapsize表示堆的大小，注意：heapsize不一定是數(shù)組大小，可能數(shù)組的前半部分是堆，例如堆排序，堆頂放到數(shù)組后的這個(gè)過程，堆的heapsize減一）

1. 笨方法

2. 采取堆結(jié)構(gòu)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

heapify （需要傳入heapsize表示堆的大小，注意：heapsize不一定是數(shù)組大小，可能數(shù)組的前半部分是堆，例如堆排序，堆頂放到數(shù)組后的這個(gè)過程，堆的heapsize減一）