1概述

本文對比較常用且比較高效的排序算法進行了總結和解析，并貼出了比較精簡的實現代碼，包括選擇排序、插入排序、歸并排序、希爾排序、快速排序等。算法性能比較如下圖所示：

2選擇排序

選擇排序的第一趟處理是從數據序列所有n個數據中選擇一個最小的數據作為有序序列中的第1個元素并將它定位在第一號存儲位置，第二趟處理從數據序列的n-1個數據中選擇一個第二小的元素作為有序序列中的第2個元素并將它定位在第二號存儲位置，依此類推，當第n-1趟處理從數據序列的剩下的2個元素中選擇一個較小的元素作為有序序列中的最后第2個元素并將它定位在倒數第二號存儲位置，至此，整個的排序處理過程就已完成。

代碼如下：

public class SelectionSort {    public void selectionSort(int[] array) {        int temp;        for (int i = 0; i < array.length - 1; i++) {            for (int j = i + 1; j <= array.length - 1; j++) {// 第i個和第j個比較j可以取到最后一位，所以要用j<=array.length-1                if (array[i] > array[j]) {// 注意和冒泡排序的區別，這里是i和j比較。                    temp = array[i];                    array[i] = array[j];                    array[j] = temp;                }            }            // 打印每趟排序結果            for (int m = 0; m <= array.length - 1; m++) {                System.out.PRint(array[m] + "/t");            }            System.out.println();        }    }      public static void main(String[] args) {        SelectionSort selectionSort = new SelectionSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        selectionSort.selectionSort(array);        for (int m = 0; m <= array.length - 1; m++) {            System.out.print(array[m] + "/t");        }    }}

3插入排序

直接插入排序法的排序原則是：將一組無序的數字排列成一排，左端第一個數字為已經完成排序的數字，其他數字為未排序的數字。然后從左到右依次將未排序的數字插入到已排序的數字中。

代碼如下：

public class InsertSort {    public void insertSort(int[] array, int first, int last) {        int temp, i, j;        for (i = first + 1; i <= last - 1; i++) {// 默認以第一個數為有序序列，后面的數為要插入的數。            temp = array[i];            j = i - 1;            while (j >= first && array[j] > temp) {// 從后進行搜索如果搜索到的數小于temp則該數后移繼續搜索，直到搜索到小于或等于temp的數即可                array[j + 1] = array[j];                j--;            }            array[j + 1] = temp;            // 打印每次排序結果            for (int m = 0; m <= array.length - 1; m++) {                System.out.print(array[m] + "/t");            }            System.out.println();        }    }      public static void main(String[] args) {        InsertSort insertSort = new InsertSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        insertSort.insertSort(array, 0, array.length);// 注意此處是0-9而不是0-8        for (int i = 0; i <= array.length - 1; i++) {            System.out.print(array[i] + "/t");        }    }}

4 歸并排序

算法描述：

把序列分成元素盡可能相等的兩半。

把兩半元素分別進行排序。

把兩個有序表合并成一個。

代碼如下：

public class MergeSortTest {    public void sort(int[] array, int left, int right) {        if (left >= right)            return;        // 找出中間索引        int center = (left + right) / 2;        // 對左邊數組進行遞歸        sort(array, left, center);        // 對右邊數組進行遞歸        sort(array, center + 1, right);        // 合并        merge(array, left, center, right);        // 打印每次排序結果        for (int i = 0; i < array.length; i++) {            System.out.print(array[i] + "/t");        }        System.out.println();      }      /**     * 將兩個數組進行歸并，歸并前面2個數組已有序，歸并后依然有序     *      * @param array     *            數組對象     * @param left     *            左數組的第一個元素的索引     * @param center     *            左數組的最后一個元素的索引，center+1是右數組第一個元素的索引     * @param right     *            右數組最后一個元素的索引     */    public void merge(int[] array, int left, int center, int right) {        // 臨時數組        int[] tmpArr = new int[array.length];        // 右數組第一個元素索引        int mid = center + 1;        // third 記錄臨時數組的索引        int third = left;        // 緩存左數組第一個元素的索引        int tmp = left;        while (left <= center && mid <= right) {            // 從兩個數組中取出最小的放入臨時數組            if (array[left] <= array[mid]) {                tmpArr[third++] = array[left++];            } else {                tmpArr[third++] = array[mid++];            }        }        // 剩余部分依次放入臨時數組（實際上兩個while只會執行其中一個）        while (mid <= right) {            tmpArr[third++] = array[mid++];        }        while (left <= center) {            tmpArr[third++] = array[left++];        }        // 將臨時數組中的內容拷貝回原數組中        // （原left-right范圍的內容被復制回原數組）        while (tmp <= right) {            array[tmp] = tmpArr[tmp++];        }    }      public static void main(String[] args) {        int[] array = new int[] { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        MergeSortTest mergeSortTest = new MergeSortTest();        mergeSortTest.sort(array, 0, array.length - 1);        System.out.println("排序后的數組：");        for (int m = 0; m <= array.length - 1; m++) {            System.out.print(array[m] + "/t");        }    }}

5希爾排序

希爾排序又稱“縮小增量排序”，該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某 個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插 入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。

代碼如下：

public class ShellSort {    public void shellSort(int[] array, int n) {        int i, j, gap;        int temp;        for (gap = n / 2; gap > 0; gap /= 2) {// 計算gap大小            for (i = gap; i < n; i++) {// 將數據進行分組                for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {// 對每組數據進行插入排序                    temp = array[j];                    array[j] = array[j + gap];                    array[j + gap] = temp;                }                // 打印每趟排序結果                for (int m = 0; m <= array.length - 1; m++) {                    System.out.print(array[m] + "/t");                }                System.out.println();            }        }    }      public static void main(String[] args) {        ShellSort shellSort = new ShellSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        shellSort.shellSort(array, array.length);// 注意為數組的個數        for (int m = 0; m <= array.length - 1; m++) {            System.out.print(array[m] + "/t");        }    }}

6快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然 后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

代碼如下：

public class QuickSort {    public int partition(int[] sortArray, int low, int height) {        int key = sortArray[low];// 剛開始以第一個數為標志數據        while (low < height) {            while (low < height && sortArray[height] >= key)                height--;// 從后面開始找，找到比key值小的數為止            sortArray[low] = sortArray[height];// 將該數放到key值的左邊            while (low < height && sortArray[low] <= key)                low++;// 從前面開始找，找到比key值大的數為止            sortArray[height] = sortArray[low];// 將該數放到key值的右邊        }        sortArray[low] = key;// 把key值填充到low位置，下次重新找key值        // 打印每次排序結果        for (int i = 0; i <= sortArray.length - 1; i++) {            System.out.print(sortArray[i] + "/t");        }        System.out.println();        return low;    }      public void sort(int[] sortArray, int low, int height) {        if (low < height) {            int result = partition(sortArray, low, height);            sort(sortArray, low, result - 1);            sort(sortArray, result + 1, height);        }    }      public static void main(String[] args) {        QuickSort quickSort = new QuickSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        for (int i = 0; i <= array.length - 1; i++) {            System.out.print(array[i] + "/t");        }        System.out.println();        quickSort.sort(array, 0, 8);        for (int i = 0; i <= array.length - 1; i++) {            System.out.print(array[i] + "/t");        }    }}

　　這里只貼出了自己總結的部分排序算法，更多的算法總結可參考自己另外一篇文章：java自學之道

　　原創文章歡迎轉載，轉載時請注明出處。

　　作者推薦文章：

　　　　》Java自學之道

　　　　》Eclipse中部署Hadoop2.3.0并直接在Eclipse中提交mapreduce任務

　　　　》Java如何獲取系統信息（包括操作系統、jvm、cpu、內存、硬盤、網絡等）

　　　　》Java如何生成二維碼過程詳解