強(qiáng)大，從來(lái)不是左右別人，而是為了不被別人左右

前言

校招面試常問(wèn)的排序算法，做個(gè)總結(jié)

2天后文章同步到個(gè)人網(wǎng)站：https://upheart.cn/，未及時(shí)同步可以私聊我，可能會(huì)比較忙忘記了！

文章不錯(cuò)的話(huà)，希望點(diǎn)贊再看，謝謝

同時(shí)520的晚上還在整理文章，是不是更該點(diǎn)個(gè)贊，哈哈！

前置知識(shí)

排序算法的穩(wěn)定性

排序算法的穩(wěn)定性是指：當(dāng)輸入元素中有兩個(gè)元素的值相同時(shí)，排序后完成之后，這兩個(gè)元素的前后位置是否發(fā)生了前后變化。

應(yīng)用場(chǎng)景

1.訂單排序

假設(shè)需要為用戶(hù)按照時(shí)間順序來(lái)展示訂單， 相同時(shí)間點(diǎn)的訂單按照訂單金額順序來(lái)展示。

實(shí)現(xiàn)上，可以先訂單金額對(duì)訂單排一次序， 再按時(shí)間對(duì)訂單排一次序。

那么，這里排序算法的穩(wěn)定性就體現(xiàn)用武之地了

假設(shè)按時(shí)間排序時(shí)不是穩(wěn)定的，那么相同時(shí)間的2筆訂單可能就會(huì)發(fā)送順序調(diào)換， 因此而破壞了前面按金額排序好的結(jié)果。

結(jié)論：按訂單金額先排序，再用穩(wěn)定排序算法按時(shí)間排序。

2.成績(jī)排序

假設(shè)需要給學(xué)生的卷面成績(jī)排序， 相同成績(jī)的學(xué)生按平時(shí)分排序。

實(shí)現(xiàn)上， 有了第一個(gè)例子的經(jīng)驗(yàn)，我們已經(jīng)知道，要先按照平時(shí)分排序，再用穩(wěn)定排序算法按卷面成績(jī)排序。

因?yàn)榧偃缬龅较嗤砻娣值膶W(xué)生， 那不穩(wěn)定的排序會(huì)破壞排好序的平時(shí)分。

• 內(nèi)排序：所有排序操作都在內(nèi)存中完成；
• 外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤(pán)中，而排序通過(guò)磁盤(pán)和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；
• 時(shí)間復(fù)雜度： 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
• 空間復(fù)雜度：運(yùn)行完一個(gè)程序所需內(nèi)存的大小。

一張圖

冒泡排序

核心思路：

依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。

在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。

在第二趟：仍從第一對(duì)數(shù)開(kāi)始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。

如此下去，重復(fù)以上過(guò)程，直至最終完成排序。

舉例說(shuō)明：4 5 6 3 2 1,從小到大排序

第一次冒泡的結(jié)果:4 5 6 3 2 1->4 5 3 6 2 1 -> 4 5 3 2 6 1 -> 4 5 3 2 1 6，6這個(gè)元素的位置確定了

第二次冒泡的結(jié)果:4 5 3 2 1 6->4 3 5 2 1 6 -> 4 3 2 5 1 6 -> 4 3 2 1 5 6，5這個(gè)元素的位置確定了

第三次冒泡的結(jié)果:4 3 2 1 5 6->3 4 2 1 5 6 -> 3 2 4 1 5 6 -> 3 2 1 4 5 6，4這個(gè)元素的位置確定了

第四次冒泡的結(jié)果:3 2 1 4 5 6->2 3 1 4 5 6 -> 2 1 3 4 5 6，3這個(gè)元素的位置確定了

第五次冒泡的結(jié)果:2 1 3 4 5 6->1 2 3 4 5 6，2這個(gè)元素的位置確定了

實(shí)現(xiàn)

設(shè)數(shù)組長(zhǎng)度為N：

1．比較相鄰的前后二個(gè)數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個(gè)數(shù)據(jù)交換。

