about Sort

稳定排序/不稳定排序 「相同的元素 在排序前后 仍然处于相同顺序 $\rightarrow$ 稳定排序」

---

• 快速排序

Pivot 算法 「每次选择一个参考数 小于这个参考数的放在左边 大于它的放在右边 // 这个参考数当然也在合适的位置」

找出参考数之后 向左右部分递归调用Pivot算法 每次调用算法 会产生一个参考数 它一定会在最后正确的位置 如果参考数每次都处在中间位置 那么为O((nlogn))级别 但在最差情况下会退化到n^2

# 定义 pivot 函数，他会以数组第一个数作为参考数，并会按上述规则调整数组，并返回参考数的下标
def pivot(a):
    # 首先我们分析一下边界情况，首先如果只有一个数，这种情况下数组已经是有序的了，我们返回 -1 代表不需要再继续后面的过程。那如果是两个数的话，我们可以直接比较大小然后给出正确排序，也不需要 pivot 过程了。我们仍然返回 -1。
    if len(a) == 1:return -1
    if len(a) == 2:
        if a[0] > a[1]:
            a[0],a[1] = a[1],a[0]
        return -1
    # 那么接下来我们就得进行我们的算法了，首先按我们刚才说的，我们假设参考数是第一个值。同时我们定义两个指针，i 指向 1，j 指向末尾。
    pivot = a[0]
    i = 1; j = len(a)-1
    # 如果 i 和 j 还没重叠的话
    while i < j:
        # 我们比较 a[i] 和 pivot 的大小关系，直到碰到第一个 a[i] 大于 pivot，或者 i 等于 j 就退出
        while a[i] < pivot and i < j:
            i += 1
        # 对 a[j] 进行类似操作
        while a[j] > pivot and i < j:
            j -= 1
        # 如果 i, j 重合，就可以退出了
        if i == j:break
        # 交换 a[i], a[j] 继续算法
        a[i],a[j] = a[j],a[i]
    # 最后交换 pivot
    if a[i] > a[0]:
        a[0],a[i-1] = a[i-1],a[0]; i -=1
    else:
        a[0],a[i] = a[i],a[0]
    return i

// 完整的快排算法 就是对其进行左右递归.  下面的是严蔚敏的快速排序算法

int Partition(vector<int>& nums, int low, int high) {
    int pivot = nums[low];
    while (low < high) {
        while (low < high and nums[high] >= pivot) --high;
        nums[low] = nums[high];
        while (low < high and nums[low] <= pivot) ++low;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}

void QuickSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int pivot = Partition(nums, low, high);
        QuickSort(nums, low, pivot - 1);
        QuickSort(nums, pivot + 1, high);
    }
}

---

• 基数排序(桶排序) 桶排序是基数排序的特例

桶排序 在序列里值的范围 且这个范围不算太大时使用

是一种非常特殊的排序算法。在前面的课程中，我们有一道题目是要找数据流的中位数，限制是所有的数都在 1 到 100 以内。我们当时提到在这种限制下，可以将数字放到 1-100 的桶里，每个桶只记录当前数字的数量，从而将插入的复杂度从 O(n) 降低为
O(1)，这就是一个桶排序的思想。同样的，如果我们碰到这样的题目：

例题：有 10 万个整数，每个数范围在 [0,99] 之间。有若干查询，每个查询给定一个数 x，问比 x 小的数有多少。

对于这道题目，我们可以直接把数都拿过来排序，然后对每个 x 做一个二分查找，可以解决问题。但是通过桶排序我们可以有更优的解。

我们开一个数组，大小为 100，分别代表 0 到 99 每个数有多少个。然后我们遍历所有数据，记录每个数字的数量。最后统计的时候，我们只需要计算数组中下标小于 x 的数的总和就可以了。

后面统计的部分只有 0 到 100 的循环，所以查询的时间非常短。整体复杂度的瓶颈就在于开始时预处理数据，也就是 O(n)

基数排序

我们开一个长度为10的桶 把数据按照==最后一位==放到对应的桶里 形成一个序列

我们开一个长度为10的桶 把数据按照 ==倒数第二位== 放到对应的桶里 ⚠️ 同一个桶里的元素要按照上个序列的顺序放

我们开始一个长度为10的桶 把数据按照 ==倒数第三位== 放到对应的桶里 同理

---

• 冒泡排序 「优化 : 如果一轮里没有元素被交换 说明排序结束」

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            // 如果左边的数大于右边的数，则交换，保证右边的数字最大
            arr[j + 1] = arr[j + 1] + arr[j];
            arr[j] = arr[j + 1] - arr[j];
            arr[j + 1] = arr[j + 1] - arr[j];
        }
    }
}

---

• 选择排序 「不受输入状态影响 & 交换次数少(最多n次交换)」「选择排序的优化版本就是堆排序」

维护一个长度逐渐变长的窗口 这个窗口中的元素是已经排好序的了 每一次都把序列搜索一遍. 搜索n-1遍

vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n-1; ++i) {
            int index = i;
            for (int j = i+1; j < n; ++j) {
                index = nums[j] < nums[index] ? j : index;
            }
            swap (nums[i], nums[index]);
        }
        return nums;
    }

---

• 插入排序 「分为 向后腾挪和交换 两种方式」

public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        int currentNumber = arr[i];
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr[j + 1] = currentNumber;
    }
}

// 这种采取了交换的方式
public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        // j 记录当前数字下标
        int j = i;
        // 当前数字比前一个数字小，则将当前数字与前一个数字交换
        while (j >= 1 && arr[j] < arr[j - 1]) {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
            // 更新当前数字下标
            j--;
        }
    }
}