必須知道的排序算法—Java實(shí)現(xiàn)

1 冒泡排序

冒泡排序是一種簡(jiǎn)單的排序算法揩局。它重復(fù)地走訪過要排序的數(shù)列田盈，一次比較兩個(gè)元素败徊，如果他們的順序錯(cuò)誤就把他們交換過來谴古。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換智政，也就是說該數(shù)列已經(jīng)排序完成认罩。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

冒泡排序動(dòng)畫演示

冒泡排序的算法實(shí)現(xiàn)如下:

/**
 * 冒泡排序
 * 比較相鄰的元素女仰。如果第一個(gè)比第二個(gè)大猜年，就交換他們兩個(gè)。
 * 對(duì)每一對(duì)相鄰元素作同樣的工作疾忍，從開始第一對(duì)到結(jié)尾的最后一對(duì)乔外。
 * 在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)一罩。
 *
 * 針對(duì)所有的元素重復(fù)以上的步驟杨幼，除了最后一個(gè)。
 * 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟聂渊，直到?jīng)]有任何一對(duì)數(shù)字需要比較差购。
 * @param numbers 需要排序的整型數(shù)組
 */
public static void bubbleSort(int[] numbers)
{
    int temp = 0;
    int size = numbers.length;
    for(int i = 0 ; i < size-1; i ++)
    {
        for(int j = 0 ;j < size-1-i ; j++)
        {
            if(numbers[j] > numbers[j+1])   // 交換兩數(shù)位置
            {
                temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
            }
        }
    }
}

2 快速排序

快速排序的基本思想： 通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分關(guān)鍵字小汉嗽，則分別對(duì)這兩部分繼續(xù)進(jìn)行排序欲逃，直到整個(gè)序列有序。

快速排序動(dòng)畫演示

RANDOM QUICK SORT動(dòng)畫演示

快速排序的算法實(shí)現(xiàn)如下:

/**
 * 查找出中軸（默認(rèn)是最低位low）的在numbers數(shù)組排序后所在位置
 * @param numbers  待排序數(shù)組
 * @param low 開始位置
 * @param high 結(jié)束位置
 * @return 中軸所在位置
 */
public static int getMiddle(int[] numbers, int low,int high)
{
    int temp = numbers[low];  // 數(shù)組的第一個(gè)作為中軸
    while(low < high)
    {
        while(low < high && numbers[high] > temp)
        {
            high--;
        }

        numbers[low] = numbers[high];   // 比中軸小的記錄移到低端

        while(low < high && numbers[low] < temp)
        {
            low++;
        }

        numbers[high] = numbers[low] ;  // 比中軸大的記錄移到高端
    }

    numbers[low] = temp ; // 中軸記錄到尾
    return low ;          // 返回中軸的位置
}


/**
 * 遞歸形式的分治排序算法
 * @param numbers 待排序數(shù)組
 * @param low  開始位置
 * @param high 結(jié)束位置
 */
public static void quickSort(int[] numbers,int low,int high) {
    if(low < high) {
        int middle = getMiddle(numbers,low,high);  // 將numbers數(shù)組進(jìn)行一分為二
        quickSort(numbers, low, middle-1);   // 對(duì)低字段表進(jìn)行遞歸排序
        quickSort(numbers, middle+1, high);   // 對(duì)高字段表進(jìn)行遞歸排序
    }
}

/**
 * 快速排序提供方法調(diào)用
 * @param numbers 待排序數(shù)組
 */
public static void quick(int[] numbers) {
    // 查看數(shù)組是否為空
    if(numbers.length > 0) {
        quickSort(numbers, 0, numbers.length-1);
    }
}

3 選擇排序

基本思想：在要排序的一組數(shù)中饼暑，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換稳析；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止弓叛。

選擇排序動(dòng)畫演示

算法實(shí)現(xiàn)

/**
 * 選擇排序算法
 * 在未排序序列中找到最小元素彰居，存放到排序序列的起始位置;
 * 再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾撰筷。
 * 以此類推陈惰，直到所有元素均排序完畢。
 * @param numbers
 */
public static void selectSort(int[] numbers) {

    int size = numbers.length; // 數(shù)組長(zhǎng)度
    int temp = 0 ;             // 中間變量

    for(int i = 0 ; i < size ; i++) {
        int k = i;   // 待確定的位置

        // 選擇出應(yīng)該在第i個(gè)位置的數(shù)
        for(int j = size -1 ; j > i ; j--) {
            if(numbers[j] < numbers[k]) {
                k = j;
            }
        }

        // 交換兩個(gè)數(shù)
        temp = numbers[i];
        numbers[i] = numbers[k];
        numbers[k] = temp;

    }
}

