經(jīng)常被問(wèn)到?今天講解下排序算法七大步

前言

由于這段時(shí)間在家辦公，所有有很多的時(shí)間來(lái)整理思路。今天主要簡(jiǎn)單講解一下幾個(gè)排序算法
剛好復(fù)工了，就到所謂的“金三銀四”了希望這段時(shí)間大家好好的整理下頭緒，爭(zhēng)取能拿到好的offer

相關(guān)內(nèi)容后續(xù)GitHub更新,想沖擊金三銀四的小伙伴可以找找看看，歡迎star
（順手留下GitHub鏈接，需要獲取相關(guān)面試等內(nèi)容的可以自己去找）
https://github.com/xiangjiana/Android-MS
(VX：mm14525201314)

一丶冒泡排序

基本思想:

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最 后的元素應(yīng)該會(huì)是最大的數(shù)。 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持 續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

Java實(shí)現(xiàn)
加入標(biāo)記狀態(tài) flag 若在一次冒泡中，沒(méi)有交換 則說(shuō)明可以停止 減少運(yùn)行時(shí)

  public static void bubbleSort(int[] numbers) { 
     int temp = 0; 
     int size = numbers.length; 
     boolean flag = true; 
     for (int i = 0; i < size - 1&&flag; i++) { 
         flag = false; 
         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; 
                flag = true; 
             } 
         }
     } 
  }

二丶選擇排序算法

基本思想：

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

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

   public static void selectSort(int[] numbers) { 
       int size = numbers.length; // 數(shù)組長(zhǎng)度 
       int temp = 0; // 中間變量 
       for (int i = 0; i < size-1; 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; 
      } 
   }

時(shí)間復(fù)雜度O(n*n) 性能上優(yōu)于冒泡排序 交換次數(shù)少

三丶插入排序算法

基本思想：

每步將一個(gè)待排序的記錄，按其順序碼大小插入到前面已經(jīng)排序的字序列的合適位 置（從后向前找到合適位置后），直到全部插入排序完為止。
Java 實(shí)現(xiàn)

  public static void insertSort(int[] numbers) { 
     int size = numbers.length; 
     int temp = 0; 
     int j = 0;
     for (int i = 1; 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; 
     } 
  }

時(shí)間復(fù)雜度
O(n*n) 性能上優(yōu)于冒泡排序和選擇排序

四丶希爾排序算法

基本思想：

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序 列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。
Java 實(shí)現(xiàn)

  /**
   * 希爾排序的原理:根據(jù)需求，如果你想要結(jié)果從小到大排列，它會(huì)首先將數(shù)組進(jìn)行分 組，然后將較小值移到前面，較大值 
   * 移到后面，最后將整個(gè)數(shù)組進(jìn)行插入排序，這樣比起一開(kāi)始就用插入排序減少了數(shù) 據(jù)交換和移動(dòng)的次數(shù)， 
   * 可以說(shuō)希爾排序是加強(qiáng) 版的插入排序 拿數(shù)組5, 2,8, 9, 1, 3，4來(lái)說(shuō)，數(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ù)組為5, 1, 3, 4, 2, 8，9 
   * 第一次后increment的值變?yōu)?/2=1,此時(shí)對(duì)數(shù)組進(jìn)行插入排序， 實(shí)現(xiàn)數(shù)組從大到 小排
   */ 
   public static void shellSort(int[] data) { 
      int j = 0; 
      int temp = 0; 
      // 每次將步長(zhǎng)縮短為原來(lái)的一半 
     for (int increment = data.length / 2; increment > 0; increme nt /= 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; 
                    } 
               }
               data[j] = temp; 
      } 
  }

五丶堆排序算法

基本思想:

堆排序是一種樹(shù)形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。

堆的定義下： 具有n個(gè)元素的序列 （h2,h3,...,hn),當(dāng)且僅當(dāng)滿(mǎn)足 （hi>=h3i,hi>=h3i+1）或（hi<=h3i,hi<=h3i+1） (i=1,2,...,n/2)時(shí)稱(chēng)之為堆。在這里 只討論滿(mǎn)足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為 最大項(xiàng)（大頂堆）。完全二叉樹(shù)可以很直觀(guān)地表示堆的結(jié)構(gòu)。堆頂為根，其它為左 子樹(shù)、右子樹(shù)。

