排序算法总结 - C实现

日期：

桶排序 Bucket Sort

  • 时间复杂度 \(O(n)\)
  • 算法描述 ： 创建一个元素全为 0 的数组，将数组下标作为元素值，遍历原始数组，每出现一次元素则对应的数组下标加一，最后对新数组按序输出。
  • 算法实现 ： 过于简单，并未实现。

冒泡排序 Bubble Sort

  • 时间复杂度 \(O(n^2)\)
  • 算法描述 ： 通过多次循环遍历数组，比较相邻两个元素大小，依次将（最小/最大）元素冒泡到数组末尾实现排序。
  • 算法实现 ： 如下。
#include <stdio.h>
#include <stdlib.h>

// 打印数组
void show(int *arr, int arrlen){
    for (int i = 0; i < arrlen; i++) printf("%d ", arr[i]);
    printf("\n");
}

// 交换两个变量的值
void swap(int * a, int * b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序
void sort(int *arr, int arrlen){
    for (int endAt = arrlen - 1; endAt > 0; endAt--) {
        for (int i = 0; i < endAt; i++) {
            if (arr[i] < arr[i + 1]) {
                swap(&arr[i], &arr[i + 1]);
                // show(arr, arrlen);
            }
        }
    }
}

int main(){
    int demo[10] = {3, 1, 0, 5, 6, 8, 9, 3, 7, 4};
    int len = sizeof(demo) / sizeof(demo[0]);
    show(demo, len); // 打印原始数组
    sort(demo, len); // 冒泡排序
    show(demo, len); // 打印排序后数组
    return 0;
}

快速排序 Quick Sort

  • 时间复杂度 \(O(n\log n)\)
  • 算法描述
  1. 将数组第一个元素作为基准，并设置左、右指针，右指针向左，左指针向右移动。
  2. 从右指针开始，遇到大等于基准的元素则继续向左移动，遇到小于基准的则将该元素覆盖到左指针上。
  3. 然后固定右指针，并将左指针向右移动，遇到小等于基准的元素则继续向右移动，遇到大于基准的则将该元素覆盖到右指针上。
  4. 交替执行，直至左右指针相遇，将基准元素覆盖到之上，此时基准处于正确的排序位置，且数组左侧都小于基准，数组右侧都大于基准。
  5. 对基准左侧和右侧分别进行如上操作。
  • 算法实现 ： 如下。
#include <stdio.h>
#include <stdlib.h>

// 打印数组
void show(int *arr, int arrlen){
    for (int i = 0; i < arrlen; i++) printf("%d ", arr[i]);
    printf("\n");
}

// 快速排序
void sort(int *arr, int arrlen, int left, int right){
    if ( left >= right ) return;
    int pointLeft = left, pointRight = right, base = arr[left], temp;
    while ( pointLeft < pointRight) {
        while (arr[pointRight] >= base && pointRight > pointLeft) pointRight--;
        arr[pointLeft] = arr[pointRight];
        while (arr[pointLeft] <= base && pointRight > pointLeft) pointLeft++;
        arr[pointRight] = arr[pointLeft];
    }
    arr[pointLeft] = base;
    sort(arr, arrlen, left, pointLeft - 1);
    sort(arr, arrlen, pointLeft + 1, right);
}

int main(){
    int demo[6] = {3, 11, 0, 5, 5, 100};
    int len = sizeof(demo) / sizeof(demo[0]);
    show(demo, len); // 打印初始数组
    sort(demo, len, 0, len - 1); // 快速排序
    show(demo, len); // 打印排序后数组
    return 0;
}



评论

发表评论