C语言十大排序算法总结

插入排序

基本思想是每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。

1.直接插入排序

代码实现

void insertSort(int *arr, int arrSize) {
    // 依次将arr[1, ..., arrSize - 1]插入到前面已经排序好的位置
    for (int i = 1; i < arrSize; i++) {
        if (arr[i] < arr[i - 1]) { // 若arr[i]小于前驱，需要将其插入前面已经排序好的子序列
            int temp = arr[i];
            // 从后往前查找待插入位置, 终止条件是，arr[j] <= temp;
            int  j = i - 1;
            while (arr[j] > temp) {
                arr[j + 1] = arr[j]; // 后移
                j--;
            }
            // arr[j] <= temp; j + 1是插入位置
            arr[j + 1] = temp;
        }
    }
}   

复杂度分析

• 时间复杂度：\(O(n^2)\)；
  • 向有序子表中逐个插入元素的操作进行了 \(n - 1\) 趟，每趟操作都分为比较关键字和移动元素。
  • 最好的情况是元素有序，此时每插入一个元素，都只需比较一次而不用移动元素，时间复杂度为 $ O(n) $;
  • 最坏的情况是元素逆序，总的比较次数为 $(1 + 2 + 3 + ··· + n - 1) $ ，总的移动次数为 \((1 + 2 + ··· + n - 1 + 2)\);
• 空间复杂度：$ O(1)$；
  • 仅使用了常数个辅助单元
• 算法稳定性：稳定
  • 由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况。

2.折半插入排序

代码实现

// 与直接插入唯一不同在于查找插入位置时是使用折半查找
void insertSort(int *arr, int arrSize) {
    // 依次将arr[1, ..., arrSize - 1]插入到前面已经排序好的位置
    for (int i = 1; i < arrSize; i++) {
        int temp = arr[i]; // 将当前元素保存
        // 在前面子序列中折半查找插入位置
        int low = 0, high = i - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (temp < arr[mid]) //查左半子表
                high = mid - 1;
            else // 查右半子表
                low = mid + 1;
        }
        // low是插入位置, 或者high + 1;
        for (int j = i - 1; j >= low; --j) {
            arr[j + 1] = arr[j];
        }
        arr[low] = temp;
    }
}

复杂度分析

• 时间复杂度：\(O(n^2)\)；
  • 折半插入排序仅减少了比较元素的次数，比较次数约为 \((nlog_2 n)\)
  • 比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 \(n\);
• 空间复杂度：$ O(1)$；
  • 仅使用了常数个辅助单元
• 算法稳定性：稳定

3.希尔排序

先将待排序表分割成若干形如 $ L[i, i + d, i + 2d, ··· , i + kd]$ 的 “特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

代码实现

void shellSort(int *arr, int arrSize) {
    // d1 = n / 2, d(i + 1) = d1 / 2;
    for (int dk = arrSize / 2; dk >= 1; dk /= 2) { // 可以将dk理解为步长，dk = 1时，退化为直接插入排序
        for (int i = dk; i < arrSize; i++) {
            if (arr[i] < arr[i - dk]) { // 需要将 arr[i] 插入有序增量子表中
                int temp = arr[i];
                int j = i - dk;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + dk] = arr[j];
                    j -= dk;
                }
                // 退出循环后，arr[j] <= temp, 显然 j + dk 是插入位置
                arr[j + dk] = temp;
            }
        }
    }
}

复杂度分析

• 时间复杂度：
  • 希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难
  • 当 \(n\) 在某个特定范围内，希尔排序的时间复杂度约为 \(O(n^{1.3})\);
  • 最坏情况下希尔排序的时间复杂度为 \(O(n^2)\);
• 空间复杂度：\(O(1)\);
  • 仅使用了常数个辅助单元
• 算法稳定性：不稳定
  • 当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。

交换排序

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

4.冒泡排序

代码实现