2．這樣對(duì)數(shù)組的第0個(gè)數(shù)據(jù)到N-1個(gè)數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個(gè)數(shù)據(jù)就“沉”到數(shù)組第N-1個(gè)位置。

3．循環(huán)N=N-1，如果N不為0就重復(fù)前面二步，否則排序完成。

public class BubbleSort {
    public static void BubbleSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j + 1] < arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = new int[]{1, 6, 2, 3, 22};
        BubbleSort.BubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

冒泡排序法存在的不足及改進(jìn)方法

在排序過(guò)程中，執(zhí)行完最后的排序后，雖然數(shù)據(jù)已全部排序完備，但程序無(wú)法判斷是否完成排序，為了解決這一不足，可設(shè)置一個(gè)標(biāo)志位flag，將其初始值設(shè)置為非0，表示被排序的表是一個(gè)無(wú)序的表，每一次排序開(kāi)始前設(shè)置flag值為0，在進(jìn)行數(shù)據(jù)交換時(shí)，修改flag為非0。

在新一輪排序開(kāi)始時(shí)，檢查此標(biāo)志，若此標(biāo)志為0，表示上一次沒(méi)有做過(guò)交換數(shù)據(jù)（有序狀態(tài)），則結(jié)束排序；否則進(jìn)行排序；

優(yōu)化

import java.util.Arrays;
public class BubbleSort {
 public static void main(String[] args) {
  int data[] = { 4, 5, 6, 3, 2, 1 };
  int n = data.length;
  for (int i = 0; i < n - 1; i++) { //排序的次數(shù)
   boolean flag = false;
   for (int j = 0; j < n - 1 - i; j++) { //具體冒泡 n - 1 - i
    if (data[j] > data[j + 1]) {
     int temp = data[j]; 
     data[j] = data[j + 1];
     data[j + 1] = temp;
     flag = true;
    }
   }
   if(!flag) break;
  }
  System.out.println(Arrays.toString(data));
 }
}

選擇排序

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?，以此類(lèi)推，直到所有元素均排序完畢

由于存在數(shù)據(jù)交換，選擇排序不是穩(wěn)定的排序算法

實(shí)現(xiàn)

