八大排序算法總結

文章目錄

• 1 冒泡排序
• • 1.1 原理
  • 1.2 圖解
  • 1.3 代碼
• 2 選擇排序
• • 2.1 原理
  • 2.2 圖解
  • 2.3 代碼
• 3 直接插入排序
• • 3.1 原理
  • 3.2 圖解
  • 3.3 代碼
• 4 希爾排序 （縮小增量排序）
• • 4.1 原理
  • • 4.1.1 交換法和移位法
  • 4.2 圖解
  • 4.3 代碼
  • • 4.3.1 交換法
    • 4.3.2 移位法
• 5 快速排序
• • 5.1 原理
  • 5.2 圖解
  • 5.3 代碼
• 6 歸并排序
• • 6.1 原理
  • 6.2 圖解
  • 6.3 代碼
• 7 基數排序
• • 7.1 原理
  • 7.2 圖解
  • 7.3 代碼
• 8 堆排序
• 9 比較
• • 9.1 時空複雜度
  • 9.2 實際測試
  • • 9.2.1 代碼
    • 9.2.2 結果

1 冒泡排序

1.1 原理

1.2 圖解

1.3 代碼

public static void bubbleSort(int[] nums) {
        int n = nums.length;
        // 有序區為i到n-1，每次把0到i之間的最值冒泡交換到有序區的前面，使得有序區擴大一位。
        for (int i = n-1; i >= 0; i--) {
            // 冒泡排序優化，如果在目前趟無序區的比較中，沒有發生過交換，說明目前無序區已經有序，可以直接結束排序過程
            boolean swapFlag = false;
            for (int j = 0; j < i ; j++) {
                // 将最大值冒泡交換到有序區
                if (nums[j] > nums[j+1]) {
                    swapFlag = true;
                    int t = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = t;
                }
            }
            if (!swapFlag)
                break;
        }
    }
           

2 選擇排序

2.1 原理

2.2 圖解

2.3 代碼

public static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = Integer.MAX_VALUE;
            int minIdx = -1;
            // 周遊無序區，找到最小(優先級最低)的數，及其索引
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    minIdx = j;
                }
            }
            // 将最小數與無序區的首位元素進行交換，進而擴大前面的無序區
            if (i != minIdx) {
                nums[minIdx] = nums[i];
                nums[i] = min;
            }
        }
    }
           

3 直接插入排序

3.1 原理

3.2 圖解

3.3 代碼

public static void insertSort(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n ; i++) {
            // 将j = i位置,即無序區的開始，囊括到有序區，并将該位置的資料，插入到合适的位置
            // 反向周遊有序區，如果目前元素不小于(優先級不低于)待插入資料)，則将目前元素後移一位（目前位置不用管）
            // 找到了第一個優先級低于 待插入資料 的位置， 将待插入資料 放到這個位置的後面即可。
            int insertValue = nums[i];
            int insertIdx = 0;
            for (int j = i - 1; j >= 0 ; j--) {
                if (nums[j] >= insertValue) {
                    nums[j + 1] = nums[j];
                }
                else {
                    insertIdx = j + 1;
                    break;
                }
            }
            // 判斷是否需要插入
            if (insertIdx != i)
                nums[insertIdx] = insertValue;
        }
    }
           

4 希爾排序 （縮小增量排序）

4.1 原理

4.1.1 交換法和移位法

4.2 圖解

4.3 代碼

4.3.1 交換法

// 希爾排序 交換法 (多次交換導緻速度很慢)
    public static void shellSortSwap(int[] nums) {
        int n = nums.length;
        // 初始增量為長度的一半，每次将增量縮小一半
        int t = 0;
        int count = 0;
        for (int gap = n / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < n  ; i++) {
                // 從每個分組的最後一個元素開始向前周遊，進行插入排序
                for (int j = i - gap; j >= 0 ; j -= gap) {
                    // 交換法
                    if (nums[j] >= nums[j + gap]) {
                        t = nums[j];
                        nums[j] = nums[j + gap];
                        nums[j + gap] = t;
                    }
                }
            }
            //System.out.println("希爾排序第"+(++count)+"輪後: " + Arrays.toString(nums));
        }
    }
           

