零、總覽 / 前言

復雜度和穩(wěn)定性表格一覽

解釋一下穩(wěn)定性：
對于存在相等元素的序列，排序后，原相等元素在排序結果中的 相對位置 相比原輸入序列不變 。
例如 nums={3,1,$2_1$,$2_2$} ，數(shù)字 2 出現(xiàn)了兩次，下標表示他們出現(xiàn)的次序，若排序方法將 nums 排成了 {1,$2_2$? ,$2_1?$ ,3} ，雖然排序結果正確，但改變了兩個 2 的相對位置。只有排序為 {1,$2_1$,$2_2$,3} 我們才說該排序是穩(wěn)定的。

如果排序對象只是數(shù)值，那么是否穩(wěn)定沒有區(qū)別。但若是對引用類型進行排序，排序依據(jù)是該類型中的某個可比較的數(shù)值字段，那么我們可能會希望該字段相同，但其他字段不同的元素相對位置相比原輸入保持不變，這時候就需要穩(wěn)定排序。

不穩(wěn)定排序算法
堆排序、快速排序、希爾排序、直接選擇排序

穩(wěn)定排序算法
基數(shù)排序、冒泡排序、插入排序、歸并排序

一、冒泡排序

1.算法描述

對于要排序的數(shù)組，從第一位開始從前往后比較相鄰兩個數(shù)字，若前者大，則交換兩數(shù)字位置，然后比較位向右移動一位。第1輪從前到后的比較將使得最大的數(shù)字 冒泡 到最后

接著第二輪，同樣的操作，只不過只需要比到倒數(shù)第二個（倒數(shù)第一已經(jīng)最大了）

重復以上操作……

2.代碼&復雜度