public class SelectionSort {
    public int[] selectionSort(int[] A, int n) {
        //記錄最小下標(biāo)值
        int min=0;
        for(int i=0; i<A.length-1;i++){
            min = i;
            //找到下標(biāo)i開(kāi)始后面的最小值
            for(int j=i+1;j<A.length;j++){
                 if(A[min]>A[j]){
                     min = j;
                 }
            }
            if(i!=min){
                swap(A,i,min);
            }
        }
        return A;
    }
    private void swap(int[] A,int i,int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

插入排序

插入排序算法的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間

實(shí)現(xiàn)

public class InsertionSort {
    public int[] insertionSort(int[] A, int n) {
      //用模擬插入撲克牌的思想
        //插入的撲克牌
        int i,j,temp;
        //已經(jīng)插入一張，繼續(xù)插入
        for(i=1;i<n;i++){
            temp = A[i];
            //把i前面所有大于要插入的牌的牌往后移一位，空出一位給新的牌
            for(j=i;j>0&&A[j-1]>temp;j--){
                A[j] = A[j-1];
            }
            //把空出來(lái)的一位填滿(mǎn)插入的牌
            A[j] = temp;
        }
        return A;
    }
}

歸并排序

歸并排序核心是分治思想，先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了

若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并

歸并排序是穩(wěn)定的排序算法

實(shí)現(xiàn)

public class MergeSort {
 public static void main(String[] args) {
  int data[] = { 9, 5, 6, 8, 0, 3, 7, 1 };
  megerSort(data, 0, data.length - 1);
  System.out.println(Arrays.toString(data));
 }
 
 public static void mergeSort(int data[], int left, int right) { // 數(shù)組的兩端
  if (left < right) { // 相等了就表示只有一個(gè)數(shù)了 不用再拆了
   int mid = (left + right) / 2;
   mergeSort(data, left, mid);
   mergeSort(data, mid + 1, right);
   // 分完了 接下來(lái)就要進(jìn)行合并，也就是我們遞歸里面歸的過(guò)程
   merge(data, left, mid, right);
  }
 }
 
 public static void merge(int data[], int left, int mid, int right) {
  int temp[] = new int[data.length];  //借助一個(gè)臨時(shí)數(shù)組用來(lái)保存合并的數(shù)據(jù)
  
  int point1 = left;  //表示的是左邊的第一個(gè)數(shù)的位置
  int point2 = mid + 1; //表示的是右邊的第一個(gè)數(shù)的位置
  
  int loc = left;  //表示的是我們當(dāng)前已經(jīng)到了哪個(gè)位置了
  while(point1 <= mid && point2 <= right){
   if(data[point1] < data[point2]){
    temp[loc] = data[point1];
    point1 ++ ;
    loc ++ ;
   }else{
    temp[loc] = data[point2];
    point2 ++;
    loc ++ ;
   }
  }
    
  while(point1 <= mid){
   temp[loc ++] = data[point1 ++];
  }
  while(point2 <= right){
   temp[loc ++] = data[point2 ++];
  }
  for(int i = left ; i <= right ; i++){
   data[i] = temp[i];
  }
 }
}

希爾排序

基本思想：

算法先將要排序的一組數(shù)按某個(gè)增量d（n/2，n為要排序數(shù)的個(gè)數(shù)）分成若干組，每組中記錄的下標(biāo)相差d，對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。當(dāng)增量減到1時(shí)，進(jìn)行直接插入排序后，排序完成

希爾排序法(縮小增量法) 屬于插入類(lèi)排序，是將整個(gè)無(wú)序列分割成若干小的子序列分別進(jìn)行插入排序的方法

假如：數(shù)組的長(zhǎng)度為10，數(shù)組元素為：25、19、6、58、34、10、7、98、160、0

整個(gè)希爾排序的算法過(guò)程如下如所示：

實(shí)現(xiàn)

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;
    }

快速排序

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

• 先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。
• 分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
• 再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。

實(shí)現(xiàn)1

public class QuickSort {
    public static void quickSort(int[]arr,int low,int high){
         if (low < high) {     
             int middle = getMiddle(arr, low, high);     
             quickSort(arr, low, middle - 1);//遞歸左邊            
             quickSort(arr, middle + 1, high);//遞歸右邊   
          }  
    }
    public static int getMiddle(int[] list, int low, int high) {     
        int tmp = list[low];    
        while (low < high) {     
            while (low < high && list[high] >= tmp) {//大于關(guān)鍵字的在右邊
                high--;     
            }     
            list[low] = list[high];//小于關(guān)鍵字則交換至左邊   
            while (low < high && list[low] <= tmp) {//小于關(guān)鍵字的在左邊
                low++;     
            }     
            list[high] = list[low];//大于關(guān)鍵字則交換至左邊   
        }     
       list[low] = tmp;           
       return low;                   
    } 
}

實(shí)現(xiàn)2

public class QuickSort {
 
 public static void quickSort(int data[], int left, int right) {
 
  int base = data[left]; // 基準(zhǔn)數(shù)，取序列的第一個(gè)
  int ll = left; // 表示的是從左邊找的位置
  int rr = right; // 表示從右邊開(kāi)始找的位置
  while (ll < rr) {
   // 從后面往前找比基準(zhǔn)數(shù)小的數(shù)
   while (ll < rr && data[rr] >= base) {
    rr--;
   }
   if (ll < rr) { // 表示是找到有比之大的
    int temp = data[rr];
    data[rr] = data[ll];
    data[ll] = temp;
    ll++;
   }
   while (ll < rr && data[ll] <= base) {
    ll++;
   }
   if (ll < rr) {
    int temp = data[rr];
    data[rr] = data[ll];
    data[ll] = temp;
    rr--;
   }
  }
  // 肯定是遞歸 分成了三部分,左右繼續(xù)快排，注意要加條件不然遞歸就棧溢出了
  if (left < ll)
   quickSort(data, left, ll - 1);
  if (ll < right)
   quickSort(data, ll + 1, right);
 }
}

優(yōu)化

基本的快速排序選取第一個(gè)或最后一個(gè)元素作為基準(zhǔn)。但是，這是一直很不好的處理方法

如果數(shù)組已經(jīng)有序時(shí)，此時(shí)的分割就是一個(gè)非常不好的分割。因?yàn)槊看蝿澐种荒苁勾判蛐蛄袦p一，此時(shí)為最壞情況，快速排序淪為冒泡排序，時(shí)間復(fù)雜度為O(n^2)

