约定

下述代码中会使用 swap() 方法完成交换操作

  1. public void swap(int[] nums, int i, int j) {
  2.     int temp = nums[i];
  3.     nums[i] = nums[j];
  4.     nums[j] = temp;
  5. }

选择排序

排序思路：从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择最小的元素，将它与数组的第二个元素交换位置，以此类推，不断进行这样的操作，直到将整个数组排序。
选择排序.gif

  1. public void selectionSort(int[] nums) {
  2.     int len = nums.length;
  3.     for (int i = 0; i < len; i++) {
  4.         int min = i;
  5.         for (int j = i + 1; j < len; j++) {
  6.             if (nums[j] < nums[min]) {
  7.                 min = j;
  8.             }
  9.         }
  10.         swap(nums, i, min);
  11.     }
  12. }

复杂度与稳定性

  • 时间复杂度：各种排序算法 - 图2。选择排序需要进行 各种排序算法 - 图3 次比较和 各种排序算法 - 图4 次交换。
  • 空间复杂度：各种排序算法 - 图5
  • 稳定性：不稳定。在交换过程会破坏原来相等数据项的相对位置。例如：[5, 8, 5, 2, 9]，在第一轮交换后，序列中的两个 5 的相对被破坏。

    冒泡排序

排序思路：从左到右不断交换相邻的逆序元素，在一轮循环后，可以让数组中的最大元素上浮到数组最右侧。
冒泡排序.gif

按此思路不断进行，每一轮都将未排序的最大元素上浮到右侧。在一轮循环中，如果未发生交换，说明数组已经有序，停止循环。

  1. public void bubbleSort(int[] nums) {
  2.     int len = nums.length;
  3.     for (int i = 0; i < len; i++) {
  4.         boolean flag = true;
  5.         for (int j = 0; j < len - i - 1; j++) {
  6.             if (nums[j] > nums[j + 1]) {
  7.                 swap(nums, j, j + 1);
  8.                 flag = false;
  9.             }
  10.         }
  11.         if (flag) {
  12.             break;
  13.         }
  14.     }
  15. }
  17. public void bubbleSort(int[] nums) {
  18.     int len = nums.length;
  19.     for (int i = len - 1; i > 0; i--) {
  20.         boolean flag = true;
  21.         for (int j = 0; j < i; j++) {
  22.             if (nums[j] > nums[j + 1]) {
  23.                 swap(nums, j, j + 1);
  24.                 flag = false;
  25.             }
  26.         }
  27.         if (flag) break;
  28.     }
  29. }

复杂度与稳定性

  • 时间复杂度：各种排序算法 - 图7。
  • 空间复杂度：各种排序算法 - 图8
  • 稳定性：稳定。

    插入排序

排序思路：从左至右开始，每次都将元素插入到左侧已经排序的数组中，插入后左侧数组仍然有序。
插入排序.gif

  1. public void insertionSort(int[] nums) {
  2.     int len = nums.length;
  3.     for (int i = 1; i < len; i++) {
  4.         for (int j = i; j > 0; j--) {
  5.             if (nums[j] < nums[j - 1]) {
  6.                 swap(nums, j, j - 1);
  7.             }
  8.         }
  9.     }
  10. }

复杂度与稳定性

  • 时间复杂度：取决于数组的初始顺序，如果数组已经部分有序，那么逆序较少，需要的交换次数也就较少，时间复杂也就越低。
    • 最坏情况下，当数组逆序时，时间复杂度为 各种排序算法 - 图10。
    • 最好情况下，当数组已经有序时，只需要进行 各种排序算法 - 图11 次比较和 0 次交换，时间复杂度为 各种排序算法 - 图12
  • 空间复杂度：各种排序算法 - 图13
  • 稳定性：稳定。

    希尔排序

对于大规模的数组，插入排序每次只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序解决了这种局限性，它利用增量 increment，使用插入排序和间隔 increment 的元素进行比较和交换。通过不断减小 increment，最后当 increment = 1 时，就恢复到了最原始的插入排序。

