C语言实现经典排序算法的示例代码

C语言排序算法 C语言排序 2022-11-13 14:11:14 341人浏览独家记忆

摘要

目录一、冒泡排序1.原理2.实现3.算法分析二、选择排序1.原理2.实现3.算法分析三、插入排序1.原理2.实现3.算法分析四、希尔排序1.原理2.实现3.算法分析总结一、冒泡排序

一、冒泡排序

1.原理

从数组的头开始不断比较相邻两个数的大小，不断将较大的数右移，一个循环后，最大数移至最后一位，无序数组规模减一。不断重复前面动作，知道数组完全有序。

2.实现

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubble_sort(int* arr, int len)
{
    bool issort = false;
    while (!issort)
    {
        issort = true;//如果有序则直接退出
        for (int i = 1; i < len; i++)
        {
            if (arr[i-1] > arr[i])//不断比较相邻两个数
            {
                swap(&arr[i - 1], &arr[i]);//将较大的数不断往右移
                issort = false;//如果进行了交换则无序
            }
        }
        len--;//无序规模减一
    }
}

3.算法分析

时间复杂度：最好情况，当数组完全有序，则只需要进行一轮比较，时间复杂度为o(n)；最坏情况为完全无序，每次比较后都要将该数移至数组末尾，时间复杂度为o(n ^2)；平均时间复杂度为o(n ^2)。

空间复杂度：冒泡排序为就地排序,空间复杂度为o(1)。

稳定排序：当数字相同时不会改变相对次序。

二、选择排序

1.原理

数组前面为无序，后面为有序。刚开始全是无序，从中选择一个最大值与最后一个无序数字进行交换，无序数组规模减一，有序数组规模加一。不断循环前面操作，直到数组变为有序数组。或者前面为有序数组，后面为无序数组，不断选择最小值与无序数组的第一个数交换，前面的有序数组加一，后面的无序数组减一。

2.实现

void selection_sort(int* arr, int len)
{
    int max_index;
    while (len)
    {
        max_index = 0;
        for (int i = 1; i < len; i++)
        {
            if (arr[max_index] < arr[i])
            {
                max_index = i;//获取最大值的索引
            }
        }
        swap(&arr[max_index], &arr[len - 1]);//将最大值与最后一个值交换
        len--;//无序规模减一
    }
}

3.算法分析

时间复杂度：所有的复杂度为每次选择最大值，不管数字的有序性，时间复杂度都为o(n)+o(n-1)+…+o(1)=o(n^2)。所以该算法平均复杂度、最好情况、最差情况都为o(n ^2)。

空间复杂度：就地排序，空间复杂度为o(1)。

不稳定性算法：排序后相同元素的顺序可能被打乱。例子：选择最大进行排序。3,1,2,2* 第一轮排序后 2*,1,2,3 2的相对顺序发生了改变。选择最小进行排序，2*,2,3,1 第一轮排序后1,2,3,2*. 2的相对顺序也被打乱。如果增加空间复杂度也能将选择排序变成稳定性排序。

三、插入排序

1.原理

数组前面为有序，后面为无序，将无序数组中的第一个数不断插入有序数组中（具体实现为不断比较相邻两数大小，前面一个数大于后一个数，则交换顺序，较小的数不断前移），有序规模增加一，无序规模减小一。或者，数组前面为无序，后面为有序，通过将无序数组的最后一位数字插入有序数组中（具体实现为将无序数组的最后一位与相邻的有序数组不断比较，将无序数组不断右移）。

2.实现

void insert_sort(int arr[], int len)
{
    for (int i = 1; i < len; i++)//i前面为有序
    {
        for (int j = i - 1; j >= 0; j--)//j为有序数的末尾
        {
            bool issort = true;//当数组有序时能够提前退出
            if (arr[j] > arr[j + 1])//将无序数组的第一个数不断与有序数组比较
            {
                swap(&arr[j], &arr[j + 1]);//将无序数字插入有序数组合适的位置
                issort = false;
            }
            if (issort) break;
        }
    }
}

3.算法分析

时间复杂度：插入排序和冒泡排序类似，最好情况完全有序则时间复杂度为o(n)，最坏情况为完全无序时间复杂度为o(n^2)，平均复杂度为o(n ^2)。

空间复杂度：就地排序不需要额外空间，空间复杂度为o(1)。

稳定性排序：和冒泡排序类似。

四、希尔排序

1.原理

每次选择一个增量进行分组，增量不断减小到一（为插入排序），数组不断变得有序，增量为一时变成完全有序。属于插入排序的改进，通过增量进行分组，对每一组进行插入排序，相比于插入排序的优势在于，shell排序能够大尺度的移动每一组的最小值，而插入排序得挨着进行比较，所以shell排序效率更高。

增量为6：

每一组只有两个数，分别比较两个数的大小，如64,57交换顺序变成57,64，所有的分组比较完后继续缩减增量。

增量为3：

每一组有四个数，总共三组，分别为23,12,53,79；57,9,64,87；24,16,71,97；以增量开始（12开始）遍历数组，遍历到12则在第一组中对12进行插入排序，交换23和12的顺序；遍历到9则在第二组对9进行插入排序。。。。遍历到64对一组中的9,57,64进行插入排序。最后每一组都变得有序。整体有序性变大。

增量为1：

对之前排序过的数组进行插入排序，通过前面的步骤数组有序性变大，最后进行插入排序的效率就更高。

2.实现

void shell_sort(int* arr, int len)
{
    int gap = 0; //分组的跨度
    int i = 0;
    int j = 0;
    for (gap = len / 2; gap >= 1; gap /= 2) //分组增量
    {
        for (i = gap; i < len; i++) {  //遍历每组
            for (j = i - gap; j >= 0; j -= gap)  //对组内进行插入排序
            {
                if (arr[j] > arr[j + gap])
                {
                    swap(&arr[j], &arr[j + gap]);
                }
            }
        }
    }
}