排序算法

稳定排序

概念

对于多个相同的值，它们的相对位置不发生改变

分类

• 插入
• 冒泡
• 归并

插入排序

• 时间复杂度：O(n) ~ O(n^2)

口诀

• 将数组分成 【以排序区】 和 【待排序区】
• 将 【待排序区】 第一个元素，向前插入到 【已排序区】
• 直到 【待排序区】 没有元素为止
• 默认第一个为【以排序区】元素

代码演示

void insert_sort(int *num, int n) { //升序 
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0; j--) {
            if (num[j] < num[j - 1]) {
                swap(num[j], num[j - 1]);
            } else break;
        }
    }
    return ;
}

冒泡排序

• 时间复杂度：O(n ^ 2)

口诀

• 将数组分为【已排序区】和【待排序区】
• 从头到尾扫描【待排序区】，若前面元素比后面元素大，就交换
• 每一轮都会将【待排序区】中最大元素放到【已排序区】头部元素
• 直到【待排序区】没有元素

代码演示

#include <stdio.h>

void f(int *a, int n) {
    printf("未排序：\n");
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n排序过程：\n");
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] < a[j]) {
                int tm = a[i];
                a[i] = a[j];
                a[j] = tm;
            }
        }
        for (int i = 0; i < 10; i++) {
                printf("%d ", a[i]);
            }
            printf("\n");
    }
    
    return ;
}

void bubble_sort(int *num, int n) { //未优化的
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (num[j] <= num[j + 1]) continue;
            else swap(num[j], num[j + 1]);
        }
    }
    return ;
} 
void bubble_sort(int *num, int n) { //优化过的
    int times = 1; 
    for (int i = 1; i < n && times; i++) {
        times = 0;
        for (int j = 0; j < n - i; j++) {
            if (num[j] <= num[j + 1]) continue;
            swap(num[j], num[j + 1]);
            times = 1;
        }
    }
    return ;
} 

归并排序

• 时间复杂度：O(nlog(n))

• 属于稳定排序

• 属于外部排序

• 分治思想

• 二路归并

• K路归并 ：利用堆实现

口诀

• 大事化小，小事化了

代码演示

void merge_sort(int *num, int l, int r) {
    if (r - l <= 1) {
        if (r - l == 1 && num[r] < num[l]) {
            swap(num[l], num[r]);
        }
        return ;
    }
    int mid = (l + r) >> 1;
    merge_sort(num, l, mid);
    merge_sort(num, mid + 1, r);
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int p1 = l, p2 = mid + 1, k = 0;
    while (p1 <= mid || p2 <= r) {
        if (p2 > r || (p1 <= mid && num[p1] <= num[p2])) {
            temp[k++] = num[p1++];
        } else {
            temp[k++] = num[p2++];
        }
    }
    memcpy(num + l, temp, sizeof(int) * (r - l + 1));
    free(temp);
    return ;
}

不稳定排序

四象限法则