4.3.2 移位法

// 希爾排序 移位法
    public static void shellSortShift(int[] nums) {
        int n = nums.length;
        // 初始增量為長度的一半，每次将增量縮小一半
        int t = 0;
        int count = 0;
        for (int gap = n / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < n  ; i++) {
                // 從每個分組的最後一個元素開始向前周遊，進行插入排序
                int insertValue = nums[i];
                int insertIdx = i;
                for (int j = i - gap; j >= 0 ; j -= gap) {
                    // 移位法：類似插入排序中的處理
                    if (nums[j] >= insertValue) {
                        nums[j + gap] = nums[j];
                        insertIdx -= gap;
                    }
                    else break;
                }
                if (insertIdx != i)
                    nums[insertIdx] = insertValue;
            }
            //System.out.println("希爾排序第"+(++count)+"輪後: " + Arrays.toString(nums));
        }
    }
           

5 快速排序

5.1 原理

5.2 圖解

5.3 代碼

選擇基準值的方式有多種：例如左邊界、中間位置、右邊界以及随機位置，這裡采用左邊界。

public static void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            // 治
            int pivot_loc = partition(nums, left, right);
            // 分
            quickSort(nums, left, pivot_loc - 1);
            quickSort(nums, pivot_loc + 1, right);
        }
    }

    public static int partition(int[] nums, int left, int right) {		
        /*   // 随機一個位置作為基準值（軸值）
    	int pivotLoc = left + new Random().nextInt(right - left + 1);
        int pivot = nums[pivotLoc];
        */
        int pivot = nums[left];  // 選擇第一個元素作為軸值
        // 以最左邊為軸值時，在交換值時應該先右後左
        while (left != right) {
            // 從右往左找到比軸值小的元素
            while (nums[right] >= pivot && left < right) {
                right--;
            }
            // 将這個元素的值賦到left位置
            if (left < right) {
                nums[left] = nums[right];
                left++;
            }
            // 從左往右找到比軸值大的元素
            while (nums[left] < pivot && left < right) {
               left++;
            }
            // 将這個元素的值賦到right位置
            if (left < right) {
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = pivot;
        return left;
    }
           

6 歸并排序

6.1 原理

6.2 圖解

6.3 代碼

少量空間換時間

public static void mergeSort(int[] nums) {
        int[] temp = new int[nums.length];
        divideAndConquer(nums, 0 , nums.length - 1, temp);
    }

    public static void divideAndConquer(int[] nums, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            // System.out.printf("正在分解數組[%d-%d]為[%d-%d][%d-%d]\n", left, right, left, mid, mid + 1, right);
            //向左遞歸不斷分解
            divideAndConquer(nums, left, mid, temp);
            //向右遞歸不斷分解
            divideAndConquer(nums, mid + 1, right, temp);

            // 第一次到這裡，數組應該被分為n份，每份長度為1，即l=r
            // System.out.printf("正在合并數組[%d-%d][%d-%d]為[%d-%d]\n", left, mid, mid + 1, right, left, right);
            merge(nums, left, mid, right, temp);
        }
    }

    public static void merge(int[] nums, int left, int mid, int right, int[] temp) {
        // 歸并排序“治”的過程，實際上就是 合并兩個有序序列的過程。
        int i = left;
        int j = mid + 1;
        int t = 0;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[t] = nums[i];
                t++;
                i++;
            }
            else {
                temp[t] = nums[j];
                t++;
                j++;
            }
        }
        while (i <= mid) {
            temp[t] = nums[i];
            i++;
            t++;
        }
        while (j <= right) {
            temp[t] = nums[j];
            j++;
            t++;
        }
        // 将temp數組的當此有效元素 拷貝到原數組nums中
        // 注意這裡temp數組和nums數組映射關系不同
        // temp  0 -> right - left - 1    nums  left -> right
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            nums[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }

    }
           

7 基數排序

7.1 原理

7.2 圖解

7.3 代碼

