Java 八種排序算法總結

前言

一、簡介

二、算法複雜度

三、常見算法

（1）冒泡排序

（2）選擇排序

（3）插入排序

（4）歸并排序

（5）快速排序

（6）希爾排序

（7）基數排序

（8）堆排序

四、總結

五、Demo位址

六、參考文檔

七、内容推薦

前言

好久沒複習基礎了，寫個冒泡排序都要想一會。感覺自己好像老了好多，今天手癢總結一下排序算法。目前網上部落格普遍都有詳細介紹，寫的很清楚。說實話我是沒必要再寫一遍的，感覺就是在啰嗦、還是重複性的，但是如果隻是單純看的話，不到3分鐘我就忘記了（可能是健忘症晚期）。是以還是自己親手“教訓”一下印象比較深刻。

一、簡介

排序(Sorting) 是計算機程式設計中的一種重要操作，它的功能是将一個資料元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

排序算法在很多領域得到相當地重視，尤其是在大量資料的處理方面。一個優秀的算法可以節省大量的資源。在各個領域中考慮到資料的各種限制和規範，要得到一個符合實際的優秀算法，得經過大量的推理和分析。

那麼怎麼對比哪個排序算法更好呢？這時候就是要看誰運作的比較快。哈哈真是一句廢話，誰不知道呢

Java 八種排序算法總結

是以我們需要了解一下算法複雜度。

二、算法複雜度

時間複雜度是指執行算法所需要的計算工作量；而空間複雜度是指執行這個算法所需要的記憶體空間

（1）時間複雜度

時間複雜度可以認為是對排序資料的總的操作次數。反映當n變化時，操作次數呈現什麼規律。

常見的時間複雜度有：常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)。

時間複雜度O(1)：算法中語句執行次數為一個常數，則時間複雜度為O(1)。

（2）空間複雜度

空間複雜度是指算法在計算機内執行時所需存儲空間的度量，它也是問題規模n的函數。

空間複雜度O(1)：當一個算法的空間複雜度為一個常量，即不随被處理資料量n的大小而改變時，可表示為O(1)。

空間複雜度O(log2N)：當一個算法的空間複雜度與以2為底的n的對數成正比時，可表示為O(log2n) ， ax=N，則x=logaN。

空間複雜度O(n)：當一個算法的空間複雜度與n成線性比例關系時，可表示為0(n)。

（3）排序算法穩定性

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

穩定性的意義

1、如果隻是簡單的進行數字的排序，那麼穩定性将毫無意義。

2、如果排序的内容僅僅是一個複雜對象的某一個數字屬性，那麼穩定性依舊将毫無意義

3、如果要排序的内容是一個複雜對象的多個數字屬性，但是其原本的初始順序毫無意義，那麼穩定性依舊将毫無意義。

4、除非要排序的内容是一個複雜對象的多個數字屬性，且其原本的初始順序存在意義，那麼我們需要在二次排序的基礎上保持原有排序的意義，才需要使用到穩定性的算法，例如要排序的内容是一組原本按照價格高低排序的對象，如今需要按照銷量高低排序，使用穩定性算法，可以使得想同銷量的對象依舊保持着價格高低的排序展現，隻有銷量不同的才會重新排序。

Java 八種排序算法總結

太複雜了，我也隻了解了點皮毛。就簡單介紹這些，要詳細了解的同學們還是自己看書吧！！！

Java 八種排序算法總結

三、常見算法

（1）冒泡排序

1、簡介：

重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來

2、步驟：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較

3、動圖：

Java 八種排序算法總結

4、代碼：

public static void order1(int[] a) {
    boolean hasSwap;
    for(int x=0;x<a.length-1;x++) {
        hasSwap = false;
        for (int y = 0; y < a.length-1-x; y++) {
            if(a[y]>a[y+1]) {
                int t = a[y];
                a[y] = a[y+1];
                a[y+1] = t;
                hasSwap = true;
            }
        }
        if(hasSwap == false) return;
    }
}

（2）選擇排序

1、簡介：

每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的資料元素排完。選擇排序是不穩定的排序方法

2、步驟：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
重複第二步，直到所有元素均排序完畢。

3、動圖：

Java 八種排序算法總結

4、代碼：

