c语言十大排序算法（冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、计数排序、桶排序和基数排序）上机实操一_c语言十大算法

一.冒泡排序（Bubble Sort）

        冒泡排序的基本思想是：对相邻的元素进行两两比较，顺序相反则进行交换，这样每一次遍历都将最大的元素“浮”到数列的最后，下一次遍历则考虑剩下的元素。

   （1）代码

#include <stdio.h>  // 包含标准输入输出头文件，为了使用printf函数  
  
// 冒泡排序函数，参数是一个整型数组和数组长度  
void bubble_sort(int arr[], int len) {  
    int i, j, temp;  // 定义循环变量和临时变量  
  
    // 外层循环，控制排序轮数  
    for (i = 0; i < len - 1; i++) {  
        // 内层循环，控制每轮比较次数  
        for (j = 0; j < len - 1 - i; j++) {  
            // 如果前面的数比后面的数大，就交换这两个数  
            if (arr[j] > arr[j + 1]) {  
                temp = arr[j];  // 临时存储较大的数  
                arr[j] = arr[j + 1];  // 将较小的数放到前面  
                arr[j + 1] = temp;  // 将较大的数放到后面  
            }  
        }  
    }  
}  
  
// 主函数，程序入口  
int main() {  
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };  // 定义一个待排序的数组  
    int len = (int) sizeof(arr) / sizeof(*arr);  // 计算数组长度，通过计算总的字节数除以一个元素的字节数得到数组元素个数  
  
    // 对数组进行冒泡排序  
    bubble_sort(arr, len);  
  
    // 打印排序后的数组  
    int i;  
    for (i = 0; i < len; i++) {  
        printf("%d ", arr[i]);  // 打印每个元素和一个空格作为分隔符  
    }  
    return 0;  // 主函数返回0，表示程序正常结束  
}

  （2）结果

  （3）应用场景

      1.数据量较小：对于大规模的数据集，冒泡排序的效率较低，因为其时间复杂度为O(n^2)。因此，在处理大规模数据时，通常会选择更高效的排序算法，如归并排序或快速排序。而当数据量较小时，冒泡排序因其实现简单和稳定性好的优点而适用。

        2.对稳定性有要求：冒泡排序是稳定的排序算法，即相等的元素的顺序不会改变。这对于一些需要保持原始顺序的场景是很有用的，例如在处理带有信息的数字数组时。

        3.数据部分有序：如果数据已经部分有序，冒泡排序的性能会相对较好，因为它每次都将当前未排序的最大（或最小）元素“冒泡”到正确的位置。

   （4）冒泡排序的特性总结

        1.冒泡排序是一种非常容易理解的排序；

        2.时间复杂度：O(N^2)；

        3.空间复杂度：O(1)；

        4. 稳定性：稳定。

二.选择排序（Selection sort）

        一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

   （1）代码

 

#include <stdio.h>  
  
void selection_sort(int arr[], int n) {  
    int i, j, min_index;  
  
    // 遍历所有数组元素  
    for (i = 0; i < n - 1; i++) {  
        // 找到剩余部分的最小元素的索引  
        min_index = i;  
        for (j = i + 1; j < n; j++) {  
            if (arr[j] < arr[min_index]) {  
                min_index = j; // 更新最小元素索引  
            }  
        }  
        // 交换找到的最小元素和第i个元素  
        int temp = arr[min_index];  
        arr[min_index] = arr[i];  
        arr[i] = temp;  
    }  
}  
  
int main() {  
    int arr[] = {64, 25, 12, 22, 11};  
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度  
    selection_sort(arr, n); // 排序数组  
    printf("排序后的数组：\n");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]); // 打印排序后的数组元素  
    }  
    return 0;  
}

   （2）结果

   （3）应用场景 

        1.数据清洗：在数据预处理阶段，我们可能需要将数据进行排序以去除异常值或进行其他数据分析。选择排序可以用于这个目的。

        2.简单数据排序：对于一些简单的、不需要高效率排序的数据，如学生成绩单、商品价格等，可以选择使用选择排序进行排序。

        3.外部排序：当需要排序的数据太大而不能全部放入内存时，我们可以使用选择排序进行外部排序。每次从外存中读取一部分数据，进行排序，然后写入外存。

       4. 教学和演示：选择排序是一个易于理解和实现的算法，经常被用于教学和演示。例如，在介绍排序算法的基本概念和实现方法时，选择排序是一个很好的起点。

        5.初创公司或小型企业数据量较小，且对效率要求不高：在这些场景下，选择排序可能是一个不错的选择，因为它的实现简单且对于小规模数据效率可以接受。

   （4）总结

        1.找到数组中的最小元素并与数组的第一个元素交换位置。

        2.找到数组中从第二个元素开始的最小元素并与数组的第二个元素交换位置。

        3.以此类推，直到数组中最后一个元素。

三.插入排序（Insertion Sort）       

        一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

        （1）代码

#include <stdio.h>  
  
void insertionSort(int arr[], int n) {  
    int i, j, key;  
    for (i = 1; i < n; i++) {  
        key = arr[i]; // 保存当前需要插入的元素  
        j = i - 1; // 指向当前元素前面一个位置  
        // 将大于key的元素向后移动一个位置  
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j]; // 将元素向后移动  
            j = j - 1; // 移动指针  
        }  
        // 将key插入到正确的位置上  
        arr[j + 1] = key;  
    }  
}  
  