4 堆排序

堆排序（Heap Sort）是由J.Williams在1964年提出的毕籽，它是在選擇排序的基礎(chǔ)上發(fā)展起來的抬闯，比選擇排序的效率要高，因此也可以說堆排序是選擇排序的升級(jí)版影钉。堆排序除了是一種排序方法外画髓，還涉及到方法之外的一些概念：堆和完全二叉樹。這里主要說說什么是堆平委？
如果將堆看成一棵完全二叉樹奈虾，則這棵完全二叉樹中的每個(gè)非葉子節(jié)點(diǎn)的值均不大于（或不小于）其左、右孩子節(jié)點(diǎn)的值。由此可知肉微，若一棵完全二叉樹是堆匾鸥，則根節(jié)點(diǎn)一定是這棵樹的所有節(jié)點(diǎn)的最小元素或最大元素。非葉子節(jié)點(diǎn)的值大于其左碉纳、右孩子節(jié)點(diǎn)的值的堆稱為大根堆勿负，反之則稱為下小根堆。

堆排序動(dòng)畫演示

算法實(shí)現(xiàn)

/**
 * 構(gòu)建大頂堆
 * @param R
 * @param low
 * @param high
 */
public static void sift(int[] R,int low,int high) {
    int i=low,j=i*2;
    int temp = R[i];
    while(j<=high) {
        if(j<high&&R[j]<R[j+1]) {
            j++;
        }
        if(temp<R[j]) {
            R[i]=R[j];
            i=j;
            j=2*i;
        } else {
            break;
        }
    }
    R[i]=temp;
}

/**
 * 堆排序
 * @param R
 */
public static void heapSort(int[] R) {
    int i,j;
    int n = R.length-1;
    int temp;
    for(i=n/2;i>=1;--i) { //初始化（大根）堆
        sift(R,i,n);
    }

    // 堆排序
    for(j=n;j>=2;j--) {
        temp=R[1];
        R[1]=R[j];
        R[j]=temp;
        sift(R,1,j-1);
    }
}

5 插入排序

基本思想：每步將一個(gè)待排序的記錄劳曹，按其順序碼大小插入到前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后）奴愉，直到全部插入排序完為止。

插入排序動(dòng)畫演示

算法實(shí)現(xiàn)

/**
 * 插入排序
 *
 * 從第一個(gè)元素開始铁孵，該元素可以認(rèn)為已經(jīng)被排序
 * 取出下一個(gè)元素锭硼，在已經(jīng)排序的元素序列中從后向前掃描
 * 如果該元素（已排序）大于新元素，將該元素移到下一位置
 * 重復(fù)步驟3蜕劝，直到找到已排序的元素小于或者等于新元素的位置
 * 將新元素插入到該位置中
 * 重復(fù)步驟2
 * @param numbers 待排序數(shù)組
 */
public static void insertSort(int[] numbers) {
    int size = numbers.length;
    int temp = 0 ;
    int j =  0;

    for(int i = 0 ; i < size ; i++) {
        temp = numbers[i];
        // 假如temp比前面的值小檀头，則將前面的值后移
        for(j = i ; j > 0 && temp < numbers[j-1] ; j --) {
            numbers[j] = numbers[j-1];
        }
        numbers[j] = temp;
    }
}

6 希爾排序

希爾排序是D.L.Shell于1959年提出來的一種排序算法，在這之前排序算法的時(shí)間復(fù)雜度基本都是O(n *n)的岖沛，希爾排序算法是突破這個(gè)時(shí)間復(fù)雜度的第一批算法之一暑始，它是直接插入排序的升級(jí)版。希爾排序的基本思想是：將待排序的記錄分成幾組婴削，從而減少參與直接插入排序的數(shù)據(jù)量廊镜，當(dāng)經(jīng)過幾次分組之后，記錄的排列已經(jīng)基本有序唉俗，這時(shí)再對(duì)所有記錄實(shí)施直接插入排序期升。

希爾排序的主要特點(diǎn)是排序的每一趟均以不同的間隔數(shù)對(duì)子序列進(jìn)行排序，當(dāng)間隔數(shù)很大時(shí)互躬，被移動(dòng)的元素是以跳躍式進(jìn)行的。而當(dāng)間隔數(shù)=1時(shí)颂郎，序列則幾乎已經(jīng)有序吼渡，只需要進(jìn)行很少的元素移動(dòng)，就能最終達(dá)到排序的目的乓序。

希爾排序動(dòng)畫演示

