排序算法汇总

常见排序算法的汇总。

简单排序法

冒泡排序

// 冒泡排序，O(n^2)，稳定排序
void bubble_sort(int* a, int len) {
    for (int i = len - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

选择排序

// 选择排序，O(n^2)，不稳定排序
void select_sort(int* a, int len) {
    for (int i = 0; i < len - 1; i++) {
        int mn = INF, flag = 0;
        for (int j = i; j < len; j++) {
            if (a[j] < mn) {
                flag = j;
                mn = a[j];
            }
        }
        swap(a[i], a[flag]);
    }
}

插入排序

// 插入排序，O(n^2)，稳定排序
void insert_sort(int* a, int len) {
    for (int i = 1; i < len; i++) {
        int val = a[i], pos = i;
        while (pos > 0 && a[pos - 1] > val) {
            a[pos] = a[pos - 1];
            pos--;
        }
        a[pos] = val;
    }
}

高效排序法

快速排序

// 快速排序，O(nlogn)，不稳定排序
void quick_sort(int* a, int l, int r) {
    if (l >= r)return;

    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

归并排序

// 归并排序，O(nlogn)，稳定排序
void merge_sort(int* a, int l, int r) {
    if (l >= r)return;

    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] < a[j])tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)tmp[k++] = a[j++];

    for (int i = l, j = 0; i <= r; i++, j++)
        a[i] = tmp[j];
}

希尔排序

// 希尔排序，O(?)，不稳定排序
// 希尔排序有多种增量序列取法，这里给出两种:

/*1.折半降低序列，效率不高，可以看作O(n^2)*/
void shell_sort_1(int *a, int len) {
    for (int delta = len >> 1; delta > 0; delta >>= 1) {
        for (int i = delta; i < len; i++) {
            for (int j = i; j >= delta && a[j - delta] > a[j]; j -= delta) {
                swap(a[j - delta], a[j]);
            }
        }
    }
}

/*2.by Knuth：1, 4, 13, 40, ...，约为O(n^1.5)*/
void shell_sort_2(int* a, int len) {
    int delta = 1;
    while (delta < len / 3) delta = delta * 3 + 1;
    for (; delta > 0; delta /= 3) {
        for (int i = delta; i < len; i++) {
            for (int j = i; j >= delta && a[j - delta] > a[j]; j -= delta) {
                swap(a[j - delta], a[j]);
            }
        }
    }
}

堆排序

// 堆排序，O(nlogn)，不稳定排序
void up(int* a, int u) {
    while (u > 0) {
        int p = (u - 1) >> 1;
        if (a[p] >= a[u]) break;
        swap(a[p], a[u]);
        u = p;
    }
}

void down(int* a, int last, int u) {
    int cl = (u << 1) + 1;
    while (cl <= last) {
        if (cl + 1 <= last && a[cl] < a[cl + 1]) ++cl;
        if (a[u] >= a[cl]) break;
        swap(a[u], a[cl]);
        u = cl;
        cl = (u << 1) + 1;
    }
}

void heap_sort(int* a, int len) {
    for (int i = 0; i < len; i++) up(a, i);
    int last = len - 1;
    while (last > 0) {
        swap(a[0], a[last--]);
        down(a, last, 0);
    }
}

基数排序

// 基数排序，O(k*n)，稳定排序 (k表示最大元素的位数)
void radix_sort(int* a, int len) {
    int bucket[10][100]; // 第二维不小于元素个数len
    int counts[10];
    for (int i = 0; i < 10; i++)counts[i] = 0;
    
    int mx = a[0];
    for (int i = 1; i < len; i++) mx = max(mx, a[i]);
    int mxlen = 0;
    while (mx > 0) mxlen++, mx /= 10;

    for (int i = 0, n = 1; i < mxlen; i++, n *= 10) {
        for (int j = 0; j < len; j++) {
            int digit = a[j] / n % 10;
            bucket[digit][counts[digit]] = a[j];
            counts[digit]++;
        }
        int index = 0;
        for (int k = 0; k < 10; k++) {
            if (counts[k] > 0) {
                for (int l = 0; l < counts[k]; l++) {
                    a[index++] = bucket[k][l];
                }
                counts[k] = 0;
            }
        }
    }
}