在不断减小 increment 的过程中，使得数组的变得越来越部分有序，最后当 increment = 1 时，即使恢复到最原始的插入排序，由于数组大部分都已经处于有序状态，从而降低了时间复杂度。
image.png
目前理想的 increment 增量公式为：各种排序算法 - 图15 （公式不唯一）

  1. public void shellSort(int[] nums) {
  2.     int len = nums.length;
  3.     int increment = 1;
  4.     // 设置初始增量
  5.     while (increment < len / 3) {
  6.         increment = increment * 3 + 1;
  7.     }
  8.     while (increment >= 1) {
  9.         for (int i = increment; i < len; i++) {
  10.             for (int j = i; j >= increment; j -= increment) {
  11.                 if (nums[j] < nums[j - increment]) {
  12.                     swap(nums, j, j - increment);
  13.                 }
  14.             }
  15.         }
  16.         increment = increment / 3;
  17.     }
  18. }

复杂度与稳定性

  • 时间复杂度：优于 各种排序算法 - 图16，但比 各种排序算法 - 图17 差。
  • 空间复杂度：各种排序算法 - 图18
  • 稳定性：不稳定

    堆排序

    二叉堆结构

二叉堆的本质一棵完全二叉树，但是它的存储方式并不是链式存储，而是顺序存储，二叉堆的所有节点都存放在数组中。使用数组存储可以利用索引下标来寻找父节点的子节点或子节点的父节点。计算方式如下：

  • 位置为 p 的节点的父节点的位置为：各种排序算法 - 图19；
  • 位置为 p 的节点的两个子节点的位置为：各种排序算法 - 图20 和 各种排序算法 - 图21

各种排序算法 - 图22
二叉堆可以分为两个类型：最大堆（大根堆）和最小堆（小根堆）。它们各自的特点如下：

  • 最大堆的任何一个父节点值，都大于或等于它左、右孩子的节点值。
  • 最小堆的任何一个父节点值，都小于或等于它左、右孩子的节点值。

二叉堆的根节点称为堆顶。根据上述特点可知：最大堆的堆顶元素是整个堆的最大元素；最小堆的堆顶元素是整个堆的最小元素。

上浮与下沉操作

在最大堆中，当一个节点比父节点大时，就需要交换这两个节点。交换后还可能比它新的父节点大，因此还需要不断地进行比较和交换，这种操作称为上浮。（最小堆也是同样的，当一个节点比父节点小时，进行上浮操作）
二叉堆上浮.gif
插入元素，然后将堆调整为最大堆。新插入元素会放到数组末尾。

  1. public static void upAdjust(int[] arr) {
  2.     // 新元素的下标：数组末尾
  3.     int childIndex = arr.length - 1;
  4.     int parentIndex = (childIndex - 1) / 2;
  5.     while (childIndex > 0 && arr[childIndex] > arr[parentIndex]) {
  6.         // 插入的元素 > 其父节点值，交换
  7.         swap(arr, childIndex, parentIndex);
  8.         // 继续和新的父节点进行比较
  9.         childIndex = parentIndex;
  10.         parentIndex = (childIndex - 1) / 2;
  11.     }
  12. }

同样，当一个节点比它的子节点小时，也需要不断地向下进行比较和交换操作，这种操作称为下沉。一个节点如果有两个子节点，应该与两个子节点中最大的节点进行交换。（最小堆就是与两个子节点中最小的节点交换）
二叉堆下沉.gif

  1. /**
  2.  * 最大堆的下沉操作
  3.  * @param arr    给定堆
  4.  * @param index    将 index 位置元素做下沉操作
  5.  * @param heapSize    堆的大小（数组长度）
  6.  *
  7.  */
  8. public static void downAdjust(int[] arr, int index, int heapSize) {
  9.     // index 元素的左孩子
  10.     int cIndex = index * 2 + 1;
  11.     // 不断向下，所以循环
  12.     while (cIndex < heapSize) {
  13.         // 如果存在右孩子，并且右孩子更大，则与右孩子交换
  14.         if (cIndex + 1 < heapSize && arr[cIndex + 1] > arr[cIndex]) {
  15.             cIndex++;
  16.         }
  17.         // 大于孩子节点时，说明已符合最大堆，结束循环
  18.         if (arr[index] > arr[cIndex]) {
  19.             break;
  20.         }
  21.         // 交换
  22.         swap(arr, index, cIndex);
  23.         // 继续向下比较
  24.         index = cIndex;
  25.         cIndex = index * 2 + 1;
  26.     }
  27. }

