数据结构：八种常见排序算法

数据结构：八种常见排序算法 | 极客日志

void InsertSort(int* arr, int n) {
    //i 表示有序数组的最后一个值
    //arr[n-1] 后面没有待排序的数，所以 i<n-1
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = arr[end + 1];
        while (end >= 0) {
            if (arr[end] > tmp) //降序用"<"
                arr[end + 1] = arr[end];
            else
                break;
            end--;
        }
        arr[end + 1] = tmp;
    }
}

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

int main() {
    int arr[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    InsertSort(arr, size);
    printArr(arr, size);
    return 0;
}

void ShellSort(int* arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; //+1 是因为当 gap=1 时是直接插入排序
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

//优化后
void SelectSort(int* arr, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (arr[i] > arr[maxi]) {
                maxi = i;
            }
            if (arr[i] < arr[mini]) {
                mini = i;
            }
        }
        if (begin == maxi) {
            maxi = mini;
        }
        Swap(&arr[mini], &arr[begin]);
        Swap(&arr[maxi], &arr[end]);
        ++begin;
        --end;
    }
}

void BubbleSort(int* arr, int n) {
    int exchange = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange = 1;
                Swap(&arr[j], &arr[j + 1]);
            }
        }
        if (exchange == 0) {
            break;
        }
    }
}

//快速排序
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    //找基准值，并把基准值放到指定的位置上
    QuickSort(arr, left, meet - 1);
    QuickSort(arr, meet + 1, right);
}

// 找基准值，时间复杂度不是 n^2，而是 n，因为两层 while 循环只循环了一遍数组
int _QuickSort(int* arr, int left, int right) {
    int keyi = left;
    left++;
    while (left <= right) {
        //right:从右往左找小于基准值的
        while (left <= right && arr[right] > arr[keyi]) {
            --right;
        }
        //left：从左往右找大于基准值的
        while (left <= right && arr[left] < arr[keyi]) {
            ++left;
        }
        //这里找到 left 比基准值大，right 比基准值小
        if (left <= right)
            Swap(&arr[left++], &arr[right--]);
    }
    //right 的位置就是基准值的位置
    Swap(&arr[keyi], &arr[right]);
    return right;
}

//快速排序
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    //找基准值 keyi
    int keyi = _QuickSort(arr, left, right);
    //左右序列递归继续排序
    QuickSort(arr, left, keyi - 1);
    QuickSort(arr, keyi + 1, right);
}

int _QuickSort(int* arr, int left, int right) {
    int hole = left;
    int key = arr[hole];
    while (left < right) {
        while (left < right && arr[right] > key) {
            --right;
        }
        arr[hole] = arr[right];
        hole = right;
        while (left < right && arr[left] < key) {
            ++left;
        }
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;
    return hole;
}

int _QuickSort(int* arr, int left, int right) {
    int prev = left, cur = left + 1;
    int key = left;
    while (cur <= right) {
        if (arr[cur] < arr[key] && ++prev != cur) {
            Swap(&arr[cur], &arr[prev]);
        }
        ++cur;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

void QuickSortNonR(int* arr, int left, int right) {
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);
    while (!STEmpty(&st)) {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);
        // 单趟
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end) {
            if (arr[cur] < arr[keyi] && ++prev != cur)
                Swap(&arr[prev], &arr[cur]);
            ++cur;
        }
        Swap(&arr[keyi], &arr[prev]);
        keyi = prev;
        // [begin, keyi-1] keyi [keyi+1, end]
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}

void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) {
        return;
    }
    int mid = (right + left) / 2;
    // [left,mid] [mid+1,right]
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;
    //合并两个有序数组为一个数组
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) {
            tmp[index++] = arr[begin1++];
        } else {
            tmp[index++] = arr[begin2++];
        }
    }
    while (begin1 <= end1) {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2) {
        tmp[index++] = arr[begin2++];
    }
    for (int i = left; i <= right; i++) {
        arr[i] = tmp[i];
    }
}

void MergeSort(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(arr, 0, n - 1, tmp);
    free(tmp);
}

// 测试排序的性能对比
void TestOP() {
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();
    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();
    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();
    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();
    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - end4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
}

void CountSort(int* arr, int n) {
    //找 min，max
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    //确定数组大小 range
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    if (count == NULL) {
        perror("malloc fail");
        exit(1);
    }
    //对 count 初始化----calloc，memset
    memset(count, 0, sizeof(int) * range);
    // 统计次数
    //通过映射的方式将数组保存在 count 数组中
    //映射的方式==原数组的值-min
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    //将 count 数组中的数据还原到 arr 数组中
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) {
            arr[index++] = i + min;
        }
    }
    free(count);
}