三數(shù)取中

一般的做法是使用左端、右端和中心位置上的三個(gè)元素的中值作為樞紐元

舉例：待排序序列為：8 1 4 9 6 3 5 2 7 0

左邊為：8，右邊為0，中間為6

我們這里取三個(gè)數(shù)排序后，中間那個(gè)數(shù)作為樞軸，則樞軸為6

插入排序

當(dāng)待排序序列的長(zhǎng)度分割到一定大小后，使用插入排序 原因：對(duì)于很小和部分有序的數(shù)組，快排不如插排好。當(dāng)待排序序列的長(zhǎng)度分割到一定大小后，繼續(xù)分割的效率比插入排序要差，此時(shí)可以使用插排而不是快排

重復(fù)數(shù)組

在一次分割結(jié)束后，可以把與Key相等的元素聚在一起，繼續(xù)下次分割時(shí)，不用再對(duì)與key相等元素分割

在一次劃分后，把與key相等的元素聚在一起，能減少迭代次數(shù)，效率會(huì)提高不少

具體過(guò)程：在處理過(guò)程中，會(huì)有兩個(gè)步驟

第一步，在劃分過(guò)程中，把與key相等元素放入數(shù)組的兩端

第二步，劃分結(jié)束后，把與key相等的元素移到樞軸周?chē)?/p>

舉例：

待排序序列 1 4 6 7 6 6 7 6 8 6

三數(shù)取中選取樞軸：下標(biāo)為4的數(shù)6

轉(zhuǎn)換后，待分割序列：6 4 6 7 1 6 7 6 8 6

樞軸key：6

第一步，在劃分過(guò)程中，把與key相等元素放入數(shù)組的兩端

結(jié)果為：6 4 1 6(樞軸) 7 8 7 6 6 6

此時(shí)，與6相等的元素全放入在兩端了

第二步，劃分結(jié)束后，把與key相等的元素移到樞軸周?chē)?/p>

結(jié)果為：1 4 6 6(樞軸) 6 6 6 7 8 7

此時(shí)，與6相等的元素全移到樞軸周?chē)?/p>

之后，在1 4 和 7 8 7兩個(gè)子序列進(jìn)行快排

堆排序

堆是一種特殊的樹(shù)。只要滿(mǎn)足這兩點(diǎn)，它就是一個(gè)堆。

• 堆是一個(gè)完全二叉樹(shù)；
• 堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于（或小于等于）其子樹(shù)中每個(gè)節(jié)點(diǎn)的值。

對(duì)于每個(gè)節(jié)點(diǎn)的值都大于等于子樹(shù)中每個(gè)節(jié)點(diǎn)值的堆，我們叫做“大頂堆”。

對(duì)于每個(gè)節(jié)點(diǎn)的值都小于等于子樹(shù)中每個(gè)節(jié)點(diǎn)值的堆，我們叫做“小頂堆”。

一般升序用大根堆，降序就用小根堆

如何實(shí)現(xiàn)一個(gè)堆

完全二叉樹(shù)比較適合用數(shù)組來(lái)存儲(chǔ)。用數(shù)組來(lái)存儲(chǔ)完全二叉樹(shù)是非常節(jié)省存儲(chǔ)空間的。因?yàn)槲覀儾恍枰鎯?chǔ)左右子節(jié)點(diǎn)的指針，單純地通過(guò)數(shù)組的下標(biāo)，就可以找到一個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)和父節(jié)點(diǎn)。

比如查找數(shù)組arr中某個(gè)數(shù)的父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)，比如已知索引為i的數(shù)，那么