算法實(shí)現(xiàn)

 /**
 *
 * 希爾排序是加強(qiáng)版的插入排序
 *
 * 希爾排序的原理:
 * 根據(jù)需求替劈，如果你想要結(jié)果從大到小排列，它會(huì)首先將數(shù)組進(jìn)行分組陨献，然后將較大值移到前面盒犹，較小值
 * 移到后面，最后將整個(gè)數(shù)組進(jìn)行插入排序急膀，
 * 這樣比起一開始就用插入排序減少了數(shù)據(jù)交換和移動(dòng)的次數(shù)，可以說希爾排序是加強(qiáng)版的插入排序
 * 拿數(shù)組5, 2, 8, 9, 1, 3卓嫂，4來說慷暂，數(shù)組長(zhǎng)度為7晨雳，當(dāng)increment為3時(shí)，數(shù)組分為兩個(gè)序列
 * 5血久，2坠宴，8和9，1副砍，3庄岖，4隅忿，第一次排序，9和5比較优烧，1和2比較链峭，3和8比較，
 * 4和比其下標(biāo)值小increment的數(shù)組值相比較
 * 此例子是按照從大到小排列熙卡，所以大的會(huì)排在前面励饵，第一次排序后數(shù)組為9, 2, 8, 5, 1, 3役听，4
 * 第一次后increment的值變?yōu)?/2=1,此時(shí)對(duì)數(shù)組進(jìn)行插入排序表窘，
 * 實(shí)現(xiàn)數(shù)組從大到小排
 */
public static void shellSort01(int[] data) {
    int j = 0;
    int temp = 0;

    // 每次將步長(zhǎng)縮短為原來的一半
    for (int increment = data.length / 2; increment > 0; increment /= 2) {
        for (int i = increment; i < data.length; i++) {
            temp = data[i];

            for (j = i; j >= increment; j -= increment) {

                /**
                 * 如想從小到大排只需修改這里
                if(temp > data[j - increment]) {

                    data[j] = data[j - increment];
                }
                else {
                    break;
                }
                 */

                if (temp < data[j]) {
                    data[j + increment] = data[j];
                } else {
                    break;
                }

            }
            data[j] = temp;
        }
    }
}

/**
 * 希爾排序
 * @param arr
 */
public static void shellSort02(int[] arr) {
    int j;
    int len = arr.length;
    for(int val=len>>1; val>0; val>>=1) {
        // 下面是對(duì)本次的所有分組做直接插入排序
        for(int i=val; i<len; i++) {

            /**
             * 為什么每次都用temp比較呢蚊丐？
             * 因?yàn)橹苯硬迦刖褪钦业絫emp的合適位置麦备。
             * 為什么temp<arr[j-val]這個(gè)條件可以放在for內(nèi)呢昭娩？
             * 因?yàn)樵瓉淼慕M內(nèi)數(shù)據(jù)已經(jīng)有序栏渺，找到位置就停止便是。
             * 不甚理解的去看直接插入排序吧填物。
             */
            int temp = arr[i];

            for(j=i; j>=val&&temp<arr[j-val]; j-=val) {

                /**
                 * 為什么是arr[j-val]不是arr[j]呢霎终？
                 * 因?yàn)閖=i開始的莱褒，而且條件是j>=val&&temp<arr[j-val]
                 */
                arr[j] = arr[j-val];
            }

            /**
             * 注意不是arr[i] = temp
             * 直接插入排序也是這樣的。
             * 為什么呢阅茶？
             * 因?yàn)閖是位置谅海，i是待插入元素
             */
            arr[j] = temp;
        }

    }

}

總結(jié)：Shell排序適用于待排序記錄數(shù)量較大的情況扭吁，在此情況下，Shell排序一般要比直接插入排序要快（從直接插入排序結(jié)果的1061ms到希爾排序的21ms）。1971年系馆，斯坦福大學(xué)的兩位教授在大量實(shí)驗(yàn)的基礎(chǔ)上推導(dǎo)出Shell排序的時(shí)間復(fù)雜度約為O(n1.3)由蘑，使得我們終于突破了慢速排序的時(shí)代（超越了時(shí)間復(fù)雜度為O(n2)）。

7 歸并排序

基本思想：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表爷狈，即把待排序序列分為若干個(gè)子序列裳擎，每個(gè)子序列是有序的鹿响。然后再把有序子序列合并為整體有序序列。

歸并排序動(dòng)畫演示

算法實(shí)現(xiàn)

