[[382785]]

本文轉(zhuǎn)載自微信公眾號(hào)「貝塔學(xué)JAVA」，作者Silently9527 。轉(zhuǎn)載本文請(qǐng)聯(lián)系貝塔學(xué)JAVA公眾號(hào)。   

前言

相信所有的程序員剛開始接觸到的算法都會(huì)是排序算法，因?yàn)榕判蛟趯?duì)數(shù)據(jù)處理和計(jì)算有這重要的地位，排序算法往往是其他算法的基礎(chǔ);本文我們就先從初級(jí)排序算法開始學(xué)習(xí)算法。

排序算法的模板

在開始之前我們先定義一個(gè)排序算法通用的模板，在后面的排序算法都會(huì)實(shí)現(xiàn)這個(gè)模板

public interface SortTemplate { 
 
    void sort(Comparable[] array); 
 
    default void print(Comparable[] array) { 
        for (Comparable a : array) { 
            System.out.print(a + " "); 
        } 
    } 
 
    default boolean less(Comparable a, Comparable b) { 
        return a.compareTo(b) < 0; 
    } 
 
    default void exch(Comparable[] array, int i, int j) { 
        Comparable tmp = array[i]; 
        array[i] = array[j]; 
        array[j] = tmp; 
    } 
     
} 

• Comparable: 為了讓我們實(shí)現(xiàn)的排序算法更加的通用，可以排序任意的對(duì)象，所以我們這里使用了Comparable數(shù)組
• sort: 不同的排序算法實(shí)現(xiàn)的方式不一樣，子類自己去實(shí)現(xiàn)
• less: 定義的公用方法，如果a < b就返回true
• exch: 定義的公用方法，交換數(shù)組中的兩個(gè)對(duì)象
• print: 打印出數(shù)據(jù)中的每個(gè)元素

選擇排序

算法實(shí)現(xiàn)的思路：

• 首先找到數(shù)組中的最小元素，
• 其實(shí)將它和數(shù)組中的第一個(gè)元素進(jìn)行交換，這樣就排定了一個(gè)元素;
• 再次找出剩余元素中最小的元素與數(shù)組中的第二個(gè)元素進(jìn)行交換，如此反復(fù)直到所有元素都是有序的

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

public class SelectionSort implements SortTemplate { 
 
    @Override 
    public void sort(Comparable[] array) { 
        int length = array.length; 
        for (int i = 0; i < length; i++) { 
            int min = i; 
            for (int j = i + 1; j < length; j++) { 
                if (less(array[j], array[min])) { 
                    min = j; 
                } 
            } 
            exch(array, i, min); 
        } 
    } 
 
} 

假如輸入的數(shù)組是有序的，我們會(huì)發(fā)現(xiàn)選擇排序運(yùn)行的時(shí)候和未排序的時(shí)間一樣長(zhǎng)!

對(duì)于N個(gè)元素的數(shù)組，使用「選擇排序的時(shí)間復(fù)雜度是O(n2)」

選擇排序的是「數(shù)據(jù)移動(dòng)最少」的，交換的次數(shù)與數(shù)組的大小是線性關(guān)系，N個(gè)元素的數(shù)組需要N次交換

冒泡排序

算法實(shí)現(xiàn)的思路：

• 比較相鄰的兩個(gè)元素，如果前一個(gè)比后一個(gè)大，那么就交換兩個(gè)元素的位置
• 對(duì)每一組相鄰的元素執(zhí)行同樣的操作，直到最后一個(gè)元素，操作完成之后就可以排定一個(gè)最大的元素
• 如此往復(fù)，直到數(shù)組中所有的元素都有序

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

public class BubbleSort implements SortTemplate { 
 
    @Override 
    public void sort(Comparable[] array) { 
        int length = array.length - 1; 
        for (int i = 0; i < length; i++) { 
            for (int j = 0; j < length - i; j++) { 
                if (less(array[j + 1], array[j])) { 
                    exch(array, j, j + 1); 
                } 
            } 
        } 
    } 
 
} 

對(duì)于N個(gè)元素的數(shù)組，使用「冒泡排序的時(shí)間復(fù)雜度是O(n2)」

插入排序

想象我們?cè)谕鎿淇伺茣r(shí)，整理?yè)淇伺贫际前衙恳粡埐迦氲阶筮呉呀?jīng)排好序的牌中適當(dāng)?shù)奈恢谩２迦肱判虻乃悸奉愃?/p>

算法實(shí)現(xiàn)的思路：

• 初始默認(rèn)第一個(gè)元素就是有序的，當(dāng)前索引的位置從0開始
• 先后移動(dòng)當(dāng)前索引的位置，當(dāng)前索引位置左邊的元素是有序的，從后往前開始掃碼與當(dāng)前索引位置元素進(jìn)行比較
• 當(dāng)確定當(dāng)前索引位置上的元素在左邊有序適合的位置之后，插入到該位置上
• 如果當(dāng)確定當(dāng)前索引位置上的元素大于了已排序的最后一個(gè)元素，那么當(dāng)前索引位置直接往后移動(dòng)
• 如此反復(fù)，直到所有元素有序

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

public class InsertionSort implements SortTemplate { 
 
    @Override 
    public void sort(Comparable[] array) { 
        int length = array.length; 
        for (int i = 1; i < length; i++) { 
            for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) { 
                exch(array, j, j - 1); 
            } 
        } 
    } 
 
} 

從代碼的實(shí)現(xiàn)我們可以看出，當(dāng)遇到了當(dāng)前索引的元素大于了左邊有序數(shù)組的最后一個(gè)元素時(shí)，內(nèi)層循環(huán)就直接結(jié)束了，所以所我們排序的數(shù)組中存在著部分有序，那么插入排序算法會(huì)很快。

考慮最糟糕的情況，如果輸入數(shù)組是一個(gè)倒置的，那么插入排序的效率和選擇排序一樣，「時(shí)間復(fù)雜度是O(n2)」

希爾排序

對(duì)于大規(guī)模的亂序數(shù)組插入排序很慢，是因?yàn)樗唤粨Q相鄰的元素，元素只能一點(diǎn)一點(diǎn)的從數(shù)組中移動(dòng)到正確的位置;插入排序?qū)τ诓糠钟行虻臄?shù)組排序是的效率很高;

希爾排序基于這兩個(gè)特點(diǎn)對(duì)插入排序進(jìn)行了改進(jìn);

算法實(shí)現(xiàn)的思路

• 首先設(shè)置一個(gè)步長(zhǎng)h用來分隔出子數(shù)組
• 用插入排序?qū)個(gè)子數(shù)組獨(dú)立排序
• 減小h步長(zhǎng)繼續(xù)排序子數(shù)組，直到h步長(zhǎng)為1
• 當(dāng)步長(zhǎng)為1時(shí)就成了普通的插入排序，這樣數(shù)組一定是有序的

希爾排序高效的原因，在排序之初，各個(gè)子數(shù)組都很短，子數(shù)組排序之后都是部分有序的，這兩種情況都很適合插入排序。

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

public class ShellSort implements SortTemplate { 
 
    @Override 
    public void sort(Comparable[] array) { 
        int gap = 1; 
        int length = array.length; 
 
        while (gap < length / 3) { 
            gap = 3 * gap + 1; 
        } 
 
        while (gap >= 1) { 
            for (int i = gap; i < length; i++) { 
                for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) { 
                    exch(array, j, j - gap); 
                } 
            } 
            gap = gap / 3; 
        } 
    } 
 
}