排序合集

秃头王

算法基础

发布于：2021年3月14日

次浏览

怎么区分稳定还是不稳定

如果在原序列里面两个数是相同的，那么排完序位置没有发生变化那么这个排序就是稳定的，如果发生变化那么这个排序就是不稳定的。

冒泡排序（稳定）

考虑冒泡排序的复杂度，对于拥有N个字母的字符串，最多需要交换 N*(N - 1) / 2 次（完全逆序）

快速排序（不稳定）

随机快速排序过程

确定分界点（也叫选择基准数）：$q[L], q[(L + R) / 2], q[R]$

调整区间：

递归：处理左右两端排序，如果左右两侧都排序好了在合并一起那么就是一个有序的序列了

（暴力）版

可以先开辟两个空的数组 a[] 和 b[]
在 L 到 R 区间内扫描一遍把 >= x 和 <= x 的数拆分出来放到 a, b 数组 $q[L - R] $

$q[i] <= x, q[i] - > a[]$ // q[i] <= x 就它放到 a 数组里面

$q[i] >= x, q[i] -> b[]$ // q[i] >= x 就它放到 b 数组里面
$a[] -> q[], b[]->q[]$ //在把 a，b 数组数据在合并到 q 数组里面

（基础）版

我们可以定义两个指针从线段两侧往中间走只要（i < j) 红色i 蓝色j，如果红色指针要小于基准数那么i++, 如果红色指针要大于基准数了，那么判断j指针数是否大于基准值如果大于那么j++, 如果小于那么交换i, j 指针。

/*************************************************************************
        > File Name: Demo15.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2021年03月16日 星期二 20时37分05秒
 ************************************************************************/

#include<stdio.h>

#define MAX_N 100000

#define swap(a, b) {\
    a ^= b, b ^= a, a ^= b;\
}

int q[MAX_N + 10];

void quick_sort(int l, int r) {
    if (l >= r) return ;
    // 如果下面递归左右 选的是j的话 基准指数一定不能选 q[r] 要不然回发生边界问题
    int x = q[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    // 遍历左侧
    quick_sort(l, j);
    // 遍历右侧
    quick_sort(j + 1, r);
    return ;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", q + i);
    }
    quick_sort(0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
    return 0;
}