/**
 * 將數(shù)組中l(wèi)ow到high位置的數(shù)進(jìn)行排序
 * @param nums 待排序數(shù)組
 * @param low 待排的開始位置
 * @param mid 待排中間位置
 * @param high 待排結(jié)束位置
 */
public static void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;     // 左指針
    int j = mid + 1; // 右指針
    int k = 0;

    // 把較小的數(shù)先移到新數(shù)組中
    while (i <= mid && j <= high) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }

    // 把左邊剩余的數(shù)移入數(shù)組
    while (i <= mid) {
        temp[k++] = nums[i++];
    }

    // 把右邊邊剩余的數(shù)移入數(shù)組
    while (j <= high) {
        temp[k++] = nums[j++];
    }

    // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
    for (int k2 = 0; k2 < temp.length; k2++) {
        nums[k2 + low] = temp[k2];
    }
}


/**
 * 歸并排序
 * 將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表
 * 即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的盯蝴。
 * 然后再把有序子序列合并為整體有序序列
 * @param nums 待排序數(shù)組
 * @param low 待排序數(shù)組的第一個(gè)元素索引
 * @param high 待排序數(shù)組的最后一個(gè)元素索引
 * @return 輸出有序數(shù)組
 */
public static int[] sort(int[] nums, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        // 左邊
        sort(nums, low, mid);
        // 右邊
        sort(nums, mid + 1, high);
        // 左右歸并
        merge(nums, low, mid, high);
    }
    return nums;
}

/**
 * 歸并排序
 * @param data 待排序數(shù)組
 */
public static void mergeSort(int[] data) {
    sort(data,0,data.length-1);
}

8 桶排序

基數(shù)排序(radix sort)又稱桶排序（bucket sort）听怕，相對(duì)于常見的比較排序叉跛，基數(shù)排序是一種分配式排序，即通過將所有數(shù)字分配到應(yīng)在的位置最后再覆蓋到原數(shù)組完成排序的過程鸣峭。

桶排序適用數(shù)據(jù)范圍
桶排序可用于最大最小值相差較大的數(shù)據(jù)情況摊溶，比如[9012,19702,39867,68957,83556,102456]充石。
但桶排序要求數(shù)據(jù)的分布必須均勻，否則可能導(dǎo)致數(shù)據(jù)都集中到一個(gè)桶中拉岁。比如[104,150,123,132,20000], 這種數(shù)據(jù)會(huì)導(dǎo)致前4個(gè)數(shù)都集中到同一個(gè)桶中喊暖。導(dǎo)致桶排序失效撕瞧。

過程分析

桶排序的基本思想是：把數(shù)組 arr 劃分為n個(gè)大小相同子區(qū)間（桶），每個(gè)子區(qū)間各自排序偏序，最后合并胖替。
計(jì)數(shù)排序是桶排序的一種特殊情況，可以把計(jì)數(shù)排序當(dāng)成每個(gè)桶里只有一個(gè)元素的情況殉摔。

基數(shù)排序動(dòng)畫演示

1. 找出待排序數(shù)組中的最大值max逸月、最小值min遍膜；
2. 我們使用 動(dòng)態(tài)數(shù)組ArrayList 作為桶瓢颅，桶里放的元素也用 ArrayList 存儲(chǔ)。桶的數(shù)量為(max-min)/arr.length+1翰意；
3. 遍歷數(shù)組 arr冀偶，計(jì)算每個(gè)元素 arr[i] 放的桶；
4. 每個(gè)桶各自排序形病；
5. 遍歷桶數(shù)組，把排序好的元素放進(jìn)輸出數(shù)組量瓜。

算法實(shí)現(xiàn)

/**
 * 桶排序
 * @param arr 待排序數(shù)組
 */
public static void bucketSort(int[] arr) {

    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    // 桶數(shù)
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++) {
        bucketArr.add(new ArrayList<Integer>());
    }

    // 將每個(gè)元素放入桶
    for(int i = 0; i < arr.length; i++) {
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }

    // 對(duì)每個(gè)桶進(jìn)行排序
    for(int i = 0; i < bucketArr.size(); i++) {
        Collections.sort(bucketArr.get(i));
    }

}

9 計(jì)數(shù)排序

計(jì)數(shù)排序適用數(shù)據(jù)范圍

計(jì)數(shù)排序需要占用大量空間榔至，它僅適用于數(shù)據(jù)比較集中的情況欺劳。比如 [0_{100]划提，[10000}19999] 這樣的數(shù)據(jù)。

過程分析

