一，普通排序

前言

為了面試，時隔一年不得不重新複習資料結構與算法，這次重新複習很有收獲，以前在上課總有不清晰的知識，通過這次手寫一遍和敲一遍代碼，以前不清晰的知識都變得清晰了，果然學程式設計還是得多敲代碼，多敲代碼，多敲代碼，也要多總結，多總結，多總結。

這個文章隻是總結筆記，有錯誤請指出，謝謝。

學習資源

視訊黑馬程式員資料結構于算法

Comparable接口

這裡要講排序，是以肯定會在元素之間進行比較，而Java提供了一個接口Comparable就是用來定義排序規則的,封裝類都實作了該接口，是以Integer等封裝類有排序規則，自定義的類也可以實作Comparable來擁有排序規則

冒泡排序

時間複雜度: O(N`2)

穩定性: 穩定

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。

需求

排序前：{4,5,6,3,2,1}

排序後：{1,2,3,4,5,6}

排序原理：

比較相鄰的元素。如果前一個元素比後一個元素大，就交換這兩個元素的位置。
對每一對相鄰元素做同樣的工作，從開始第一對元素到結尾的最後一對元素。最終最後位置的元素就是最大值。

import java.util.Arrays;

//冒泡排序 大的往後放（交換位置） 從0開始往後比較
//時間複雜度 O(N`2)
public class Bubble {

    //将數組a排序 a={4,5,6,3,2,1}
    public static void sort(Comparable[] a){
        //每次循環 忽略上次的 最後一位 4,5,6,3,2,1>4,5,3,2,1, 6 忽略6
        for(int i=a.length-1;i>0; i--){
            for(int j=0;i>j;j++){
                if(greater(a[j],a[j+1])){ //6,3 傳回true
                    exch(a,j,j+1); //6,3 3,6
                }
            }
        }
    }

