首页 > 编程语言 >排序算法

排序算法

时间:2022-10-15 23:12:23浏览次数:48  
标签:sort arr int flag 算法 test 排序

内部排序:

  1. 稳定排序(冒泡、插入、归并):重复的元素一定按原始顺序排列

  2. 非稳定排序(选择、快排)

外部排序:多路归并排序

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

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

#define TEST(arr, n, func) { \
    int *arr_test = (int *)malloc(sizeof(int) * n); \
    memcpy(arr_test, arr, sizeof(int) * n); \
    output(arr_test, n); \
    printf("%s = ", #func); \
    func(arr_test, n); \
    output(arr_test, n); \
    free(arr_test); \
    printf("\n"); \
}

void bubble_sort(int *arr, int n) {
    int flag = 1;
    for (int i = 0; i < n - 1 && flag; i++) {
        flag = 0; //如果flag始终没有被改变过,则证明序列已经是有序的
        for (int j = n - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
                flag = 1;
            }
        }
    }
    return;
}

void insert_sort(int *arr, int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr[j], arr[j - 1]);
        }
    }
    return;
}

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

void merge_sort(int *arr, int n) {
    merge_sort_recur(arr, 0, n - 1);
    return;
}

void select_sort(int *arr, int n) {
    for (int i = 0; i < n; i++) {
        int index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[index]) index = j;
        }
        swap(arr[i], arr[index]);
    }
    return;
}

void quick_sort_recur(int *arr, int l, int r) {
    if (l >= r) return;
    int x = l, y = r, base = arr[l];
    while (x < y) {
        while (x < y && arr[y] >= base) y--;
        if (x < y) swap(arr[x], arr[y]);
        while (x < y && arr[x] <= base) x++;
        if (x < y) swap(arr[x], arr[y]);
    }
    arr[x] = base;
    quick_sort_recur(arr, l, x - 1);
    quick_sort_recur(arr, x + 1, r);
    return;
}

void quick_sort(int *arr, int n) {
    quick_sort_recur(arr, 0, n - 1);
    return;

}

void randint(int *arr, int n) {
    while (n--) arr[n] = rand() % 100; //判断的时候不减,判断完就已经减了,所以n的范围是[MAX_N - 1, 0]
    return;
}

void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        i && printf(" ");
        printf("%d", arr[i]);
    }
    printf("]\n");
}

int main() {
    srand(time(0));
    #define MAX_N 20
    int arr[MAX_N];
    randint(arr, MAX_N);
    TEST(arr, MAX_N, bubble_sort);
    TEST(arr, MAX_N, insert_sort);
    TEST(arr, MAX_N, merge_sort);
    TEST(arr, MAX_N, select_sort);
    TEST(arr, MAX_N, quick_sort);
    #undef MAX_N
    return 0;
}

快排退化与改进!!!

标签:sort,arr,int,flag,算法,test,排序
From: https://www.cnblogs.com/Kelvin-Wu/p/16795306.html

相关文章

  • 【LeetCode-769. medium】最多能完成排序的块
    ​​力扣​​ 解题报告:注意这种【根据一个要求,将数组分成多个区间】类模型的问题(比如汽车加油站、加法表达式求和),套路就这三步:1、初始化2、for循环或者while,里面三步  ......
  • 比较排序算法概述
    文章目录​​排序​​​​ref​​​​排序的对象​​​​排序分类​​​​排序算法的稳定性SortAlgorithmStability​​​​性能分析​​​​比较排序算法的性能分析原则​......
  • 原来ShardingSphere也用雪花算法
    原来ShardingSphere也用雪花算法分布式主键的生成有很多实现方式,比如百度开源的UidGenerator、美团的Leaf、以及众所周知的雪花算法,而在分库分表的场景下,id要保证唯一性,分......
  • 力扣-148-排序链表
    采用归并排序对链表进行排序可以达到O(nlogn)的时间复杂度使用自底向上的迭代写法可以将空间复杂度从O(N)降低到O(1)但是官方的写法对我来说实在是太难以理解了,尝试了......
  • 代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节
    24.两两交换链表中的节点本题是一道模拟过程的题目。搞清楚两两交换的步骤之后,写出对应的代码也就不是难题了。不过在学习题解的过程中发现,两两交换的步骤也有很多种实现......
  • 快速排序
    voidquick_sort(intq[],intl,intr){if(l>=r)return;inti=l-1,j=r+1,x=q[l+r>>1];while(i<j){doi++;w......
  • 归并排序
    voidquick_sort(intq[],intl,intr){if(l>=r)return;inti=l-1,j=r+1,x=q[l+r>>1];while(i<j){doi++;w......
  • 拓扑排序
     拓扑排序是将有向无环图G的所有顶点排成一个线性序列,使得对图G中的任意两个顶点u、v,如果存在边u->v,那么在序列中u一定在v前面,这个序列又被称为拓扑序列。 注意是将所......
  • AcWing 算法提高课 通过递推求等比数列的和(防止使用逆元出现问题)
    基于分治的思想:  例题:https://www.acwing.com/problem/content/99/模板:求num^0+num^1+...+num^kconstintMOD=9901;intQuickExp(intbase,intexp){bas......
  • C语言习题:数组与选择排序、冒泡排序
    题目1.选择法排序。输入一个正整数n(1<n≤10),再输入n个整数,将它们从大到小排序后输出。试编写相应程序。2.冒泡法排序。输入一个正整数n(1<n≤10),再输入n个整数,将它们从......