【C语言】排序方法

前言：

在本章节为大家提供一些C语言排序的方法，供大家使用。

本文将详细介绍三种基础排序方法：冒泡排序、选择排序和插入排序

一·冒泡排序 

算法原理：

冒泡排序是最简单的排序算法之一，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序的核心思想是通过相邻元素之间的比较和交换，将最大（或最小）的元素逐步 "冒泡" 到数组的末尾。

具体步骤如下：

1. 比较相邻的元素。如果第一个比第二个大，就把它们交换过来。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 外层循环（for i）：控制排序的轮数。对于长度为n的数组，需要进行n-1轮，因为每轮会确定一个元素的最终位置。
6. 内层循环（for j）：负责每一轮中的元素比较和交换。具体作用如下：
   • 比较相邻元素：通过j的递增，依次比较arr[j]和arr[j+1]。
   • 交换条件：如果前一个元素大于后一个元素（即arr[j] > arr[j+1]），则交换它们。
   • 减少比较次数：每完成一轮，最大的元素已在正确位置，因此下一轮可以减少一次比较（通过n-1-i实现）。

完整代码

#include <stdio.h>

// 冒泡排序函数

void bubbleSort(int arr[], int n) 
{
    int i, j, temp;
    for (i = 0; i < n - 1; i++) 
    {
        // 最后i个元素已经就位
        for (j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1]) 
            {
                // 交换元素
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

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

// 主函数
int main()
{
    int arr[] = {11,33,3,0,11111,77,44 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组: \n");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

 如果想要从小到大的排序。仅仅把比较部分的小于改成大于即可。

二·选择排序

算法原理

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

具体步骤如下：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

完整代码

#include <stdio.h>

void selectionSort(int arr[], int n) 
{
    for (int i = 0; i < n - 1; i++) 
    {
        int min = i;
        for (int j = i + 1; j < n; j++) 
        {
            if (arr[j] < arr[min])
                min = j;
        }

        // 交换找到的最小元素和第一个元素
        if (min != i) 
        {
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

int main()
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("排序后的数组: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

三·插入排序 

算法原理

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

 完整代码

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将比 key 大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    insertionSort(arr, n);
    
    printf("排序后的数组: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    return 0;
}