人型混淆器

2017-05-12

快速排序算法

本文迁移自吾得，原始链接为 https://wudew.com/posts/59

void qs(int l, int r) {
    if (l >= r) return;
    int m, t, i, j, k;

    m = (l + r) / 2;
    t = a[l];
    a[l] = a[m];
    a[m] = t;

    i = l;
    j = r;
    k = a[i];
    while (i < j) {
        while (i < j && a[j] > k) j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }
        while (i < j && a[i] < k) i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = k;
    qs(l, i - 1);
    qs(i + 1, r);
}

使用： 定义一个全局的 a[] 调用的时候 qs[0, n-1]

#include <stdio.h>
#include "stdlib.h"
#include "time.h"

int a[110], n;

void qs(int l, int r) {
    if (l >= r) return;
    int m, i, j, k, t;
    m = (l + r) / 2;
    t = a[l];
    a[l] = a[m];
    a[m] = t;

    i = l;
    j = r;
    k = a[i];
    while (i < j) {
        while (i < j && a[j] > k) j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }
        while (i < j && a[i] < k) i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = k;
    qs(l, i - 1);
    qs(i + 1, r);
}

void ms() {
    int i, j, f, t;
    for (i = 0; i <= n - 1; i++) {
        f = 0;
        for (j = 1; j <= n - i; j++)
            if (a[j] > a[j + 1]) {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                f++;
            }
        if (f == 0) break;
    }
}

int main() {
    int i, j, k, t, p;
    scanf("%d", &n);
    // 产生n个随机数保存在数组中
    srand(time(NULL));
    for (i = 1; i <= n; i++) a[i] = rand() % 100;
    // 输出排序之前n个数
    printf("排序前:");
    for (i = 1; i <= n; i++) printf("%d ", a[i]);
    // 排序
    ms(0, n - 1);
    // 输出排序之后n个数
    printf("\n排序后:");
    for (i = 1; i <= n; i++) printf("%d ", a[i]);
    getchar();
}