删除最大元素

一个最大堆的堆顶元素就是整个堆的最大元素，删除堆顶元素后，将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

  1. public static int delMax(int[] arr) {
  2.     int len = arr.length;
  3.     int max = arr[0];
  4.     swap(arr, 0, len - 1);
  5.     arr[len - 1] = null;
  6.     downAdjust(arr, 0, len);
  7.     return max;
  8. }

构建堆

构建二叉堆，就是把一个无序的完全二叉树调整为最大堆或最小堆。代码实现：让所有非叶子节点依次执行 “下沉” 操作。（根据下沉操作中的逻辑来决定是调整成最大堆还是最小堆）

  1. public static void buildHeap(int[] arr) {
  2.     // 第一个非叶子节点：arr.length / 2 - 1
  3.     for (int i = arr.length / 2 - 1; i >= 0; i--) {
  4.         downAdjust(arr, i, arr.length);
  5.     }
  6. }

堆排序

1. 构建堆

将无序数组构建成堆。需要升序排列时，构建成最大堆；需要降序排列时，构建成最小堆。

可以使用 “上浮” 操作或 “下沉” 操作构建堆。使用 “下沉” 操作构建堆时，只需要从第一个非叶子节点开始遍历即可。而叶子节点不需要进行 “下沉” 操作，因此无需遍历叶子节点，可以节省遍历所需要的时间。
上浮构建堆.gif

2. 交换栈顶元素与数组最后一个元素

构建堆后，栈顶元素已经是最大元素，相当于已经排序好了一个元素。然后将数组最后一个元素与栈顶元素交换，将栈顶元素利用 “下沉” 操作维持堆的有序状态。每一轮下沉后都可以找出未排序部分数组的最大元素，从而实现数组的整体排序。

3. 代码实现

堆排序实现升序

  1. public static void heapSort(int[] arr) {
  2.     int len = arr.length;
  3.     // 1. 构建堆
  4.     for (int i = len / 2 - 1; i >= 0; i--) {
  5.         downAdjust(arr, i, len);
  6.     }
  7.     // 2. 交换栈顶元素与数组最后一个元素
  8.     for (int i = len - 1; i > 0; i--) {
  9.         swap(arr, 0, i);
  10.         // 下沉栈顶元素
  11.         downAdjust(arr, 0, i);
  12.     }
  13. }
  15. public static void downAdjust(int[] arr, int index, int heapSize) {
  16.     int cIndex = index * 2 + 1;
  17.     while (cIndex < heapSize) {
  18.         if (cIndex + 1 < heapSize && arr[cIndex + 1] > arr[cIndex]) {
  19.             cIndex++;
  20.         }
  21.         if (arr[index] >= arr[cIndex]) {
  22.             break;
  23.         }
  24.         swap(arr, index, cIndex);
  25.         index = cIndex;
  26.         cIndex = index * 2 + 1;
  27.     }
  28. }

复杂度与稳定性

一个堆的高度为 各种排序算法 - 图26，因此在堆中插入元素和删除最大元素的复杂度都为 各种排序算法 - 图27。

初始化构建堆的时间复杂度：各种排序算法 - 图28。

  • 时间复杂度：
    • 堆排序需要将 N 个节点进行 “下沉” 操作，因此时间复杂度：各种排序算法 - 图29。
  • 空间复杂度：
    • 堆排序一种原地排序，因此空间复杂度：各种排序算法 - 图30。
  • 稳定性：
    • 不稳定排序。

      归并排序

归并排序的算法思想是分治，将一个大数组分割成两个小数组，两个小数组再继续分割，对各个小数组进行排序，最后合并起来。
归并排序.png

归并方法