計(jì)數(shù)排序的基本思想是：對(duì)每一個(gè)輸入的元素arr[i]淡诗，確定小于 arr[i] 的元素個(gè)數(shù)韩容。
所以可以直接把 arr[i] 放到它輸出數(shù)組中的位置上唐瀑。假設(shè)有5個(gè)數(shù)小于 arr[i]哄辣，所以 arr[i] 應(yīng)該放在數(shù)組的第6個(gè)位置上。

計(jì)數(shù)排序動(dòng)畫演示

• 算法流程（1）
  需要三個(gè)數(shù)組:
  待排序數(shù)組 int[] arr = new int[]{4,3,6,3,5,1};
  輔助計(jì)數(shù)數(shù)組 int[] help = new int[max - min + 1]; //該數(shù)組大小為待排序數(shù)組中的最大值減最小值+1
  輸出數(shù)組 int[] res = new int[arr.length];

1. 求出待排序數(shù)組的最大值max=6毅弧， 最小值min=1
2. 實(shí)例化輔助計(jì)數(shù)數(shù)組help够坐，help數(shù)組中每個(gè)下標(biāo)對(duì)應(yīng)arr中的一個(gè)元素崖面，help用來記錄每個(gè)元素出現(xiàn)的次數(shù)
3. 計(jì)算 arr 中每個(gè)元素在help中的位置 position = arr[i] - min嘶朱，此時(shí) help = [1,0,2,1,1,1]; （3出現(xiàn)了兩次，2未出現(xiàn)）
4. 根據(jù) help 數(shù)組求得排序后的數(shù)組脉课，此時(shí) res = [1,3,3,4,5,6]

/**
 * 計(jì)數(shù)排序
 * @param arr 待排序數(shù)組
 * @return
 */
public static int[] countSort1(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }

    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;

    // 找出數(shù)組中的最大最小值
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    /**
     * 輔助計(jì)數(shù)數(shù)組
     * 該數(shù)組大小為待排序數(shù)組中的最大值減最小值+1
     */
    int help[] = new int[max];

    // 找出每個(gè)數(shù)字出現(xiàn)的次數(shù)
    for(int i = 0; i < arr.length; i++){
        int mapPos = arr[i] - min;
        help[mapPos]++;
    }

    int index = 0;
    for(int i = 0; i < help.length; i++) {
        while(help[i]-- > 0) {
            arr[index++] = i+min;
        }
    }

    return arr;
}

• 算法流程（2）
  需要三個(gè)數(shù)組:
  待排序數(shù)組 int[] arr = new int[]{4,3,6,3,5,1};
  輔助計(jì)數(shù)數(shù)組 int[] help = new int[max - min + 1]; //該數(shù)組大小為待排序數(shù)組中的最大值減最小值+1
  輸出數(shù)組 int[] res = new int[arr.length];

1. 求出待排序數(shù)組的最大值max=6， 最小值min=1
2. 實(shí)例化輔助計(jì)數(shù)數(shù)組help戳寸，help用來記錄每個(gè)元素之前出現(xiàn)的元素個(gè)數(shù)
3. 計(jì)算 arr 每個(gè)數(shù)字應(yīng)該在排序后數(shù)組中應(yīng)該處于的位置疫鹊，此時(shí) help = [1,1,4,5,6,7];
4. 根據(jù) help 數(shù)組求得排序后的數(shù)組司致，此時(shí) res = [1,3,3,4,5,6]

/**
 * 計(jì)數(shù)排序
 * @param arr 待排序數(shù)組
 * @return
 */
public static int[] countSort2(int[] arr) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;

    // 找出數(shù)組中的最大最小值
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    int[] help = new int[max - min + 1];

    // 找出每個(gè)數(shù)字出現(xiàn)的次數(shù)
    for(int i = 0; i < arr.length; i++){
        int mapPos = arr[i] - min;
        help[mapPos]++;
    }

    // 計(jì)算每個(gè)數(shù)字應(yīng)該在排序后數(shù)組中應(yīng)該處于的位置
    for(int i = 1; i < help.length; i++){
        help[i] = help[i-1] + help[i];
    }

    // 根據(jù)help數(shù)組進(jìn)行排序
    int res[] = new int[arr.length];
    for(int i = 0; i < arr.length; i++){
        int post = --help[arr[i] - min];
        res[post] = arr[i];
    }

    return res;
}

各種算法的時(shí)間復(fù)雜度

排序?qū)Ρ?/div>

各種算法的時(shí)間復(fù)雜度

對(duì)應(yīng)語言的實(shí)現(xiàn)代碼下載

• 排序算法C#語言的實(shí)現(xiàn)
• 排序算法JavaScript語言的實(shí)現(xiàn)