1、冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法委刘。它重復地走訪過要排序的數(shù)列丧没，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來锡移。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換呕童，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端淆珊。

1.1算法描述

• 比較相鄰的元素夺饲。如果第一個比第二個大，就交換它們兩個施符；
• 對每一對相鄰元素作同樣的工作往声，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數(shù)戳吝；
• 針對所有的元素重復以上的步驟浩销，除了最后一個；
• 重復步驟1~3听哭，直到排序完成慢洋。

1.2動圖演示

image

1.3代碼實現(xiàn)

    /**
     * 冒泡排序
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        if (array.length == 0)
            return array;
        for (int i = 0; i < array.length; i++)
            for (int j = 0; j < array.length - 1 - i; j++)
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
        return array;
    }

1.4算法分析

最佳情況：T(n) = O(n) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

2塘雳、選擇排序（Selection Sort）

表現(xiàn)最穩(wěn)定的排序算法之一，因為無論什么數(shù)據(jù)進去都是O(n2)的時間復雜度且警，所以用到它的時候粉捻，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧斑芜。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧祟霍。

選擇排序(Selection-sort)是一種簡單直觀的排序算法杏头。它的工作原理：首先在未排序序列中找到最小（大）元素沸呐，存放到排序序列的起始位置懦窘，然后奸攻，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾裆悄。以此類推，直到所有元素均排序完畢蔑祟。

2.1 算法描述

• n個記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結果晌区。具體算法描述如下：
  初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空屁置；
• 第i趟排序(i=1,2,3…n-1)開始時焊夸，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區(qū)中-選出關鍵字最小的記錄 R[k]蓝角，將它與無序區(qū)的第1個記錄R交換阱穗，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；
• n-1趟結束使鹅，數(shù)組有序化了揪阶。

2.2 動圖演示

image

2.3 代碼實現(xiàn)

    /**
     * 選擇排序
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
        if (array.length == 0)
            return array;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) //找到最小的數(shù)
                    minIndex = j; //將最小數(shù)的索引保存
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

2.4 算法分析

最佳情況：T(n) = O(n2) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法患朱。它的工作原理是通過構建有序序列鲁僚，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描麦乞，找到相應位置并插入蕴茴。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序）姐直，因而在從后向前掃描過程中倦淀，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間声畏。

3.1 算法描述

• 一般來說撞叽，插入排序都采用in-place在數(shù)組上實現(xiàn)姻成。具體算法描述如下：
• 從第一個元素開始，該元素可以認為已經(jīng)被排序愿棋；
• 取出下一個元素科展，在已經(jīng)排序的元素序列中從后向前掃描；
• 如果該元素（已排序）大于新元素糠雨，將該元素移到下一位置才睹；
• 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置甘邀；
• 將新元素插入到該位置后琅攘；
• 重復步驟2~5。

3.2 動圖演示

image

    /**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }

3.4 算法分析

最佳情況：T(n) = O(n) 最壞情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

4松邪、希爾排序（Shell Sort）

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法坞琴。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進之后的一個更高效的版本逗抑，也稱為縮小增量排序剧辐，同時該算法是沖破O(n2）的第一批算法之一。它與插入排序的不同之處在于邮府，它會優(yōu)先比較距離較遠的元素荧关。希爾排序又叫縮小增量排序。

希爾排序是把記錄按下表的一定增量分組挟纱，對每組使用直接插入排序算法排序羞酗；隨著增量逐漸減少，每組包含的關鍵詞越來越多紊服，當增量減至1時檀轨，整個文件恰被分成一組，算法便終止欺嗤。

4.1 算法描述
我們來看下希爾排序的基本步驟参萄，在此我們選擇增量gap=length/2，縮小增量繼續(xù)以gap = gap/2的方式煎饼，這種增量選擇我們可以用一個序列來表示讹挎，{n/2,(n/2)/2...1}，稱為增量序列吆玖。希爾排序的增量序列的選擇與證明是個數(shù)學難題筒溃，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量沾乘，稱為希爾增量翅阵，但其實這個增量序列不是最優(yōu)的。此處我們做示例使用希爾增量。

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序蜂科，具體算法描述：

• 選擇一個增量序列t1，t2，…屹蚊，tk，其中ti>tj嘱兼，tk=1芹壕；
• 按增量序列個數(shù)k踢涌，對序列進行k 趟排序睁壁；
• 每趟排序潘明，根據(jù)對應的增量ti钳降，將待排序列分割成若干長度為m 的子序列固阁，分別對各子表進行直接插入排序。僅增量因子為1 時并齐，整個序列作為一個表來處理，表長度即為整個序列的長度测垛。

4.2 過程演示

image

4.3 代碼實現(xiàn)

    /**
     * 希爾排序
     *
     * @param array
     * @return
     */
    public static int[] ShellSort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return array;
    }

