排序

本文最后更新于：2024年2月12日 晚上

Shopee-002. Shoffee

剑指 Offer 51. 数组中的逆序对

排序算法比较

算法 平均时间复杂度 最优时间复杂度 最坏时间复杂度 空间复杂度 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ 稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(k)$ 稳定
桶排序 $O(n+k)$ $O(n+k)$ $O(n^2)$ $O(n+k)$ 稳定
基数排序 $O(n\times k)$ $O(n\times k)$ $O(n\times k)$ $O(n+k)$ 稳定
希尔排序 $O(nlogn)$ $O(nlog^2n)$ $O(nlog^2n)$ $O(1)$ 不稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(logn)$ 不稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ 不稳定

空间复杂度：是指除了原数组外，需要开辟的额外空间的大小

稳定性是指：排序前后两个相等的数的相对位置不变

快速排序

思想：分而治之

时间复杂度：$O(nlogn)$，最坏情况下：$O(n^{2})$

空间复杂度：$O(logn)$，最坏情况下：$O(n)$

算法稳定性：不稳定

void quick_sort(int[] nums, int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = nums[l + r >> 1];
    while (i < j) {
        while (nums[++i] < x); // 找到左边第一个大于中点值的元素
        while (nums[--j] > x); // 找到右边第一个小于中点值的元素
        // 交换逆序对
        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    // 以 j 为分界点进行递归处理
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

为了提高快速排序效率，可以在数据接近有序时，将其打乱在进行快排：

static final Random random = new Random();
static void shuffleSort(int[] a) {
    int n = a.length;//shuffle, then sort 
    for (int i = 0; i < n; i++) {
        int oi = random.nextInt(n), temp = a[oi];
        a[oi] = a[i]; 
        a[i] = temp;
    }
    // Arrays.sort(a);
    quick_sort(a, 0, n - 1);
}

快速选择算法：QuickSelect

解决Top K问题，可以快速的从无序序列中找到第k小、k大的数字。原理和快速排序算法相同。

最优时间复杂度：$O(n)$

最坏时间复杂度：$O(n^{2})$

平均时间复杂度：$O(n)$

空间复杂度：$O(1)$

int quickSelect(int[] nums, int l, int r, int k) {
    // 说明序列已经排好序
    if (l == r) return nums[k];
    int i = l - 1, j = r + 1, x = nums[l + r >> 1];
    while (i < j) {
        while (nums[++i] < x); // 找到左边第一个大于中值的元素
        while (nums[--j] > x); // 找到右边第一个小于中值的元素
        // 交换逆序对
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    // 进行判断，k属于那段区间
    if (k <= j) return quickSelect(nums, l, j, k);
    else return quickSelect(nums, j + 1, r, k);
}

归并排序

时间复杂度：$O(NlogN)$

空间复杂度：$O(N)$，辅助数组空间

写法一

int[] tmp = new int[n]; // 辅助数组

static void mergeSort(int[] nums, int l, int r) {
    // stop
    if (l >= r) return;
    // 递归划分数组
    int mid = (l + r) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    // 开始合并数组: i， j分别表示左右子数组的左端点
    int i = l, j = mid + 1, idx = l;
    // 复制原数组该段数值
    for (int k = l; k <= r; k++) {
        tmp[k] = nums[k];
    }
    // 按照顺序将数值依次填入原数组
    while (i <= mid && j <= r) {
        if (tmp[i] <= tmp[j]) {
            nums[idx++] = tmp[i++];
            // 非逆序对的个数
            // ans += r - j + 1;
        } else {
            nums[idx++] = tmp[j++];
            // 逆序对的个数
            // ans += mid - i + 1;
        }
    }
    while (i <= mid) {
        nums[idx++] = tmp[i++];
    }
    while (j <= r) {
        nums[idx++] = tmp[j++];
    }
}

写法二

int[] tmp = new int[n]; // 辅助数组

static void mergeSort(int[] nums, int l, int r) {
    // stop
    if (l >= r) return;
    // 递归划分数组
    int mid = (l + r) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    // 开始合并数组: i， j分别表示左右子数组的左端点
    int i = l, j = mid + 1;
    // 复制原数组该段数值
    for (int k = l; k <= r; k++) {
        tmp[k] = nums[k];
    }
    // 按照顺序将数值依次填入原数组
    for (int k = l; k <= r; k++) {
        // 左边已经加完
        if (i == mid + 1) {
            nums[k] = tmp[j++];
        } else if (j == r + 1 || tmp[i] <= tmp[j]) { 
            // 右边已经加完或者左边小于右边
            nums[k] = tmp[i++];
            // 非逆序对的个数
            // cnt += r - j + 1;
        } else {
            // 左边当前元素大于右边元素，即存在逆序对
            // cnt += mid - i + 1; // 逆序对的个数
            nums[k] = tmp[j++];
        }
    }
}

堆排序

大顶堆

void siftDown(int[] arr, int l, int r) {
    // 计算父节点和子节点的下标
    int parent = l;
    int child = parent * 2 + 1;
    while (child <= r) { // 在下标范围内做比较
        // 先比较两个子节点的大小，选择最大的
        if (child + 1 <= r && arr[child] < arr[child + 1]) {
            child++;
        }
        // 如果父节点比最大的子节点大，代表调整完毕，直接跳出函数
        if (arr[parent] >= arr[child]) {
            return;
        } else {
            // 否则交换父子节点的值，子节点再和孙节点比较,直到交换完毕
            int t = arr[parent];
            arr[parent] = arr[child];
            arr[child] = t;
            parent = child;
            child = parent * 2 + 1;
        }
    }
}

void heapSort(int[] arr, int len) {
    // 从最后一个节点的父节点开始pushDown来初始化堆
    for (int i = (len - 1 - 1) / 2; i >= 0; i--) {
        siftDown(arr, i, len - 1);
    }
    // 先将第一个元素和已经排好的元素前一位做交换，再重新调整
    for (int i = len - 1; i > 0; i--) {
        // 将堆顶元素和堆末尾元素交换
        int t = arr[0];
        arr[0] = arr[i];
        arr[i] = t;
        // 重新调整堆使其满足有序状态
        siftDown(arr, 0, i - 1);
    }
}

小顶堆

void siftDown(int[] arr, int l, int r) {
    // 计算父节点和子节点的下标
    int parent = l;
    int child = parent * 2 + 1;
    while (child <= r) { // 在下标范围内做比较
        // 先比较两个子节点的大小，选择最小的
        if (child + 1 <= r && arr[child] > arr[child + 1]) {
            child++;
        }
        // 如果父节点比最小的子节点小，代表调整完毕，直接跳出函数
        if (arr[parent] <= arr[child]) {
            return;
        } else {
            // 否则交换父子节点的值，子节点再和孙节点比较,直到交换完毕
            int t = arr[parent];
            arr[parent] = arr[child];
            arr[child] = t;
            parent = child;
            child = parent * 2 + 1;
        }
    }
}

void heapSort(int[] arr, int len) {
    // 从最后一个节点的父节点开始pushDown来初始化堆
    for (int i = (len - 1 - 1) / 2; i >= 0; i--) {
        siftDown(arr, i, len - 1);
    }
    // 先将第一个元素和已经排好的元素前一位做交换，再重新调整
    for (int i = len - 1; i > 0; i--) {
        // 将堆顶元素和堆末尾元素交换
        int t = arr[0];
        arr[0] = arr[i];
        arr[i] = t;
        // 重新调整堆使其满足有序状态
        siftDown(arr, 0, i - 1);
    }
}