    //比較v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0; //6-3>0 傳回true
    }

    //數組元素i和j交換  6,3
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //6
        a[i] = a[j]; //3
        a[j] = t; //6
    }

    //測試
    public static void main(String[] args) {
        //封裝類 Integer 已經實作Comparable接口 的比較規則
        Integer[] a={4,5,6,3,2,1};
        Bubble.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

選擇排序

時間複雜度: O(N`2)

穩定性: 不穩定

選擇排序是一種更加簡單直覺的排序方法。

需求：

排序前：{4,6,8,7,9,2,10,1}

排序後：{1,2,4,5,7,8,9,10}

排序原理：

每一次周遊的過程中，都假定第一個索引處的元素是最小值，和其他索引處的值依次進行比較，如果目前索引處的值大于其他某個索引處的值，則假定其他某個索引出的值為最小值，最後可以找到最小值所在的索引；
交換第一個索引處和最小值所在的索引處的值；

import java.util.Arrays;

//選擇排序
/*
1.假定目前索引的值是最小值 minIndex=i
2.往後比較 找到比目前的值小的索引，
3.則該索引為目前最小值  minIndex=j
4.重複這3個步驟，j<a.length 找到最小值
5.交換第一位和最小值得位置
 */
public class Selection {
    //将數組a排序 a={4,6,8,7,9,2,10,1}
    //如第一輪周遊找到 最小值1 1,6,8,7,9,2,10,4 忽略1 從後一位周遊
    //如第一輪周遊找到 最小值2 1,6,8,7,9,2,10,4 忽略2 從後一位周遊 ...
    public static void sort(Comparable[] a){
        for(int i=0;i<=a.length-2;i++){
            int minIndex = i; //假定目前索引的值是最小值
            //往後比較 找到比目前的值小的索引  j<a.length 找到最小值 1
            for(int j = i+1;j<=a.length-1;j++){
                if(greater(a[i],a[j])){ //4>2  2>1  則該索引為目前最小值  minIndex=j
                    minIndex = j;
                }
            }
            //目前第一位的4和目前的最小值1交換位置
            exch(a,i,minIndex); 
        }
    }

    //比較v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;  //4-2>0 2-1>0 傳回true
    }

    //數組元素i和j交換  4,1
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //4
        a[i] = a[j]; //1
        a[j] = t; //4
    }

    //測試
    public static void main(String[] args) {
        //封裝類 Integer 已經實作Comparable接口 的比較規則
        Integer[] a={4,6,8,7,9,2,10,1} ;
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

插入排序

時間複雜度: O(N`2)

穩定性: 穩定

插入排序（Insertion sort）是一種簡單直覺且穩定的排序算法。

插入排序的工作方式非常像人們排序一手撲克牌一樣。開始時，我們的左手為空并且桌子上的牌面朝下。然後，我們每次從桌子上拿走一張牌并将它插入左手中正确的位置。為了找到一張牌的正确位置，我們從右到左将它與已在手中的每張牌進行比較。

需求：

排序前：{4,3,2,10,12,1,5,6}

排序後：{1,2,3,4,5,6,10,12}

排序原理：

把所有的元素分為兩組，已經排序的和未排序的；
找到未排序的組中的第一個元素，向已經排序的組中進行插入；
倒叙周遊已經排序的元素，依次和待插入的元素進行比較，直到找到一個元素小于等于待插入元素，那麼就把待插入元素放到這個位置，其他的元素向後移動一位；

import java.util.Arrays;

//插入排序
/*
    循環,比較目前值和後一位比較，如果目前值比後一位大，則交換位置，否則位置不變,跳出循環
    {4,3,2,10,12,1,5,6}
    4>3大交換位置  4>2大交換位置 4<10 位置不變 10<12  位置不變  ...
 */
public class Insertion {
    //将數組a排序 a={4,3,2,10,12,1,5,6}
    public static void sort(Comparable[] a){
        for(int i=1;i<a.length;i++){
            for(int j=i;j>0;j--){
                if(greater(a[j-1],a[j])){ //目前值和後一位比較 4>3
                   exch(a,j-1,j);  //4,3 交換位置
                }else{
                    break; //否則，位置不變，跳出循環
                }
            }
        }
    }

    //比較v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0; //4-3>0 傳回true
    }

    //數組元素i和j交換  4,3
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //4
        a[i] = a[j]; //3
        a[j] = t; //4
    }

    //測試
    public static void main(String[] args) {
        //封裝類 Integer 已經實作Comparable接口 的比較規則
        Integer[] a={4,3,2,10,12,1,5,6} ;
        Insertion.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

二，進階排序

希爾排序

時間複雜度: O(n^s) ,1<s<2

穩定性:不穩定

希爾排序是插入排序的一種，又稱“縮小增量排序”，是插入排序算法的一種更高效的改進版本。

需求：

排序前：{9,1,2,5,7,4,8,6,3,5}

排序後：{1,2,3,4,5,5,6,7,8,9}

排序原理：

標明一個增長量h，按照增長量h作為資料分組的依據，對資料進行分組；
對分好組的每一組資料完成插入排序；
減小增長量，最小減為1，重複第二步操作。

資料結構與算法——排序算法一，普通排序二，進階排序

package com.mai.myAlgorithm.sort;
//希爾排序

import java.util.Arrays;

public class Shell1 {

    //對數組a中的元素進行排序 a={9,1,2,5,7,4,8,6,3,5}
    public static void sort(Comparable[] a){
        //1.根據數組a的長度，确定增長量h的初始值；
        int h = a.length/2;

        /* 
           第一次循環 h=5 索引 0 和 5 1和 6 2和 7... 比較 如果後面小于前面 則交換位置
           第二次循環 h=2 索引 0 和 2 1 和 3  2 和 4... 比較 如果後面小于前面 則交換位置
           第三次循環 h=1 索引 0 和 1 1 和 2  2 和 3... 比較 如果後面小于前面 則交換位置
        */
        while (h>=1) {
            for (int j = 0; j < a.length - h; j++) { //10-5 =5 10-2=8 10-1=9
                //  0 和 5 1和 6 2和 7... 比較 9>4 傳回true 1<8 false
                if (greater(a[j], a[j + h])) { 
                    exch(a, j, j + h);  //交換
                }
            }
            h = h / 2; //減小h的值 5 2 1
        }
    }

    //比較v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0; //9-4>0 傳回true 1-8 傳回false
    }

    //數組元素i和j交換  9,4
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //9
        a[i] = a[j]; //4
        a[j] = t; //9
    }
    
    //測試
    public static void main(String[] args) {
        //封裝類 Integer 已經實作Comparable接口 的比較規則
        Integer[] a={9,1,2,5,7,4,8,6,3,5};
        Shell1.sort(a);
        System.out.println(a.length);
        System.out.println(Arrays.toString(a));
    }

}