4.4 算法分析
最佳情況：T(n) = O(nlog2 n) 最壞情況：T(n) = O(nlog2 n) 平均情況：T(n) =O(nlog2n)

5秧均、歸并排序（Merge Sort）

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響目胡，但表現(xiàn)比選擇排序好的多，因為始終都是O(n log n）的時間復雜度誉己。代價是需要額外的內(nèi)存空間眉尸。

歸并排序是建立在歸并操作上的一種有效的排序算法巨双。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用噪猾。歸并排序是一種穩(wěn)定的排序方法炉峰。將已有序的子序列合并疼阔，得到完全有序的序列；即先使每個子序列有序淘邻，再使子序列段間有序统阿。若將兩個有序表合并成一個有序表彩倚，稱為2-路歸并。

5.1 算法描述

image

5.3 代碼實現(xiàn)

/**
     * 歸并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 歸并排序——將兩段排序好的數(shù)組結合成一個排序數(shù)組
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }

5. 4 算法分析

最佳情況：T(n) = O(n) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)

6扶平、快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠址耄渲幸徊糠钟涗浀年P鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序结澄，以達到整個序列有序哥谷。

6.1 算法描述

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

• 從數(shù)列中挑出一個元素麻献，稱為 “基準”（pivot）们妥；
• 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面勉吻，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）监婶。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置齿桃。這個稱為分區(qū)（partition）操作压储；
• 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

6.2 動圖演示

image

6.3 代碼實現(xiàn)

/**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] QuickSort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start)
            QuickSort(array, start, smallIndex - 1);
        if (smallIndex < end)
            QuickSort(array, smallIndex + 1, end);
        return array;
    }
    /**
     * 快速排序算法——partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++)
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex)
                    swap(array, i, smallIndex);
            }
        return smallIndex;
    }

    /**
     * 交換數(shù)組內(nèi)兩個元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

6.4 算法分析

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)

7源譬、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構孕似，并同時滿足堆積的性質(zhì)：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點踩娘。

7.1 算法描述

• 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區(qū)喉祭；
• 將堆頂元素R[1]與最后一個元素R[n]交換养渴，此時得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
• 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)泛烙，因此需要對當前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆理卑，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)蔽氨。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1藐唠，則整個排序過程完成。

7.2 動圖演示

image

7.3 代碼實現(xiàn)

注意：這里用到了完全二叉樹的部分性質(zhì)：詳情見《數(shù)據(jù)結構二叉樹知識點總結》

//聲明全局變量鹉究，用于記錄數(shù)組array的長度宇立；
static int len;
    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len < 1) return array;
        //1.構建一個最大堆
        buildMaxHeap(array);
        //2.循環(huán)將堆首位（最大值）與末位交換，然后在重新調(diào)整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }
    /**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
        //從最后一個非葉子節(jié)點開始向上構造最大堆
        for (int i = (len/2 - 1); i >= 0; i--) { //感謝 @讓我發(fā)會呆 網(wǎng)友的提醒自赔，此處應該為 i = (len/2 - 1) 
            adjustHeap(array, i);
        }
    }
    /**
     * 調(diào)整使之成為最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子樹妈嘹，且左子樹大于父節(jié)點，則將最大指針指向左子樹
        if (i * 2 < len && array[i * 2] > array[maxIndex])
            maxIndex = i * 2;
        //如果有右子樹绍妨，且右子樹大于父節(jié)點润脸，則將最大指針指向右子樹
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
            maxIndex = i * 2 + 1;
        //如果父節(jié)點不是最大值柬脸，則將父節(jié)點與最大值交換，并且遞歸調(diào)整與父節(jié)點交換的位置毙驯。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }

7.4 算法分析

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)