将两个有序的数组合并成一个有序的数组。

  1. public void merge(int[] nums, int[] helper, int lo, int mid, int hi) {
  2.     for (int i = lo; i <= hi; i++) {
  3.         helper[i] = nums[i];    // 将数据复制到辅助数组
  4.     }
  5.     int left = lo;
  6.     int right = mid + 1;
  7.     for (int i = lo; i <= hi; i++) {
  8.         if (left > mid) {
  9.             nums[i] = helper[right++];
  10.         } else if (right > hi) {
  11.             nums[i] = helper[left++];
  12.         } else if (helper[left] <= helper[right]) {
  13.             nums[i] = helper[left++];
  14.         } else {
  15.             nums[i] = helper[right++];
  16.         }
  17.     }
  18. }

自顶向下归并排序

将一个大问题分解成若干个小问题，最后把小问题合并来解决大问题。

  1. public void mergeSort(int[] nums) {
  2.     int[] helper = new int[nums.length];
  3.     sort(nums, helper, 0, nums.length - 1);
  4. }
  6. public void sort(int[] nums, int[] helper, int lo, int hi) {
  7.     if (lo >= hi) {    // 递归出口
  8.         return;
  9.     }
  10.     int mid = lo + (hi - lo) / 2;
  11.     sort(nums, helper, lo, mid);
  12.     sort(nums, helper, mid + 1, hi);
  13.     merge(nums, helper, lo, mid, hi);
  14. }

复杂度与稳定性

  • 稳定性：
    • 合并时，如果遇到相等元素，先将左子数组中的相等元素移动会原数组可保证稳定性。
  • 时间复杂度：
    • 从图中可以看出每一层进行排序的时间都是 各种排序算法 - 图32，共有 各种排序算法 - 图33 层，所以时间复杂度为：各种排序算法 - 图34。

      在合并过程使用辅助数组

个人更喜欢这种写法

public int[] sortArray(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums;
}

public void mergeSort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    mergeSort(nums, lo, mid);
    mergeSort(nums, mid + 1, hi);
    merge(nums, lo, mid, hi);
}

public void merge(int[] nums, int lo, int mid, int hi) {
    int[] helper = new int[hi - lo + 1];
    int l = lo;
    int r = mid + 1;
    for (int i = 0; i < helper.length; i++) {
        if (l > mid) {
            helper[i] = nums[r++];
        } else if (r > hi) {
            helper[i] = nums[l++];
        } else if (nums[l] <= nums[r]) {
            helper[i] = nums[l++];
        } else {
            helper[i] = nums[r++];
        }
    }
    for (int i = 0; i < helper.length; i++) {
        nums[lo + i] = helper[i];
    }
}

快速排序

快速排序每一轮挑选一个基准元素，通过 partition() 操作将数组分为两个子数组，左子数组小于等于基准元素，右子数组大于基准元素。然后对这两个子数组递归这个过程，将子数组排序也就将整个数组排序了。
image.png

递归过程

public void quickSort(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
}

public void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int pivotIndex = partition(nums, lo, hi);
    quickSort(nums, lo, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, hi);
}

partition

选择基准元素最简单的方式是选择数组的第一个元素，但是对于一个原本是逆序的数组，比如：[8, 7, 6, 5, 4, 3, 2, 1]，如果选择第一个元素作为基准元素，此时会导致以该基准元素分割后的两个子数组元素数量过于悬殊，元素数量多的那个子数组进行递归操作就需要 各种排序算法 - 图36 的时间，进而整个快速排序算法的时间复杂度也退化成 各种排序算法 - 图37。

所以在这种极端情况下，可以随机选择数组中的一个元素作为基准元素，保证快速排序的时间复杂度为 各种排序算法 - 图38。

单边循环

这里仍使用数组第一个元素作为基准元素 pivot。同时设置一个 mark 变量指向数组起始位置，mark 代表小于基准元素的区域边界。
image.png
接下来从基准元素的下一个位置开始遍历数组。

如果遍历到的元素大于基准元素，就继续往后遍历。

如果遍历到的元素小于基准元素，则需要做两件事：

  1. 把 mark 指针右移 1 为，因为小于 pivot 的区域边界增大了 1；
  2. 将遍历到的元素与 mark 指针所在位置的元素交换位置，因为这个元素归属于小于 pivot 的区域。