public static void radixSort(int[] nums) {
        int n = nums.length;
        // 建立10個桶，第i個桶存儲目前位為i的資料,為了防止溢出，每個桶的大小應該和原數組大小相同
        int[][] buckets = new int[10][n];
        // 記錄每輪排序後，每個桶實際放了多少個資料
        int[] bucketsTop = new int[10];

        // 排序前，先周遊依次：1、找到數組最小值； 2、找到數組最大絕對值，計算最大位數
        int min = 0;
        for (int num : nums) {
            min = Math.min(num, min);
        }
        // 如果min < 0，說明存在負數，将所有資料加上 -min 使得全部為正數
        int max = 0;
        if (min < 0) {
            for (int i = 0; i < nums.length; i++) {
                nums[i] += -min;
                max = Math.max(max, nums[i]);
            }
        }
        // 計算最大位長度
        int maxBitLength = (max + "").length();
        for (int b = 0; b <= maxBitLength; b++) {
            // 周遊原數組，按照目前位每個資料的位值，将其放到對應的桶
            int bit = (int) Math.pow(10, b);
            for (int i = 0; i < n; i++) {
                int digit = (nums[i] / bit) % 10;
                buckets[digit][bucketsTop[digit]] = nums[i];
                bucketsTop[digit]++;
            }
            // 周遊所有桶，将桶中資料按順序放回原數組
            int index = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < bucketsTop[i]; j++) {
                    nums[index] = buckets[i][j];
                    index++;
                }
                // 每一輪處理後，應該把桶的資料下标置0
                bucketsTop[i] = 0;
            }
        }
        // 如果min < 0，說明存在負數，恢複排序好的資料，所有資料加上 min
        if (min < 0) {
            for (int i = 0; i < nums.length; i++) {
                nums[i] += min;
            }
        }
    }
           

8 堆排序

9 比較

9.1 時空複雜度

搬一張尚矽谷的圖

9.2 實際測試

9.2.1 代碼

public class SortTest {
    public static void main(String[] args) {
        int length = 100000000;
        int[] nums = new int[length];
        for (int i = 0; i < length; i++) {
            nums[i] = (int) (Math.random() * length);
        }
        System.out.printf("測試 %d 長度随機數組進行升序排序的耗時:\n", length);
        System.out.println("冒泡排序: " + bubbleSortTest(nums) + "ms");
        System.out.println("選擇排序: " + selectSortTest(nums) + "ms");
        System.out.println("插入排序: " + insertSortTest(nums) + "ms");
        System.out.println("希爾排序交換法: " + shellSortSwap(nums) + "ms");
        System.out.println("希爾排序移位法: " + shellSortShift(nums) + "ms");
        System.out.println("快速排序左邊基準值法: " + quickSortLeftPivotTest(nums) + "ms");
        System.out.println("快速排序随機基準值法: " + quickSortRandomPivotTest(nums) + "ms");
        System.out.println("歸并排序:" + mergeSortTest(nums) + "ms");
        System.out.println("基數排序:" + radixSortTest(nums) + "ms");
    }

    public static long bubbleSortTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        BubbleSort.bubbleSort(arr);
        return System.currentTimeMillis() - start;
    }

    public static long selectSortTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        SelectSort.selectSort(arr);
        return System.currentTimeMillis() - start;
    }

    public static long insertSortTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        InsertSort.insertSort(arr);
        return System.currentTimeMillis() - start;
    }

    public static long shellSortSwap(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        ShellSort.shellSortSwap(arr);
        return System.currentTimeMillis() - start;
    }

    public static long shellSortShift(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        ShellSort.shellSortShift(arr);
        return System.currentTimeMillis() - start;
    }

    public static long quickSortLeftPivotTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        QuickSort.quickSort(arr, 0, arr.length - 1);
        return System.currentTimeMillis() - start;
    }

    public static long quickSortRandomPivotTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        QuickSort.randomQuickSort(arr, 0, arr.length - 1);
        return System.currentTimeMillis() - start;
    }

    public static long mergeSortTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        MergeSort.mergeSort(arr);
        return System.currentTimeMillis() - start;
    }

    public static long radixSortTest(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        long start = System.currentTimeMillis();
        RadixSort.radixSort(arr);
        return System.currentTimeMillis() - start;
    }
}
           

9.2.2 結果