歸并排序

時間複雜度: O(nlogn)

穩定性:穩定

歸并排序需要額外的數組空間

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。

需求：

排序前：{8,4,5,7,1,3,6,2}

排序後：{1,2,3,4,5,6,7,8}

排序原理：

1.盡可能的一組資料拆分成兩個元素相等的子組，并對每一個子組繼續拆分，直到拆分後的每個子組的元素個數是1為止。

2.将相鄰的兩個子組進行合并成一個有序的大組；

3.不斷的重複步驟2，直到最終隻有一個組為止

資料結構與算法——排序算法一，普通排序二，進階排序

import java.util.Arrays;

//歸并排序
public class Merge {

    //輔助數組 歸并排序需要額外的數組空間
   private static Comparable[] assist;

    // 對數組a中的元素進行排序 a={8, 4, 5, 7, 1, 3, 6, 2};
    public static void sort(Comparable[] a){
        //初始化 輔助數組
        assist = new Comparable[a.length];
        int lo = 0;  //左指針
        int hi =a.length-1; //右指針

        //調用sort重載方法完成數組a中，從索引lo到索引hi的元素的排序（整個數組排序）
        sort(a,lo,hi);

    }

    //對數組a中從lo到hi的元素進行排序  a={8, 4, 5, 7, 1, 3, 6, 2}
    private static void sort(Comparable[] a,int lo,int hi){
        //做安全性校驗；
        if(hi<=lo){
            return;
        }
        //對lo到hi之間的資料進行分為兩個組 分組
        int mid = lo + (hi-lo)/2;  //mid 0+(7-0)/2 = 3

        //分别對每一組資料進行 排序 （遞歸）
        /*
        第一次左邊的數組 8, 4, 5, 7
        第二次  左邊的數組 8, 4, 右邊的 5, 7
        第三次 ...
        */
        sort(a,lo,mid);
        sort(a,mid+1,hi); //右邊的數組 1, 3, 6, 2 同左邊的一樣分組

        //再把兩個組中的資料進行歸并 合并
        merge(a,lo,mid,hi);

    }

    // 對數組中，從lo到mid為一組，從mid+1到hi為一組，對這兩組資料進行歸并
    private static void merge(Comparable[] a,int lo,int mid, int hi){
        //定義三個指針
        int i = lo; //輔助數組下标
        int p1=lo; //輔助數組左指針 0 -> 1 2 3 
        int p2=mid+1; //輔助數組中間往右的指針 4-> 5 6 7

        //周遊，移動p1指針和p2指針，比較對應索引處的值，找出小的那個，放到輔助數組的對應索引處
        /*
            a={8, 4, 5, 7, 1, 3, 6, 2}
            最後一步合并的兩組 4578 和 1236
            i=0  p1=0 p2=4 hi=7
            i++ 先複值再自增
         */
        while (p1<=mid && p2<=hi){
            //a[0]=4>a[4]=1 false 4>2 false 4>3 false 4<6 true  5<6 true 7>6 false
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];  //4<6 4 5
            }else{
                assist[i++] = a[p2++]; //assist[0]=a[4]=1 2 3 6 右邊的數組走完了 退出循環
            }
        }

        //周遊，如果左邊的數組沒有走完，那麼順序移動p1指針，把對應的元素放到輔助數組的對應索引處
        while (p1<=mid){
            assist[i++] = a[p1++];
        }

        //周遊，如果右邊邊的數組沒有走完，那麼順序移動p2指針，把對應的元素放到輔助數組的對應索引處
        while (p2<=hi){
            assist[i++] = a[p2++];
        }

        //把輔助數組中的元素拷貝到原數組中
        for(int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }

    }

    //比較v元素是否小于w元素 4-1>0 傳回false
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w)<0; 
    }

    //測試
    public static void main(String[] args) {
        //封裝類 Integer 已經實作Comparable接口 的比較規則
        Integer[] a = {8, 4, 5, 7, 1, 3, 6, 2};
        Merge.sort(a);
        System.out.println(a.length);
        System.out.println(Arrays.toString(a));
    }
}

快速排序

時間複雜度