//冒泡排序，從小到大排序，比較相鄰元素，更大的往數(shù)組右邊移動
    static void bubbleSort3(int[] arr)
    {
        for(int i=arr.length-1;i>0;i--)
        {
            for(int j=0;j<i;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
    }

時間復雜度：O(n^2)
空間復雜度：O(1）

二、選擇排序

1.算法描述

步驟：
（1）長度為n的數(shù)組中，第一次遍歷n-1個數(shù)，找到最小的數(shù)值與第一個元素交換

（2）第二次遍歷n-2個數(shù)，找到最小的數(shù)值與第二個元素交換

（3）第n-1次遍歷，找到最小的數(shù)值與第n-1個元素交換，排序完成

2.代碼&復雜度

 public void selectSort3(int[] arr)
    {
        for(int i=0;i<arr.length;i++)
        {
            int minTmp = Integer.MAX_VALUE;
            int index=0;
            // 開始尋找本輪最小的數(shù)字
            for(int j=i;j<arr.length;j++)
            {
                if(minTmp>arr[j])
                {
                    // 每次找到更小的時候記錄數(shù)字和下標值
                    minTmp = arr[j];
                    index = j;
                }
            }
            // 本輪循環(huán)結束，將最小值交換到數(shù)組前方
            int temp = arr[i];
            arr[i] = minTmp;
            arr[index] = temp;
    }

時間復雜度：O(n^2)
空間復雜度：O(1）

三、插入排序

1.算法描述

插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列

算法步驟：
（1）將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。

（2）從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。

2.代碼&復雜度分析

 /*插入排序：從小到大排序，類似于打撲克牌*/
    static void insertSort(int[] arr)
    {
        for(int i=1;i<arr.length;i++)
        {
            int now=arr[i]; //剛抓的手牌
            int j=i-1; //現(xiàn)有最后一張手牌的位置
            while (j>=0 && now<arr[j])  //剛抓的手牌小于手上現(xiàn)有的
            {
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=now;
        }
    }

時間復雜度：O(n^2)—— i 遍歷一次，j遍歷了一次，所以n^2
空間復雜度：O(1)—— 原地修改，沒有用額外空間

四、希爾排序

1.算法步驟

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。

2.代碼&復雜度分析

  //希爾排序：從小到大
  static void shellSort(int[] arr)
  {
      for(int interval=arr.length/2;interval>0;interval=interval/2)
      {
          for(int i=interval;i<arr.length;i++)
          {
              int temp=arr[i]; //從中間開始
              int j=i-interval; //增量是interval的前面的一個元素
              while (j>=0 && temp<arr[j])
              {
                  arr[j+interval]=arr[j];
                  j-=interval;
              }
              arr[j+interval]=temp;
          }
      }
  }

時間復雜度：
空間復雜度：

五、歸并排序

1.算法描述

分而治之，先分治，再合并

2.代碼&復雜度分析

public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
       // 自頂向下，遞歸實現(xiàn)
        public static void mergeSort(int[] arr, int left, int right) {
            if (left < right) {
                int mid = (left + right) / 2;
                mergeSort(arr, left, mid);
                mergeSort(arr, mid+1, right);
                merge(arr, left, mid, right);
            }
        }

        // 非原地合并
        public static void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[arr.length];
            int i = left;
            int j = mid + 1;
            int k = left;
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            for (int m = left; m <= right; m++) {
                arr[m] = temp[m];
            }
        }

六、快速排序

1.算法描述

首先在數(shù)組中確定一個主軸元素 (一般以第一個元素為主軸元素)，然后遍歷數(shù)組，將數(shù)組分為兩部分， 小于 主軸的元素放在 (最終的) 主軸下標 p 的左側， 大于等于 主軸的放在右側。

具體每一輪的操作過程是：
雙指針的思想，左指針指向第一個元素，右指針指向最后一個元素。左指針的目標是找到比主軸元素大的，找到后指針就停止，右指針則相反。當兩者都找到后，就進行交換。然后繼續(xù)這個過程，知道兩指針相遇。

貼一個簡單易懂的快排的排序過程：https://blog.csdn.net/qq_40941722/article/details/94396010

2.代碼&復雜度分析

void quickSort(int[] arr,int left,int right)
    {
        if(left>right)
            return;
        int pivot=arr[left];
        int i=left;
        int j=right;
        while(i!=j)
        {
            while (i<j && arr[j]>=pivot)
                j--;
            while(i<j && arr[i]<=pivot)
                i++;
            if(i<j)
            {
                int temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
        arr[left]=arr[i];
        arr[i]=pivot;

        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }

時間復雜度：O(nlogn)
空間復雜度：O(logn)

七、堆排序

八、計數(shù)排序——非比較排序

1.算法描述

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉化為鍵存儲在額外開辟的數(shù)組空間中。通常 適用于整數(shù)數(shù)組，是一種利用整數(shù)特點取得 線性復雜度 的非比較排序方法

算法步驟：
（1）找出待排序的數(shù)組中最大max和最小min的元素

（2）創(chuàng)建一個計數(shù)數(shù)組 countArr ，其大小為 arrarr 中的max-min+1

（3）統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，每讀取一個arr[i] ，直接令countArr[arr[i]-min]++

(4) 遍歷countArr ，依次輸出 counter[i] 個 i ，即為排序結果

2.代碼&復雜度分析

static int[] countSort(int[] arr)
    {
        int minNum=0,maxNum=0;
        // 先求出數(shù)組中的最大值和最小值
        for (int num : arr) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        // 開辟一個新數(shù)組：計數(shù)數(shù)組
        int[] count = new int[maxNum-minNum+1];
 
        // 遍歷原數(shù)組，對應計數(shù)數(shù)組索引值++
        for(int num:arr)
        {
            count[num-minNum]++;
        }
        // 開始將計數(shù)數(shù)組輸出
        int index=0;
        for(int i=0;i<count.length;i++)
        {
            while(count[i]>0)
            {
                arr[index++] = i;
                count[i]--;
            }
        }
        return arr;
    }

時間復雜度： O(n + k)，n 為元素個數(shù)， k 計數(shù)數(shù)組大小

空間復雜度：O(k)

上面的還是屬于不穩(wěn)定版本的，穩(wěn)定版本可以參見：https://leetcode.cn/circle/discuss/eBo9UB/

九、基數(shù)排序——非比較排序

十、桶排序——非比較排序

參考鏈接：https://leetcode.cn/circle/discuss/eBo9UB/文章來源地址http://www.zghlxwxcb.cn/news/detail-520205.html

到了這里，關于十大排序算法（Java實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！