排序

比较

分类

• 比较排序的时间复杂度的下界O(nlogn)

  对于n个待排序元素，在未比较时，可能的正确结果有n!种。在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种（确定之前两个元素的前后位置的情况是相同，确定之后相当于少了一半的可能性）。依次类推，直到经过m次比较，剩余可能性n!/(2^{m)种。直到n!/(2}m)<=1时，结果只剩余一种。根据斯特灵公式，此时的比较次数m为o(nlogn)次。所以基于排序的比较算法，最优情况下，复杂度是O(nlogn)的。

源码

• Sort.cpp

/**
 * @file Sort.cpp
 * @author Sprinining (Sprinining@gmail.com)
 * @brief   交换排序：冒泡排序、快速排序
 *          选择排序：普通选择排序、堆排序
 *          插入排序：直接插入排序、二分插入排序、希尔排序
 *          归并排序：普通归并排序
 *          分布排序：计数排序、桶排序、基数排序
 * @version 0.1
 * @date 2022-05-06
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) { return *(int*)(a) - *(int*)b; }

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// a, b不能是同一个地址的东西，否则会把该地址清零
void swap2(int* a, int* b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void display(int* ary, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", ary[i]);
    }
    puts("");
}

// 1.冒泡排序
void bubbleSort(int* array, int size) {
    // 比较size-1轮
    for (int i = 0; i < size - 1; i++) {
        // 是否已经有序了
        bool isSorted = true;
        // 每一轮都会有个大元素移到后面
        for (int j = 0; j < size - 1 - i; j++) {
            // 将相邻的两个比较，大的移到后面
            if (array[j] > array[j + 1]) {
                // 有交换的说明没排好
                isSorted = false;
                swap(&array[j], &array[j + 1]);
            }
        }
        if (isSorted == true) break;
    }
    display(array, size);
}

void quickSortRecursive(int* array, int left, int right) {
    if (left >= right) return;
    int i = left;
    int j = right;
    // 基准元素
    int key = array[left];
    // 分成两半，左边小于基准元素，右边大于基准元素
    while (i < j) {
        // 从右往左找第一个小于key的
        while (i < j && array[j] >= key) {
            j--;
        }
        // 与key交换
        if (i < j) {
            array[i] = array[j];
            // array[j]不用立刻放入key，后面可能会有比key大的元素防止这
            i++;
        }
        // 从左往右找第一个大于key的
        while (i < j && array[i] <= key) {
            i++;
        }
        // 与key交换
        if (i < j) {
            array[j] = array[i];
            j--;
        }
    }
    // 循环退出时i=j
    array[i] = key;
    quickSortRecursive(array, left, i - 1);
    quickSortRecursive(array, i + 1, right);
}

// 2.快速排序
void quickSort(int* array, int size) {
    quickSortRecursive(array, 0, size - 1);
    display(array, size);
}

// 3.普通选择排序
void selectionSort(int* array, int size) {
    // size-1轮
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        // 从后面找更小的
        for (int j = i + 1; j < size; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 确实有更小的
        if (minIndex != i) {
            swap(&array[i], &array[minIndex]);
        }
    }
    display(array, size);
}

// 自顶向下调整堆顶（只有堆顶不符合堆的定义）
void adjustHeap(int* array, int currentIndex, int size) {
    int temp = array[currentIndex];
    int leftChildIndex = 2 * currentIndex + 1;

    while (leftChildIndex <= (size - 1)) {
        // 找更大点的子节点
        if (leftChildIndex < (size - 1) &&
            array[leftChildIndex] < array[leftChildIndex + 1]) {
            leftChildIndex++;
        }
        if (array[leftChildIndex] <= temp) break;
        // 与子节点交换
        array[currentIndex] = array[leftChildIndex];
        currentIndex = leftChildIndex;
        leftChildIndex = 2 * currentIndex + 1;
    }
    array[currentIndex] = temp;
}

// 4.堆排序
void heapSort(int* array, int size) {
    // 从第一个非叶子节点开始，自底向上
    for (int i = (size - 2) / 2; i >= 0; i--) {
        adjustHeap(array, i, size);
    }
    printf("建堆：");
    display(array, size);
    // size-1轮
    for (int i = 1; i < size; i++) {
        swap(&array[0], &array[size - i]);
        // 已经是堆了，在修改完堆顶后只需要对堆顶进行重定位
        adjustHeap(array, 0, size - i);
    }
    display(array, size);
}

// 5.直接插入排序
void insertionSort(int* array, int size) {
    // size-1轮
    // [0, i-1]是有序序列
    for (int i = 1; i < size; i++) {
        // 待插入的元素
        int temp = array[i];
        // 插入已经有序的序列
        // 从有序序列的末尾往前找第一个小于等于temp的
        int j = i - 1;
        while (j >= 0 && (array[j] > temp)) {
            // 边找边把不符合的元素后移
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }

    display(array, size);
}

// 6.二分插入排序
void binaryInsertionSort(int* array, int size) {
    for (int i = 1; i < size; i++) {
        int temp = array[i];
        // 二分查找插入位置
        int left = 0;
        int right = i - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (array[mid] >= temp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 循环结束后left就是应该插入的下标
        // 把下标从left到i-1的都往后移动一位
        for (int j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = temp;
    }
    display(array, size);
}

// 7.希尔排序
void shellSort(int* array, int size) {
    // 步长（让一个元素可以一次性地朝最终位置前进一大步）
    int gap = size / 2;
    while (gap > 0) {
        // 间隔gap的分在同一组(共gap组，gap下标[0,
        // gap-1]是这gap组每组的首个已排序元素)，进行普通的插入排序
        for (int i = gap; i < size; i++) {
            int temp = array[i];
            int j = i - gap;
            while (j >= 0 && array[j] > temp) {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = temp;
        }
        printf("gap:%d
", gap);
        display(array, size);
        gap = gap / 2;
    }
}

// 分治-治
void mergeSort_conquer(int* array, int left, int mid, int right, int* temp) {
    // [left, mid]和[mid+1, right]两个有序数组
    int i = left;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= right) {
        if (array[i] < array[j]) {
            temp[index++] = array[i++];
        } else {
            temp[index++] = array[j++];
        }
    }
    // 剩余元素直接放入temp
    while (i <= mid) {
        temp[index++] = array[i++];
    }
    while (j <= right) {
        temp[index++] = array[j++];
    }
    // 放回原数组
    index = 0;
    while (left <= right) {
        array[left++] = temp[index++];
    }
}

// 分治-分
void mergeSort_divide(int* array, int left, int right, int* temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    // 左边归并排序
    mergeSort_divide(array, left, mid, temp);
    // 右边归并排序
    mergeSort_divide(array, mid + 1, right, temp);
    // 合并两个有序序列
    mergeSort_conquer(array, left, mid, right, temp);
}

// 8.普通归并排序
void mergeSort(int* array, int size) {
    int* temp = (int*)malloc(sizeof(int) * size);
    mergeSort_divide(array, 0, size - 1, temp);
    display(array, size);
}

// TODO: 迭代版归并排序

// 9.计数排序(每个桶只存储单一键值) 0~10
void countingSort(int* array, int size) {
    int* frequency = (int*)calloc(11, sizeof(int));
    // frequency[i]表示统计i出现的次数
    for (int i = 0; i < size; i++) {
        frequency[array[i]]++;
    }
    display(frequency, 11);
    // frequency[i]表示小于等于i的个数
    for (int i = 1; i < 11; i++) {
        frequency[i] += frequency[i - 1];
    }
    display(frequency, 11);

    int* sorted = (int*)calloc(size, sizeof(int));
    // 倒着遍历原数组，把原数组放在新数组正确的位置上
    for (int i = size - 1; i >= 0; i--) {
        // 有frequency[array[i]]个小于等于array[i]个元素
        // 说明array[i]排在第frequency[array[i]]个位置，下标就是frequency[array[i]]-1
        // 放好后frequency[array[i]]要自减
        sorted[--frequency[array[i]]] = array[i];
        printf("frequency:	");
        display(frequency, 11);
        printf("sorted:		");
        display(sorted, size);
    }
}

typedef struct {
    int** bucket;
    int row;
    int column;
    int* index;
} Bucket;

// 10.桶排序(每个桶存储一定范围的数值)
// 数要相对均匀分布，桶的个数也要合理设计(需要知道输入数据的上界和下界和分布情况)，桶排序是一种用空间换取时间的排序
void bucketSort(int* array, int size) {
    Bucket* b = (Bucket*)malloc(sizeof(Bucket));
    b->row = 5;
    b->column = 3;
    b->index = (int*)calloc(b->row, sizeof(int));
    b->bucket = (int**)malloc(sizeof(int) * b->row);
    for (int i = 0; i < b->row; i++) {
        b->bucket[i] = (int*)malloc(sizeof(int) * b->column);
    }
    // 放入桶
    for (int i = 0; i < size; i++) {
        int index = array[i] / 10;
        b->bucket[index][b->index[index]++] = array[i];
    }
    size = 0;
    // 对每个桶进行排序（可用其他算法）
    for (int i = 0; i < b->row; i++) {
        qsort(b->bucket[i], b->column, sizeof(int), cmp);
        for (int j = 0; j < b->column; j++) {
            array[size++] = b->bucket[i][j];
        }
    }
    display(array, size);
}

// 11.基数排序(根据键值的每位数字来分配桶)
void radixSort(int* array, int size) {
    Bucket* b = (Bucket*)malloc(sizeof(Bucket));
    b->row = 10;
    b->column = 10;
    b->index = (int*)calloc(b->row, sizeof(int));
    // 临时存放按某一位排好序的序列
    b->bucket = (int**)malloc(sizeof(int) * b->row);
    for (int i = 0; i < b->row; i++) {
        b->bucket[i] = (int*)malloc(sizeof(int) * b->column);
    }

    // 最大的数的位数为3
    for (int i = 0; i < 3; i++) {
        // 按某一位重新排序
        for (int j = 0; j < size; j++) {
            int index = (array[j] / (int)pow(10, i)) % 10;
            b->bucket[index][b->index[index]++] = array[j];
        }
        // 放回原数组
        int returnSize = 0;
        for (int j = 0; j < b->row; j++) {
            for (int k = 0; k < b->index[j]; k++) {
                array[returnSize++] = b->bucket[j][k];
            }
            // 重置下标数组
            b->index[j] = 0;
        }
    }

    display(array, size);
}

void testSort() {
    // int a[] = {1, 0, 7, 2, 10, 5, 2, 8, 6, 0};
    // display(a, 10);
    // bubbleSort(a, 10);
    // quickSort(a, 10);
    // selectionSort(a, 10);
    // heapSort(a, 10);
    // insertionSort(a, 10);
    // binaryInsertionSort(a, 10);
    // shellSort(a, 10);
    // mergeSort(a, 10);
    // countingSort(a, 10);

    // int b[] = {1, 8, 7, 44, 42, 46, 38, 34, 33, 17, 15, 16, 27, 28, 24};
    // display(b, 15);
    // bucketSort(b, 15);

    int c[] = {53, 3, 542, 748, 14, 77, 214, 154, 63, 616};
    radixSort(c, 10);
}