最優時間複雜度: O(nlogn)

最壞時間複雜度: O(N`2)

平均時間複雜度: O(nlogn)

穩定性: 不穩定

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

需求：

排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}

排序後:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理：

首先設定一個分界值，通過該分界值将數組分成左右兩部分；
将大于或等于分界值的資料放到到數組右邊，小于分界值的資料放到數組的左邊。此時左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值；
然後，左邊和右邊的資料可以獨立排序。對于左側的數組資料，又可以取一個分界值，将該部分資料分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組資料也可以做類似處理。
重複上述過程，可以看出，這是一個遞歸定義。通過遞歸将左側部分排好序後，再遞歸排好右側部分的順序。當左側和右側兩個部分的資料排完序後，整個數組的排序也就完成了。

資料結構與算法——排序算法一，普通排序二，進階排序

切分原理：

把一個數組切分成兩個子數組的基本思想：

找一個基準值，用兩個指針分别指向數組的頭部和尾部；
先從尾部向頭部開始搜尋一個比基準值小的元素，搜尋到即停止，并記錄指針的位置；
再從頭部向尾部開始搜尋一個比基準值大的元素，搜尋到即停止，并記錄指針的位置；
交換目前左邊指針位置和右邊指針位置的元素；
重複2,3,4步驟，直到左邊指針的值大于右邊指針的值停止。

import java.util.Arrays;

//快速排序
public class Quick {

    //對數組内的元素進行排序 a={6, 1, 2, 7, 9, 3, 4, 5, 8}
    public static void sort(Comparable[] a){
        //定義數組的左右指針調用重載的sort方法排序整個數組
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);

    }

    //對數組a中從索引lo到索引hi之間的元素進行排序 ,先分組，再排序
    private static void sort(Comparable[] a,int lo,int hi){
        //安全性校驗
        if(hi<=lo){
            return;
        }

        //需要對數組中lo索引到hi索引處的元素進行分組（左子組和右子組）；
        int partition = partition(a,lo,hi); //傳回的是分組的分界值所在的索引，分界值位置變換後的索引

        //讓左子組有序
        sort(a,lo,partition-1);  // partition = 5 2

        //讓右子組有序
        sort(a,partition+1,hi); // partition =  5 7

    }

    // a={6, 1, 2, 7, 9, 3, 4, 5, 8}
    //對數組a中，從索引 lo到索引 hi之間的元素進行分組，并傳回分組界限對應的索引
    private static int partition(Comparable[] a,int lo,int hi){
        //确定分界值
        Comparable key = a[lo];  // a[0]=6

        //定義兩個指針，分别指向待切分元素的最小索引處和最大索引處的下一個位置
        int left = lo ; //0
        int right = hi+1; //9

        //++i 先自增再複值

        //切分
        while(true) {
            //先從右往左掃描，移動right指針，找到一個比分界值小的元素，停止退出循環
            while (less(key, a[--right])) {  //6-8 key-a[--right]>=0 false 退出循環
                if (right == lo) {  // 安全性校驗 安心左右指針相遇，退出循環
                    break;
                }
            }

            //再從左往右掃描，移動left指針，找到一個比分界值大的元素，停止退出循環
            while (less(a[++left], key)) { //1-6 key-a[--right]<0  2-6  true  7-6  false 退出循環
                if (left == hi) {  //安全性校驗 左右指針相遇，退出循環
                    break;
                }
            }
            //判斷 left>=right,如果是，則證明元素掃描完畢，結束循環，如果不是，則交換元素即可
            if (left >= right) {
                break;
            } else {
                exch(a, left, right);
            }
        }

        //交換分界值
        exch(a,lo,right);

        return right; //傳回值

    }


    //比較v元素是否小于w元素1-6<0 true
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w)<0; 
    }

    //數組元素i和j交換
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; 
        a[i] = a[j]; 
        a[j] = t; 
    }


    //測試
    public static void main(String[] args) {
        //封裝類 Integer 已經實作Comparable接口 的比較規則
        Integer[] a = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

資料結構與算法——排序算法一，普通排序二，進階排序

一，普通排序

前言

Comparable接口

冒泡排序

選擇排序

插入排序

二，進階排序

希爾排序

歸并排序

快速排序

後續文章連結

資料結構與算法——順序表

繼續閱讀

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

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希