思想: 初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹(shù)，調(diào)整它們的存儲(chǔ) 序，使之成為一個(gè) 堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié) 點(diǎn)交換。然后對(duì)前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類(lèi)推，直到只有兩個(gè)節(jié)點(diǎn) 的堆，并對(duì) 它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。從算法描述來(lái)看，堆排 序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排 序有兩個(gè)函數(shù)組成。一是建堆的***函數(shù)，二是反復(fù)調(diào)用***函數(shù)實(shí)現(xiàn)排序的函 數(shù)。

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

   public static void heapSort(int[] a){ 
      int arrayLength = a.length; 
      // 循環(huán)建堆 
      for (int i = 0; i < arrayLength - 1; i++) { 
          // 建堆 
          buildMaxHeap(a, arrayLength - 1 - i); 
         // 交換堆頂和最后一個(gè)元素 
         swap(a, 0, arrayLength - 1 - i); 
         System.out.println(Arrays.toString(a)); 
      }
   }
   // 對(duì)data數(shù)組從0到lastIndex建大頂堆 
   public static void buildMaxHeap(int[] data, int lastIndex) { 
      // 從lastIndex處節(jié)點(diǎn)（最后一個(gè)節(jié)點(diǎn)）的父節(jié)點(diǎn)開(kāi)始 
     for (int i = (lastIndex - 1) / 2; i >= 0; i--) { 
          // k保存正在判斷的節(jié)點(diǎn) 
          int k = i; 
         // 如果當(dāng)前k節(jié)點(diǎn)的子節(jié)點(diǎn)存在 
         while (k * 2 + 1 <= lastIndex) {
         // k節(jié)點(diǎn)的左子節(jié)點(diǎn)的索引 
         int biggerIndex = 2 * k + 1; 
        // 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k 節(jié)點(diǎn)的右子節(jié)點(diǎn)存在
         if (biggerIndex < lastIndex) { 
            // 若果右子節(jié)點(diǎn)的值較大 
            if (data[biggerIndex] < data[biggerIndex + 1]) { 
               // biggerIndex總是記錄較大子節(jié)點(diǎn)的索引 
               biggerIndex++; 
           } 
         }
         // 如果k節(jié)點(diǎn)的值小于其較大的子節(jié)點(diǎn)的值 
         if (data[k] < data[biggerIndex]) { 
              // 交換他們 
              swap(data, k, biggerIndex); 
              // 將biggerIndex賦予k，開(kāi)始while循環(huán)的下一次循環(huán)，重新 保證k節(jié)點(diǎn)的值大于其左右子節(jié)點(diǎn)的值 
              k = biggerIndex; 
         } else { 
              break; 
         } 
       } 
     } 
   }
   // 交換 
   private static void swap(int[] data, int i, int j) { 
      int tmp = data[i]; 
      data[i] = data[j]; 
      data[j] = tmp; 
  }

六丶快速排序算法

基本思想：

通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另 一部分關(guān)鍵字小，則分別對(duì)這兩部分繼續(xù)進(jìn)行排序，直到整個(gè)序列有序。
Java 實(shí)現(xiàn)

  /**
   * 快速排序 
   *
   * @param numbers 
   * 帶排序數(shù)組 
   */ 
   public static void quick(int[] numbers) { 
      if (numbers.length > 0) // 查看數(shù)組是否為空 
      { 
         quickSort(numbers, 0, numbers.length - 1); 
      } 
  }
  /**
   *
   * @param numbers 
   * 帶排序數(shù)組 
   * @param low 
   * 開(kāi)始位置 
   * @param high 
   * 結(jié)束位置 
   */ 
    public static void quickSort(int[] numbers, int low, int high) { 
        if (low >= high) { 
            return; 
        }
        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)行遞歸排序 
  }
  /**
   * 查找出中軸（默認(rèn)是最低位low）的在numbers數(shù)組排序后所在位置 
   *
   * @param numbers 
   * 帶查找數(shù)組
   * @param low 
   * 開(kāi)始位置 
   * @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; // 返回中軸的位置 
  }

快速排序在序列中元素很少時(shí)，效率將比較低，不如插入排序，因此一般在序列中 元素很少時(shí)使用插入排序，這樣可以提高整體效率。

七丶?xì)w并排序算法

基本思想:

歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即 把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并 為整體有序序列。
Java 實(shí)現(xiàn)

  /**
   * 歸并排序 
   * 簡(jiǎn)介:將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表 即把待排序序列分為若 干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列 
   * 時(shí)間復(fù)雜度為O(nlogn) 
   * 穩(wěn)定排序方式 
   * @param nums 待排序數(shù)組 
   * @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; 
  }
   /**
    * 將數(shù)組中l(wèi)ow到high位置的數(shù)進(jìn)行排序 
    * @param nums 待排序數(shù)組 
    * @param low 待排的開(kāi)始位置 
    * @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]; 
     } 
  }

各種算法的時(shí)間復(fù)雜度等性能比較

相關(guān)內(nèi)容后續(xù)GitHub更新，想沖擊金三銀四的小伙伴可以找找看看，歡迎star
（順手留下GitHub鏈接，需要獲取相關(guān)面試等內(nèi)容的可以自己去找）
https://github.com/xiangjiana/Android-MS
(VX：mm14525201314)