//Sort.h
#pragma once
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>

//插入排序
//1）直接插入排序 <n^2
void InsertSort(int* arr, int n);
//2）希尔排序 n^1.3
void ShellSort(int* arr, int n);

//选择排序
//1）直接选择排序 n^2
void SelectSort(int* arr, int n);
//2）堆排序 nlogn
void HeapSort(int* arr, int n);

//交换排序
//1）冒泡排序 n^2
void BubbleSort(int* arr, int n);
//2）快速排序 nlogn
void QuickSort(int* arr, int left, int right);
//3)非递归版本的快速排序
void QuickSortNonR(int* arr, int left, int right);

//归并排序 nlogn
void MergeSort(int* arr, int n);

//非比较排序
void CountSort(int* arr, int n);

//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack {
    STDataType* arr; //数组
    int top; //有效数据的个数，也是栈顶
    int capacity; //栈的空间大小
} ST;

// 初始化栈
void STInit(ST* ps);
// 销毁栈
void STDestroy(ST* ps);
// 入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);

//Stack.c
#include"Stack.h"

// 初始化栈
void STInit(ST* ps) {
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

// 销毁栈
void STDestroy(ST* ps) {
    if (ps->arr)
        free(ps->arr);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

// 入栈
void STPush(ST* ps, STDataType x) {
    assert(ps); //先判断空间是否足够
    if (ps->top == ps->capacity) {
        //如果 capacity==0；不能直接*2
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    //空间足够
    ps->arr[ps->top++] = x;
}

//出栈
void STPop(ST* ps) {
    assert(!STEmpty(ps));
    ps->top--;
}

//取栈顶元素
STDataType STTop(ST* ps) {
    assert(!STEmpty(ps));
    return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps) {
    assert(ps); //传的参数指针不为空就行，有效数据个数可以为 0
    return ps->top;
}

//栈是否为空
bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0; //如果 top==0 就直接返回
}

//test.c
#include"Sort.h"

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

void test01() {
    //int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
    //int a[] = { 5, 3, 9, 6, 2, 4 };
    int a[] = {6, 1, 2, 7, 9, 3};
    int n = sizeof(a) / sizeof(a[0]);
    printf("排序之前:");
    printArr(a, n);
    //InsertSort(a,n);
    //ShellSort(a, n);
    //SelectSort(a, n);
    //QuickSort(a, 0, n - 1);
    //QuickSortNonR(a, 0, n - 1);
    //MergeSort(a, n);
    CountSort(a, n);
    printf("排序之后:");
    printArr(a, n);
}

// 测试排序的性能对比
void TestOP() {
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();
    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();
    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();
    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();
    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
}

int main() {
    test01();
    //TestOP();
    return 0;
}

数据结构：八种常见排序算法

1. 排序概念及应用

1.1 概念

1.2 常见排序算法

2. 实现常见排序算法

2.1 插入排序

2.1.1 直接插入排序

2.1.2 希尔排序

2.1.2.1 希尔排序的时间复杂度计算

2.2 选择排序

2.2.1 直接选择排序

2.2.2 堆排序

2.3 交换排序

2.3.1 冒泡排序

2.3.2 快速排序

2.3.2.1 hoare 版本（重要）

2.3.2.2 挖坑法

2.3.2.3 lomuto 前后指针（重要）

2.3.2.4 非递归版本（重要）

2.4 归并排序（重要）

2.5 测试代码：排序性能对比

2.6 非比较排序

2.6.1 计数排序

3. 排序算法复杂度及稳定性分析

更多推荐文章

相关免费在线工具

数据结构：八种常见排序算法

1. 排序概念及应用

1.1 概念

1.2 常见排序算法

2. 实现常见排序算法

2.1 插入排序

2.1.1 直接插入排序

2.1.2 希尔排序

2.1.2.1 希尔排序的时间复杂度计算

2.2 选择排序

2.2.1 直接选择排序

2.2.2 堆排序

2.3 交换排序

2.3.1 冒泡排序

2.3.2 快速排序

2.3.2.1 hoare 版本（重要）

2.3.2.2 挖坑法

2.3.2.3 lomuto 前后指针（重要）

2.3.2.4 非递归版本（重要）

2.4 归并排序（重要）

2.5 测试代码：排序性能对比

2.6 非比较排序

2.6.1 计数排序

3. 排序算法复杂度及稳定性分析

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具