int main() {  
    int arr[] = {12, 11, 13, 5, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int i;  
    printf("原始数组：\n");  
    for (i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("\n");  
    insertionSort(arr, n); // 调用插入排序函数  
    printf("排序后的数组：\n");  
    for (i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("\n");  
    return 0;  
}

   （2）结果

   （3）应用场景

        1.数据库系统：在数据库系统中，经常需要将新的数据插入到已排序的表中。此时，插入排序可以非常高效地完成这个任务。

        2.数据结构：在数据结构中，例如栈和队列，经常需要插入新的元素并保持其排序。在这种情况下，插入排序可以很好地满足需求。

        3.文件系统：在文件系统中，可能需要按照字母顺序排列文件列表。插入排序可以用于此目的。

        4.内存管理：在某些情况下，可能需要将新元素插入到已排序的内存区域中。在这种情况下，插入排序是非常合适的选择。

    （4）总结

        1.实现简单，容易理解。

        2.对于小规模的数据排序，插入排序的效率可以接受。

        3.稳定，不会改变相同元素的相对顺序。

        4.对于大规模的数据排序，插入排序的效率较低。

        5.时间复杂度为O(n^2)，空间复杂度为O(1)。

 

四.希尔排序（Shell Sort）

        也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

        1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

        2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

     （1）代码

#include <stdio.h>  
  
void shellSort(int arr[], int n) {  
    int gap, i, j, temp;  
    for (gap = n / 2; gap > 0; gap /= 2) {  
        for (i = gap; i < n; i++) {  
            temp = arr[i];  
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  
                arr[j] = arr[j - gap];  
            }  
            arr[j] = temp;  
        }  
    }  
}  
  
int main() {  
    int arr[] = {12, 11, 13, 5, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int i;  
    printf("原始数组：\n");  
    for (i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("\n");  
    shellSort(arr, n); // 调用希尔排序函数  
    printf("排序后的数组：\n");  
    for (i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("\n");  
    return 0;  
}

     （2）结果

    （3）应用场景 

        1.内存管理：在内存中处理大量数据时，希尔排序可以作为一种有效的排序算法。由于其效率在大部分情况下优于插入排序，因此，当需要排序大量数据时，希尔排序是一个不错的选择。

        2.文件系统：在文件系统中，可能需要对大量的文件进行排序。在这种情况下，希尔排序可以高效地完成这个任务。

        3.大型数据集的初步排序：希尔排序可以作为对大型数据集进行初步排序的方法，后续可以使用更复杂的算法进行精细排序。

        4.需要快速排序的场合：在一些需要快速排序的场合，希尔排序可以作为一个备选方案。

     

    （4）总结

        虽然希尔排序在许多情况下效率优于插入排序，但其最坏情况时间复杂度仍然是O(n^2)，因此在对大规模数据集进行排序时，应谨慎选择使用希尔排序。

五.快速排序

       在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

    （1）代码

#include <stdio.h>  
  
// 交换两个元素的位置  
void swap(int* a, int* b) {  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  
  
// 找到基准元素的正确位置  
int partition(int arr[], int low, int high) {  
    int pivot = arr[high]; // 选择最后一个元素作为基准  
    int i = low - 1; // i指向已排序部分的最后一个元素  
    for (int j = low; j <= high - 1; j++) {  
        if (arr[j] < pivot) { // 如果当前元素小于基准，则将它放入i之后  
            i++;  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]); // 将基准元素放入正确的位置  
    return i + 1;  
}  
  
// 递归地进行快速排序  
void quickSort(int arr[], int low, int high) {  
    if (low < high) {  
        int pi = partition(arr, low, high); // 找到基准元素的正确位置  
        quickSort(arr, low, pi - 1); // 对基准左边部分进行排序  
        quickSort(arr, pi + 1, high); // 对基准右边部分进行排序  
    }  
}  
  
int main() {  
    int arr[] = {10, 7, 8, 9, 1, 5}; // 待排序数组  
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度  
    quickSort(arr, 0, n - 1); // 调用快速排序函数  
    printf("排序后的数组：\n");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("\n");  
    return 0;  
}

   （2）结果

    （3）应用场景

        1.大规模数据排序：对于大规模的数据排序，快速排序的性能通常优于其他排序算法。无论是在科学研究、商业应用还是其他需要处理大量数据的领域，快速排序都是非常有效的。

        2.需要快速处理数据的场景：在一些需要快速处理数据的场景中，快速排序的快速性能使得它成为首选。例如，在实时系统、大数据处理、高性能计算等领域，快速排序被广泛使用。

        3.复杂数据集：对于复杂数据集，例如多维数组、稀疏矩阵等，快速排序能够提供更好的性能。这是因为它能够有效地处理数据集中的复杂结构，使得排序过程更加高效。

        4.需要稳定排序的场景：虽然快速排序不是稳定排序算法，但是在一些需要稳定排序的场景中，通过一些改进算法可以实现稳定排序的效果。例如，可以使用稳定的合并排序与快速排序结合使用，以保证数据的稳定性。

    （4）总结

        1.选择一个基准元素。

        2.把数组分成两部分：一部分的元素都比基准元素小，另一部分的元素都比基准元素大。

        3.对这两部分元素分别进行快速排序。

六.下一篇上机实操二

        介绍剩下的五种排序算法。