// 基本思想：从前往后两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完
// 上述是第一趟冒泡，结果是将最大的元素交换到最后一个
void bubbleSort(int *arr, int arrSize) {
    for (int i = 0; i < arrSize - 1; i++) { // 无须和自己比较，所以趟数为 arrSize - 1;
        int swapflag = 0;// 表示本趟冒泡是否发生交换的标志
        for (int j = 0; j < arrSize - 1 - i; j++) { // arrSize - 1 - i 是因为每一趟就会少一个
            if (arr[j] > arr[j + 1]) {
            /* 交换 */
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapflag = 1;
            }
        }
        // 本趟遍历后没有发生交换，说明表已经有序
        if (swapflag == 0)
            return ;
    }
}

// 从后往前
void bubbleSort2(int *arr, int arrSize) {
    for (int i = 0; i < arrSize - 1; i++) {
        int swapflag = 0;
        // j 从后往前，第i趟说明第i个元素确定好顺序了
        for (int j = arrSize - 1; j > i; --j) {
            if (arr[j] < arr[j - 1]) {
                /* 交换 */
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                swapflag = 1;
            }
        }
        if (swapflag == 0)
            return ;
    }
}

复杂度分析

• 时间复杂度： \(O(n^2)\);
  • 最好情况下时间复杂度为 \(O(n)\);
    • 初始序列有序，第一趟冒泡排序后直接跳出循环。此时比较次数为 \(n - 1\)，移动次数为 \(0\);
  • 最坏情况下时间复杂度为 \(O(n^2)\) ;
    • 初始序列逆序，要进行 \((n - 1)\) 趟冒泡。第 \(i\) 趟要进行 \(n - i\) 次比较，移动次数为 \(3(n - i)\) ;
• 空间复杂度： \(O(1)\);
  • 仅使用了常数个辅助单元
• 算法稳定性：稳定

5.快速排序

代码实现

int partition(int *arr, int low, int high) {
    // 假设枢轴元素为第一个
    int pivot = arr[low];
    // 高低指针向中心靠拢
    while (low < high) {
        // 高指针寻找第一个比枢轴元素小的
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];   // 将其移动至arr[low]
        // 低指针寻找第一个比枢轴元素大的
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];   // 将其移动至arr[high]
    }
    arr[low] = pivot;
    // 返回的是确定位置的元素下标  
    return low;
}
void quickSort(int *arr, int low, int high) {
    // 递归终止条件 
    if (low >= high) 
        return ;
    // 确定位置的元素下标 
    int mid = partition(arr, low, high);
    // 左边递归排序 
    quickSort(arr, low, mid - 1);
    // 右边递归排序 
    quickSort(arr, mid + 1, high);
}

复杂度分析

• 时间复杂度： \(O(log_2n)\);
  • 快速排序的运行时间与划分是否对称有关。
  • 最坏情况：\(O(n^2)\);
    • 两个区域分别包括 \(n - 1\) 和 \(0\) 个元素时，即序列开始时便逆序
  • 最好情况：\(O(nlog_2n)\);
    • 尽可能地划分两个左右序列
• 空间复杂度：\(O(nlog_2n)\);
  • 由于快排是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大深度一致
  • 最好的情况：\(O(log_2n)\);
  • 最坏的情况：\(O(n)\);
    • 因为要进行 \(n - 1\) 次递归调用
• 算法稳定性：不稳定
  • 在划分算法中，若右端区间有两个关键字相同，且均小于枢轴元素，则在交换到左端区间后，它们的相对位置会发生变化

选择排序

选择排序的基本思想是：每一趟（如第 \(i\) 趟）在后面 \(n - i + 1(i = 1, 2, ··· ,n - 1)\) 个待排序元素中选取关键字最小的元素，作为有序子序列的第 \(i\) 个元素，直到第 \(n - 1\) 趟排序做完，待排序元素只剩下1个，就不再选了。

6.简单选择排序

代码实现