image.png
后续重复该过程。当遍历结束时，将 pivot 元素与 mark 指针所在位置的元素交换，此时就将数组分成了以 pivot 为基准元素的两个子数组，左子数组小于 pivot，右子数组大于 pivot。
image.png
然后对左右子数组重复上述过程，每一轮都可以确定一个基准元素的位置，最后将整个数组排好序。

public int partition(int[] nums, int lo, int hi) {
    int pivot = nums[lo];
    int mark = lo;
    for (int i = lo + 1; i <= hi; i++) {
        if (nums[i] < pivot) {
            mark++;
            swap(nums, i, mark);
        }
    }
    nums[lo] = nums[mark];
    nums[mark] = pivot;
    return mark;
}

双边循环

选择第一个元素作为基准元素 pivot，并设置两个指针 left 和 right，执行数组的最左和最右两个元素。
image.png
接下来进行第 1 次循环，从 right 指针开始，让指针所指向的元素和基准元素作比较。如果大于或等于 pivot，则指针向左移动；如果小于 pivot 则 right 指针停止移动，切换到 left 指针。

在图中数组，因为 1 < 4，所以 right 直接停止移动，换到 left 指针。

left 指针所指向的元素和基准元素作比较。如果小于或等于 pivot，则指针向右移动；如果大于 pivot ，则 left 指针停止移动。

由于 left 开始指向的是基准元素，判断肯定相等，所以 left 右移 1 位。
image.png
此时 7 > 4，所以 left 指针停止移动。这时让 left 和 right 指针所指向的元素进行交换。
image.png
接下来开始下一次循环，重复上述过程。最后当 left 和 right 重合时，整个循环结束，将 pivot 与重合点元素进行交换。
image.png

public int partition(int[] nums, int lo, int hi) {
    int pivot = nums[lo];
    int left = lo;
    int right = hi;
    while (left != right) {
        // 这里需要先进行 right 指针的判断，因为 left 指针一定会向前移动 1 步。
        while (left < right && nums[right] > pivot) {
            right--;
        }
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        if (left < right) {
            // 当 left 所在元素大于 pivot, right 所在元素小于 pivot，交换。
            swap(nums, left, right);    
        }
    }
    nums[lo] = nums[left];
    nums[left] = pivot;
    return left;
}

随机快排

在数组中随机选择一个数来作为基准元素。

public void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int r = lo + (int)(Math.random()*(hi - lo + 1));
    swap(nums, lo, r);
    int pivotIndex = partition(nums, lo, hi);
    quickSort(nums, lo, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, hi);
}

复杂度与稳定性分析

  • 时间复杂度：
    • 最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下时间复杂度为 各种排序算法 - 图46。
    • 最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，依次这样。这种情况下时间复杂度为 各种排序算法 - 图47。为了防止这种情况的方法，可以在使用随机选取基准元素，或者在进行快速排序时将数组随机打乱。
  • 空间复杂度：
    • 最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下时间复杂度为 各种排序算法 - 图48 。也就是辅助栈的深度为 各种排序算法 - 图49
    • 最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，依次这样。这种情况下空间复杂度为 各种排序算法 - 图50。
  • 稳定性：
    • 不稳定。

      总结

      排序算法的比较

      | 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | | —- | —- | —- | —- | | 选择排序 | ❌ | 各种排序算法 - 图51 | 各种排序算法 - 图52 | | 冒泡排序 | ✅ | 各种排序算法 - 图53 | 各种排序算法 - 图54 | | 插入排序 | ✅ | 各种排序算法 - 图55 ~ 各种排序算法 - 图56 | 各种排序算法 - 图57 | | 希尔排序 | ❌ | 各种排序算法 - 图58 ~ 各种排序算法 - 图59 | 各种排序算法 - 图60 | | 堆排序 | ❌ | 各种排序算法 - 图61 | 各种排序算法 - 图62 | | 归并排序 | ✅ | 各种排序算法 - 图63 | 各种排序算法 - 图64 | | 快速排序 | ❌ | 各种排序算法 - 图65 | 各种排序算法 - 图66 |