public static void order2(int[] a) {
    for (int i = 0; i < a.length-1; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

（3）插入排序

1、簡介：

插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但将最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就隻包含這一個元素（即待插入元素）。在第一部分排序完成後，再将這個最後元素插入到已排好序的第一部分中。

2、步驟：

從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大于新元素，将該元素移到下一位置
重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到下一位置中
重複步驟2~5

3、動圖：

Java 八種排序算法總結

4、代碼：

public static void order3(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int get = a[i];
        int j = i-1;
        while (j >= 0 && a[j] > get) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = get;
    }
}

（4）歸并排序

1、簡介：

将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。

2、步驟：

把長度為n的輸入序列分成兩個長度為n/2的子序列。
對這兩個子序列分别采用歸并排序。
将兩個排序好的子序列合并成一個最終的排序序列。

3、動圖：

Java 八種排序算法總結

4、代碼：

/**
* 歸并排序
*/
public static void order4(int[] a) {
    sort(a,0,a.length-1);
}

public static void sort(int[] data,int left,int right) {
    if(left >= right) return;
    //找出中間索引
    int center = (left + right)/2;
    //對左邊數組進行遞歸
    sort(data, left, center);
    //對右邊數組進行遞歸
    sort(data, center+1, right);
    //合并
    merge(data,left,center,right);
}
	
public static void merge(int[] data,int left, int center,int right) {
    //臨時數組
    int[] tmpArr = new int[data.length];
    //右數組第一個元素索引
    int mid = center + 1;
    //third 記錄臨時數組的索引
    int third = left;
    //緩存左數組第一個元素的索引
    int tmp = left;
    while (left <= center && mid <=right) {
        //從兩個數組中取出最小的放入臨時數組
        if (data[left] <= data[mid]) {
            tmpArr[third++] = data[left++];
        } else {
            tmpArr[third++] = data[mid++];
        }
    }
    //剩餘部分依次放入臨時數組（實際上兩個while隻會執行其中一個）
    while(mid <= right) {
        tmpArr[third++] = data[mid++];
    }
    while(left <= center) {
        tmpArr[third++] = data[left++];
    }
    //将臨時數組中的内容拷貝回原數組中
    while (tmp <= right) {
        data[tmp] = tmpArr[tmp++];
    }
}

（5）快速排序

1、簡介：

在數組中随機選一個數（預設數組首個元素），數組中小于等于此數的放在左邊，大于此數的放在右邊，再對數組兩邊遞歸調用快速排序，重複這個過程。

2、步驟：

先從數列中取出一個數作為key值；
将比這個數小的數全部放在它的左邊，大于或等于它的數全部放在它的右邊；
對左右兩個小數列重複第二步，直至各區間隻有1個數。

3、動圖：

Java 八種排序算法總結

4、代碼：

/**
* 快速排序
*/
public static void order5(int[] a) {
    quickSort(a,0,a.length-1);
}

private static void quickSort(int[] a, int left, int right) {
    if(left < right) {
        int i = getMiddle(a,left,right);
        quickSort(a, left, i - 1);
        quickSort(a, i + 1,right);
    }
}
	
private static int getMiddle(int[] a, int low, int high) {
    int pivot = a[low];
    int i = low;
    int j = high;
    while(i < j) {
        while(pivot <= a[j] && i < j) j--;
        while(pivot >= a[i] && i < j) i++;
        if(i < j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    a[low] = a[i];
    a[i] = pivot;
    return i;
}

（6）希爾排序

1、簡介：

希爾排序是插入排序改良的算法，希爾排序步長從大到小調整，第一次循環後面元素逐個和前面元素按間隔步長進行比較并交換，直至步長為1，步長選擇是關鍵。

2、步驟：

先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，具體算法描述：

選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列個數k，對序列進行k 趟排序；
每趟排序，根據對應的增量ti，将待排序列分割成若幹長度為m 的子序列，分别對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

3、動圖：

Java 八種排序算法總結

4、代碼：

/**
* 希爾排序
*/
public static void order6(int[] a) {
    int len = a.length;//單獨把數組長度拿出來，提高效率。
    while(len != 0) {
        len = len/2;
        for (int i = 0; i < len; i++) {//分組
            for (int j = i + 1; j < a.length; j+=len) {//元素從第二個開始
                int k = j - len;//k為有序序列最後一位的位數
                int temp = a[j];//要插入的元素
                while (k >= 0 && temp < a[k]) {//從後往前周遊
                    a[k + len] = a[k];
                    k -= len;//向後移動len位
                }
                a[k + len] = temp;
            }
        }
    }
}

（7）基數排序

1、簡介：

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。

2、步驟：

取得數組中的最大數，并取得位數；
arr為原始數組，從最低位開始取每個位組成radix數組；
對radix進行計數排序（利用計數排序适用于小範圍數的特點）；

3、動圖：

Java 八種排序算法總結

4、代碼：

/**
* 基數排序
*/
public static void order7(int[] a) {
    int max = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    int time = 0;
    while (max > 0) {
        max /= 10;
        time++;
    }
    List<ArrayList<Integer>> queue = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < 10; i++) {
        ArrayList<Integer> queue1 = new ArrayList<Integer>();
        queue.add(queue1);
    }
    for (int i = 0; i < time; i++) {
        for (int j = 0; j < a.length; j++) {
            int x = a[j] % (int) Math.pow(10, i+1)/(int)Math.pow(10, i);
            ArrayList<Integer> queue2 = queue.get(x);
            queue2.add(a[j]);
            queue.set(x, queue2);
        }
        int count = 0;
        for (int k = 0; k < 10; k++) {
            while (queue.get(k).size()>0) {
                ArrayList<Integer> queue3 = queue.get(k);
                a[count] = queue3.get(0);
                queue3.remove(0);
                count++;
            }
        }
    }
}

（8）堆排序

1、簡介：

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

2、步驟：

将初始待排序關鍵字序列(R1,R2….Rn)建構成大頂堆，此堆為初始的無序區；
将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
由于交換後新的堆頂R[1]可能違反堆的性質，是以需要對目前無序區(R1,R2,……Rn-1)調整為新堆，然後再次将R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。

3、動圖：

Java 八種排序算法總結

4、代碼：

/**
* 堆排序
*/
public static void order8(int[] a) {
    int len = a.length;
    for (int i = 0; i < len - 1; i++) {
        buildMaxHeap(a,len - 1 - i);
        swap(a,0,len - 1 - i);
    }
}
	
private static void buildMaxHeap(int[] data, int lastIndex) {
    //從lastIndex處節點（最後一個節點）的父節點開始
    for (int i = (lastIndex - 1)/2; i >= 0; i--) {
        //k儲存正在判斷的節點
        int k = i ;
        //如果目前K節點的子節點存在
        while(k * 2 + 1 <= lastIndex) {
            //k節點的左子節點的索引
            int biggerIndex = 2 * k +1;
            //如果biggerIndex小于lastIndex,即biggerIndex +1代表的K節點的右子節點存在
            if(biggerIndex < lastIndex) {
                //如果右子節點的值較大
                if(data[biggerIndex] < data[biggerIndex + 1]) {
                    biggerIndex++;
                }
            }
            //如果K節點的值小于其較大的子節點的值
            if(data[k] < data[biggerIndex]) {
                //交換他們
                swap(data, k, biggerIndex);
                k = biggerIndex;
            } else {
                break;
            }
        }
    }
}
	
private static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

四、總結

場景應用：

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。

    　當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插人，應選直接選擇排序為宜。

(2)若檔案初始狀态基本有序(指正序)，則應選用直接插人、冒泡或随機的快速排序為宜；

(3)若n較大，則應采用時間複雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

    　快速排序是目前基于比較的内部排序中被認為是最好的方法，當待排序的關鍵字是随機分布時，快速排序的平均時間最短；

    　堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。

    　若要求排序穩定，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的排序算法并不值得提倡，通常可以将它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子檔案，然後再兩兩歸并之。因為直接插入排序是穩定的，是以改進後的歸并排序仍是穩定的。

果然算法很複雜，以我智商都有點不夠用。分析的我腦殼有點疼，實在扯不下去。就寫這麼多了。見諒。。。

Java 八種排序算法總結

轉存失敗重新上傳取消

Java 八種排序算法總結

五、Demo位址

https://github.com/DayorNight/JavaOrderingMethod

六、參考文檔

《Java資料結構與算法》

http://www.runoob.com/w3cnote/sort-algorithm-summary.html

https://jingyan.baidu.com/article/db55b609f856604ba30a2f18.html

https://blog.csdn.net/yushiyi6453/article/details/76407640

http://www.cnblogs.com/aoyihuashao/p/9453649.html

https://www.cnblogs.com/end/archive/2011/10/22/2220995.html

七、内容推薦

簡書：https://www.jianshu.com/p/a43bd0f44f65

《Java 設計模式總結》

《JAVA 設計模式——單例模式》

《Java 設計模式——工廠模式》

《Java 設計模式——觀察者模式》

《Java 設計模式——建造者模式》

如果你覺得我寫的不錯或者對您有所幫助的話

不妨頂一個【微笑】，别忘了點贊、收藏、加關注哈

您的每個舉動都是對我莫大的支援

Java 八種排序算法總結

Java 八種排序算法總結

前言

一、簡介

二、算法複雜度

三、常見算法

（1）冒泡排序

（2）選擇排序

（3）插入排序

（4）歸并排序

（5）快速排序

（6）希爾排序

（7）基數排序

（8）堆排序

四、總結

五、Demo位址

六、參考文檔

七、内容推薦

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希