// 算法思想：假设排序表为L[1,...,n]，第i趟排序即从L[i,..,n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置
// 这样经过 n - 1趟排序就可以使得整个排序表有序
void selectSort(int *arr, int arrSize) {
    for (int i = 0; i < arrSize; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arrSize; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        // minIndex 为最小元素下标
        // 交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

复杂度分析

• 时间复杂度： \(O(n^2)\);
  • 主要分为比较次数和移动次数
  • 最坏情况下，比较次数为\((1 + 2 + ··· + n - 1)\), 移动次数为\(3(n - 1)\);
  • 最好情况下，比较次数为\((1 + 2 + ··· + n - 1)\), 移动次数为 \(0\);
• 空间复杂度： \(O(1)\);
  • 仅使用常数个辅助单元
• 算法稳定性：不稳定
  • {2，2， 1} 经过一趟排序后变为 {1，2， 2};

7.堆排序

代码实现

/* 首先将元素建成大根堆，此时堆顶元素就是最大值。
 * 输出堆顶元素后，通常将堆底元素送入堆顶，此时根节点不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质。
 * 再输出堆顶元素，如此重复，直至堆中仅剩下一个元素为止
 */

// 调整以k为根节点的堆
void adjustDown(int *arr, int arrSize, int k) {
    // 先将根节点的值保存一下 
    int tmp = arr[k];
    // 2 * k + 1: k节点的左节点
    // 2 * k + 2: k节点的右节点
    for (int i = 2 * k + 1; i < arrSize; i = 2 * k + 1) {
        // i + 1 < arrSize 确保右节点存在
        if (i + 1 < arrSize && arr[i] < arr[i + 1]) // 左子节点 < 右子节点
            i++;
        // i始终指向值最大的子节点
        if (tmp >= arr[i]) // k节点值 >= 子节点，满足大根堆性质
            break;
        else { 
            arr[k] = arr[i];
            k = i; 
        }
    }
    arr[k] = tmp;
}   
/* 建立小跟堆 */
void buildMaxHeap(int *arr, int arrSize) {
    // 最后一个父节点 
    // arrSize为元素个数, -1 是因为下标从0开始
    int i = arrSize / 2 - 1;
    for (; i >= 0; i--) {
        adjustDown(arr, arrSize, i); // 调整以i为父节点的堆
    }   
}
// 堆排序
void heapsort(int *arr, int arrSize) {
    // 1. 建立大根堆
    buildMaxHeap(arr, arrSize);
    // 2. 从最后一个元素开始，与堆顶元素进行交换，直到只剩下一个元素
    for (int i = arrSize - 1; i > 0; i--) {
        int temp = arr[0]; 
        arr[0] = arr[i];
        arr[i] = temp;
        // 交换完成，调整大根堆，此时堆的长度为i
        adjustDown(arr, i, 0);
    }
}   

复杂度分析

• 时间复杂度： \(O(nlog_2n)\);
  • 分为建立大根堆和调整堆
    • 在建n个元素的堆时，时间复杂度为 \(O(n)\);
    • 需要进行 \(n - 1\) 次堆调整，每次调整的时间复杂度为 \(O(h)\)
• 空间复杂度：\(O(1)\);
  • 仅使用了常数个辅助单元
• 算法稳定性：不稳定

8.归并排序

代码实现

/*
 * 假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，等到 n/2(向上取整) 个长度为2或1的有序表；
 * 继续两两归并······
 * 如此重复，直至合并成一个长度为n的有序表为止
 */
// 将前后相邻的两个有序表归并为一个有序表
// arr[low, mid], arr[mid + 1, high];
void merge(int *arr, int low, int mid, int high) {
    // 开辟一个临时数组，tmp[low, high]
    int *tmp = (int *)malloc(sizeof(int) * (high - low + 1));
    int i = low, j = mid + 1;
    int k = 0; // tmp[]的下标
    // 从两个有序表第一个元素开始往后遍历，将小元素放入tmp中
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    // 前面有序表未放完
    while (i <= mid)
        tmp[k++] = arr[i++];
    // 后面有序表未放完
    while (j <= high)
        tmp[k++] = arr[j++];
    // 将tmp元素赋值到arr中
    for (int i = 0; i < k; i++)
        arr[low + i] = tmp[i];
}
void mergesort(int *arr, int left, int right) {
    if (left >= right)
        return ;
    int mid = left + (right - left) / 2;
    mergesort(arr, left, mid);
    mergesort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

复杂度分析

• 时间复杂度： \(O(nlog_2n)\)
  • 每趟归并的时间复杂度为 \(O(n)\)，需要进行 \(log_2n(向上取整)\) 趟归并
• 空间复杂度： \(O(n)\);
  • merge()操作中，辅助空间刚好为\(n\)个单元
• 算法稳定性： 稳定

9. 计数排序

主要思想：开辟一个长为 maxVal - minVal + 1的计数数组，然后遍历一遍原数组，将元素值-minVal作为计数数组的索引，值则自增。

此时计数数组中不为0的元素值为原数组中元素值等于索引的个数。遍历计数数组，遇到不为0的元素，反写回原数组。

代码实现

// 不稳定法
void countSort(int *arr, int arrSize) {
    // 初始化最大值和最小值为首元素
    int maxVal = arr[0], minVal = arr[0];
    for (int i = 1; i < arrSize; i++) {
        if (arr[i] > maxVal)
            maxVal = arr[i];
        if (arr[i] < minVal)
            minVal = arr[i];
    }
    // 此时 maxVal, minVal分别为最大值和最小值
    // 创建一个计数数组, 长度为maxVal - minVal + 1;
    int countArrSize = maxVal - minVal + 1;
    int *countArr = (int *)malloc(sizeof(int) * (countArrSize));
    // 将计数数组初始化为0
    for (int i = 0; i < countArrSize; i++)
        countArr[i] = 0;
    // 将原数组中的值减去最小值，将其作为索引，存入计数数组
    for (int i = 0; i < arrSize; i++) {
        countArr[arr[i] - minVal]++;
    }
    // 遍历计数数组，根据元素个数还原
    int j = 0;
    for (int i = 0; i < countArrSize; i++) {
        while (countArr[i]) { // count数组中还有计数
            arr[j++] = i + minVal; // 要加上最小值，还原    
            countArr[i]--;
        }
    }
    free(countArr);
}
// 稳定法
void countSort2(int *arr, int arrSize) {
    // 获取排序数组的最大元素
    int maxVal = arr[0];
    // 获取排序数组的最小元素
    int minVal = arr[0];
    for (int i = 1; i < arrSize; i++) {
        if (arr[i] > maxVal)
            maxVal = arr[i];
        if (arr[i] < minVal)
            minVal = arr[i];
    }
    // 计数数组的长度
    int countArrSize = maxVal - minVal + 1;
    // 创建一个计数数组
    int *countArr = (int *)malloc(sizeof(int) * countArrSize);
    // 初始化为0
    memset(countArr, 0, sizeof(int) * countArrSize);
    // 计数, 统计每个元素出现的次数
    for (int i = 0; i < arrSize; i++) {
        countArr[arr[i] - minVal]++;
    }
    // 累计计数，计算每个元素在排序后数组中的位置
    for (int i = 1; i < countArrSize; i++) {
        countArr[i] += countArr[i - 1];
    }
    // 排序：根据累计计数数组将元素放置到正确的位置
    int *result = (int *)malloc(sizeof(int) * arrSize);
    for (int i = arrSize - 1; i >= 0; i--) {
        result[countArr[arr[i] - minVal] - 1] = arr[i];
        countArr[arr[i] - minVal]--;
    }
    // 复制到原空间
    for (int i = 0; i < arrSize; i++) {
        arr[i] = result[i];
    }
}

复杂度分析

• 时间复杂度： $O(n + k) \(，\)k$ 为整数范围
  • 最后的两层循环，最外层执行的次数为 \(k\), 最里层最终次数为\(n\), 因此总的次数是 \(n + k\);
• 空间复杂度：
  • \(O(k)\)，\(k\)​ 为整数范围（不稳定算法）
  • \(O(k + n)\), （稳定算法）
• 算法稳定性：稳定 / 不稳定

10. 桶排序

主要思想就是：将要排序的数据分到几个有序的桶里，每个桶里的元素再单独进行排序。桶内排序完之后，再把每个桶里面的数据按照顺序依次取出，组成的序列就是排好序的序列。

要先确定好桶的个数和映射函数

代码实现

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


// 定义桶的数据结构
struct Bucket {
    int count;      // 桶中元素个数
    int* values;    // 桶中数据
};
// 桶排序函数
void bucketSort(int array[], int size) {
    int bucketCount = 10;
    // 创建桶数组
    struct Bucket buckets[bucketCount];   
    // 初始化桶
    for (int i = 0; i < bucketCount; i++) {
        buckets[i].count = 0;
        buckets[i].values = (int*)malloc(sizeof(int) * size);
    }
    // 将数据分散到桶中
    for (int i = 0; i < size; i++) {
        int bucketIndex = array[i] / bucketCount;
        buckets[bucketIndex].values[buckets[bucketIndex].count++] = array[i];
    }
     // 对每个桶中的数据进行排序
     for (int i = 0; i < bucketCount; i++) {
         if (buckets[i].count > 0) {
             // 使用简单的冒泡排序，实际中可以使用其他更高效的排序算法
             for (int j = 0; j < buckets[i].count - 1; j++) {
                 for (int k = 0; k < buckets[i].count - j - 1; k++) {
                     if (buckets[i].values[k] > buckets[i].values[k + 1]) {
                         // 交换桶中的元素
                         int temp = buckets[i].values[k];
                         buckets[i].values[k] = buckets[i].values[k + 1];
                         buckets[i].values[k + 1] = temp;
                     }
                 }
             }
         }
     }
 
     // 合并所有桶的结果
     int index = 0;
     for (int i = 0; i < bucketCount; i++) {
         for (int j = 0; j < buckets[i].count; j++) {
             array[index++] = buckets[i].values[j];
         }
         // 释放桶内存
         free(buckets[i].values);
     }
 }

复杂度分析

• 时间复杂度： \(O(n)\)​
  • 在均匀分布情况下，桶排序的平均时间复杂度接近线性
• 空间复杂度：较高，具体取决于桶的数量和分配的空间
• 算法稳定性：取决于桶内排序的稳定性
• 桶排序仅适用于元素数据分布相对均匀且元素范围较小。

11.基数排序

主要思想是：第一趟排序的基数为1，即根据个位数放入相应的桶中，然后再将按桶号将桶中元素分别放回原数组，完成一趟排序，此时个位数已经有序

第二趟排序的基数为10，即根据10位数放入相应的桶中，重复以上过程。

趟数为最大元素的数字个数。

代码实现

int radixSort(int *arr, int arrSize) {
    // 定义十个桶 0...9
    int bucket[10] = {0};
    // result 是答案数组
    int *result = (int *)malloc(sizeof(int) * arrSize);
    /* 1.求数组中最大元素 */
    int maxVal = arr[0];
    for (int i = 1; i < arrSize; i++) {
        if (arr[i] > maxVal)
            maxVal = arr[i];
    }
    /* 2.求最大元素数字个数 */
    int maxValCount = 0;
    while (maxVal) {
        maxValCount += 1;
        maxVal /= 10;
    }
     int base = 1;
     for (int k = 0; k < maxValCount; k++) {
         // 求每一个元素的base上数字，放入对应的桶里面
         for (int i = 0; i < arrSize; i++) {
             bucket[(arr[i] / base) % 10]++;
         }
         // 计算累加和
         for (int i = 1; i < 10; i++) {
             bucket[i] += bucket[i - 1];
         }
         // 根据桶数组，将元素放入原先数组中
         for (int i = arrSize - 1; i >= 0; i--) {
             result[bucket[(arr[i] / base) % 10] - 1] = arr[i];
             bucket[(arr[i] / base) % 10]--;
         }
         // 将result数组元素复制到arr中，循环
         for (int i = 0; i < arrSize; i++) {
             arr[i] = result[i];
         }
         // 清空桶元素
         for (int i = 0; i < 10; i++) {
             bucket[i] = 0;
         }
         // base乘以10，进入下一趟排序
         base *= 10;
     }
 }

复杂度分析

• 时间复杂度： \(O(d(n + r)\)
  • \(d\) —— 最大数字的位数，即循环的次数
  • \(r\) —— 数字的基数，表明桶的个数
• 空间复杂度：\(O(n + r)\)
• 算法稳定性：稳定