【数据结构】排序

参考：
图解算法数据结构
leetcode题解

• How to choose：
• 如果对时间复杂度要求比较高并且键的分布范围比较广，可以使用归并排序、快速排序和堆排序。
• 如果不能使用额外的空间，那么快速排序和堆排序都是不错的选择。
• 如果规定了排序的键的范围，可以优先考虑使用桶排序。
• 如果不想写太多的代码同时时间复杂度没有太高的要求，可以考虑冒泡排序、选择排序和插入排序。
• 如果排序的过程中没有复杂的额外操作，直接使用编程语言内置的排序算法就行了。

冒泡排序

从前往后（或从后往前比较两个元素，若逆序则交换）

• 内循环（相邻双指针比较） + 外循环（重复内循环）
• 标志位优化：如果在某轮内循环中未执行任何交换操作，说明数组已经完成排序，直接返回结果

public int[] BubbleSort(int[] nums) {
    int n = nums.length;
    for(int i = 0; i < n - 1; i++){
        boolean flag = false;
        for(int j = 0; j < n - i - 1; j++){ // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
            if(nums[j] > nums[j+1]){
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
                flag = true;
            }
        }
        if(!flag) break; //此轮“冒泡”未交换任何元素，直接跳出
    }
    return nums;
}

选择排序

在待排序元素中选取最小（最大）的元素加入序列

与冒泡排序的区别是：冒泡在每个内循环都会交换，而选择只会在外循环交换

public int[] sortArray(int[] nums) {
    int n = nums.length;
    for(int i = 0; i < n; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(nums[j] < nums[min]) min = j;
        }
        if(min != i){
            int tmp = nums[i];
            nums[i] = nums[min];
            nums[min] = tmp;
        }
    }
    return nums;
}

插入排序

遍历整个数组，保持左侧的始终是排序好的数组，将当前元素插入到左侧对应的位置。

void insertionSort(int[] nums) {
    // 外循环：已排序区间为 [0, i-1]
    for (int i = 1; i < nums.length; i++) {
        int base = nums[i], j = i - 1;
        // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        nums[j + 1] = base;        // 将 base 赋值到正确位置
    }
}

希尔排序

进行多次的、间隔的插入排序

public int[] sortArray(int[] nums) {
    int n = nums.length;
    int gap = n >> 1; // gap首先取nums.length的一半
    while (gap > 0) {
        for (int index = 0; index < gap; index++) { //多次的
            //间隔的
            for (int i = index + gap; i < n; i += gap) {
                int j = i;
                while (j > index && nums[j] < nums[j - gap]) {
                    int tmp = nums[j];
                    nums[j] = nums[j - gap];
                    nums[j - gap] = tmp;
                    j -= gap;
                }
            }
        }
        gap >>= 1; // gap除2
    }
    return nums;
}

归并排序

分治思想：将两个或多个已经有序的序列合并成一个
先划分【中点处】后合并

void mergeSort(int[] nums, int left, int right) {
    if (left >= right) return; // 当子数组长度为 1 时终止递归
    // 划分
    int mid = (left + right) / 2;  // 中点处
    mergeSort(nums, left, mid); // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并
    merge(nums, left, mid, right);
}

/* 合并左子数组和右子数组 */
void merge(int[] nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    int[] tmp = new int[right - left + 1];
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

快速排序

1. 取一个枢轴pivot作为基准值
2. 哨兵划分：将大于pivot的值排到右边，小于pivot的值排到左边
3. 递归左子表：重复步骤1、2
4. 递归右子表：重复步骤1、2

public int[] sortArray(int[] nums) {
    int l = 0, r = nums.length - 1;
    quickSort(nums, l, r);
    return nums;
}
void quickSort(int[] nums, int l, int r){
    if(l >= r) return;
    int pivot = partition(nums, l, r); // 步骤2
    quickSort(nums, l, pivot - 1); // 步骤3
    quickSort(nums, pivot + 1, r); // 步骤4
}
int partition(int[] nums, int l, int r){
    int i = l, j = r;  //步骤1：选取最左边元素为pivot
    while(i < j){
        while(i < j && nums[j] >= nums[l]) j--; //大的放左边
        while(i < j && nums[i] <= nums[l]) i++; //小的放右边
        swap(nums, i, j);
    }
    swap(nums, l, i);
    return i;
}
void swap(int[] nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
    return;
}

• 优化：

  • 随机pivot：在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为pivot。【解决输入数组是完全倒序的最差情况】

  • 尾递归：每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() 【完全有序的输入数组在每次划分时占用栈帧空间大】

public int[] sortArray(int[] nums) {
    int l = 0, r = nums.length - 1;
    quickSort(nums, l, r);
    return nums;
}
void quickSort(int[] nums, int l, int r){
    if(l >= r) return;
    int pivot = partition(nums, l, r); // 步骤2
    // 😊尾递归优化
    if (pivot - l < r - pivot) {
        quickSort(nums, l, pivot - 1); // 递归排序左子数组
        l = pivot + 1; // 剩余未排序区间为 [pivot + 1, r]
    } else {
        quickSort(nums, pivot + 1, r); // 递归排序右子数组
        r = pivot - 1; // 剩余未排序区间为 [l, pivot - 1]
    }
}
// 😊随机pivot优化
/* 选取三个候选元素的中位数 */
int medianThree(int[] nums, int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m 在 l 和 r 之间
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l 在 m 和 r 之间
    return right;
}

int partition(int[] nums, int l, int r){
	// 😊随机pivot优化
	int m = medianThree(nums, l, (l + r) / 2, r); // 选取三个候选元素的中位数
	swap(nums, l, m);  // 将中位数交换至数组最左端
    int i = l, j = r;  //步骤1：选取最左边元素为pivot
    while(i < j){
        while(i < j && nums[j] >= nums[l]) j--; //大的放左边
        while(i < j && nums[i] <= nums[l]) i++; //小的放右边
        swap(nums, i, j);
    }
    swap(nums, l, i);
    return i;
}
void swap(int[] nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
    return;
}

• 快排为什么快：
  • 虽然快速排序的最差时间复杂度为$O(n^2)$，没有归并排序稳定，但在绝大多数情况下，快速排序能在$O(n\text{log}n)$的时间复杂度下运行，出现最差情况的概率很低。
  • 在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性，缓存使用效率较低。
  • 快速排序的比较、赋值、交换等操作的总数量最少，复杂度的常数系数小。

堆排序

1. 建大顶堆
2. 循环：交换堆顶元素和堆底元素 —> 堆长度-1 ——>自顶向下调整堆(即堆化）
3. n - 1次循环后 升序排序完成

void heapSort(int[] nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1, int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma]) ma = l;
        if (r < n && nums[r] > nums[ma]) ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) break;
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}