1. 父結(jié)點(diǎn)索引：(i-1)/2（這里計(jì)算機(jī)中的除以2，省略掉小數(shù)）

2. 左孩子索引：2*i+1

3. 右孩子索引：2*i+2

所以堆的定義性質(zhì)：

• 大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

• 小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

堆排序基本步驟

1.首先將待排序的數(shù)組構(gòu)造成一個(gè)大根堆，此時(shí)，整個(gè)數(shù)組的最大值就是堆結(jié)構(gòu)的頂端

2.將頂端的數(shù)與末尾的數(shù)交換，此時(shí)，末尾的數(shù)為最大值，剩余待排序數(shù)組個(gè)數(shù)為n-1

3.將剩余的n-1個(gè)數(shù)再構(gòu)造成大根堆，再將頂端數(shù)與n-1位置的數(shù)交換，如此反復(fù)執(zhí)行，便能得到有序數(shù)組

以下將針對(duì)數(shù)組arr[1,2,5,4,3,7]進(jìn)行大頂堆的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換。

• 我們從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始（第一個(gè)非葉子結(jié)點(diǎn) arr.length/2-1=5/2-1=1，也就是索引為2的結(jié)點(diǎn)），從右至左，從下至上進(jìn)行調(diào)整
• 由于[5,7]中7元素最大，5和7交換。
• 最后一個(gè)非葉子結(jié)點(diǎn)索引減1，找到第二個(gè)非葉結(jié)點(diǎn)(索引1)，由于[4,3,2]中4元素最大，2和4交換。
• 非葉子結(jié)點(diǎn)索引減1，找到第三個(gè)非葉結(jié)點(diǎn)(索引0)，由于[4,1,7]中7元素最大，1和7交換。
• 這時(shí)，交換導(dǎo)致了子根[1，5]結(jié)構(gòu)混亂，繼續(xù)調(diào)整，[1,5]中5最大，交換1和5。
• 此時(shí)，我們就將一個(gè)無(wú)序序列構(gòu)造成了一個(gè)大頂堆。

• 將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換

• 最后，就實(shí)現(xiàn)了堆排序

實(shí)現(xiàn)

import java.util.Arrays;
 
public class HeapSort {
 public static void main(String[] args) {
  int data[] = { 8, 4, 20, 7, 3, 1, 25, 14, 17 };
  heapSort(data);
  System.out.println(Arrays.toString(data));
 }
 
 public static void maxHeap(int data[], int start, int end) { 
 
  int parent = start;
  int son = parent * 2 + 1; // 下標(biāo)是從0開(kāi)始的就要加1，從1就不用
  while (son < end) {
   int temp = son;
   // 比較左右節(jié)點(diǎn)和父節(jié)點(diǎn)的大小
   if (son + 1 < end && data[son] < data[son + 1]) { // 表示右節(jié)點(diǎn)比左節(jié)點(diǎn)大
    temp = son + 1; // 就要換右節(jié)點(diǎn)跟父節(jié)點(diǎn)
   }
   // temp表示的是 我們左右節(jié)點(diǎn)大的那一個(gè)
   if (data[parent] > data[temp])
    return; // 不用交換
   else { // 交換
    int t = data[parent];
    data[parent] = data[temp];
    data[temp] = t;
    parent = temp; // 繼續(xù)堆化
    son = parent * 2 + 1;
   }
  }
  return;
 
 }
 
 public static void heapSort(int data[]) {
 
  int len = data.length;
  for (int i = len / 2 - 1; i >= 0; i--) { 
   maxHeap(data, i, len);  
  }
  for (int i = len - 1; i > 0; i--) {
   int temp = data[0];
   data[0] = data[i];
   data[i] = temp;
   maxHeap(data, 0, i);
  }
 }
 
}

最后

覺(jué)得有收獲，希望幫忙點(diǎn)贊，轉(zhuǎn)發(fā)下哈，謝謝，謝謝

微信搜索：月伴飛魚(yú)，交個(gè)朋友

公眾號(hào)后臺(tái)回復(fù)666，可以獲得免費(fèi)電子書(shū)籍