亲宝软件园·资讯

展开

C语言排序算法

随便写写。 人气:0

一、冒泡排序

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]);
                }
            }
        }
    }
}

3.算法分析

时间复杂度:最好情况为完全有序o(n),最差情况为完全无序o(n^2),平均复杂度为o(n ^1.3)。

空间复杂度:该算法为就地排序空间复杂度为o(1)。

稳定性:shell排序在分组中可能将相同数字划分成不同的分组,会改变相对顺序,属于不稳定性排序算法。

总结

冒泡排序、选择排序、插入排序、希尔排序的实现都是基于线性表进行实现的(数组或者链表),实现逻辑都是通过比较数字的大小。算法的时间复杂度都比较大,但是属于就地排序,不需要额外空间。几种算法相比之下希尔排序更具有优势。

加载全部内容

相关教程
猜你喜欢
用户评论