C语言经典算法之直接排序算法

这篇具有很好参考价值的文章主要介绍了C语言经典算法之直接排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

一、代码实现

二、时空复杂度

时间复杂度:

空间复杂度:


前言

建议:1.学习算法最重要的是理解算法的每一步,而不是记住算法。

           2.建议读者学习算法的时候,自己手动一步一步地运行算法。

tips:希尔排序算法就是通过该算法衍生出来的,通过理解本算法可以为理解希尔排序打下基础。同时,本算法的逻辑简单。

直接排序算法,也称为选择排序(Selection Sort),是一种简单直观的排序算法。其基本思想是每一趟从待排序的数据元素中选择最小(或最大)的一个元素,将它与序列的第一个元素进行交换,然后再从剩余的元素中选择最小(或最大)的元素,与序列的第二个元素进行交换,如此循环,直到整个序列有序。总结就是,将无序元素与其前面的元素比较大小,以此来确定其位置,从而将其加入前面的有序的部分。

一、代码实现

#include <stdio.h>

// 交换数组中两个元素的值
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// 直接排序函数
void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // 选择排序的主循环
    for (i = 0; i < n-1; i++) {
        // 寻找在未排序部分中的最小元素的索引
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // 将找到的最小元素与当前位置元素交换
        swap(&arr[min_idx], &arr[i]);
    }
}

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

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

    printf("原始数组: \n");
    printArray(arr, n);

    // 调用直接排序算法
    selectionSort(arr, n);

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

    return 0;
}

在这段代码中,swap 函数用于交换数组中两个元素的值,而 selectionSort 函数实现了直接排序算法。主要的思路是在未排序的部分中找到最小元素的索引,然后与当前位置的元素进行交换,通过不断进行这样的操作,实现整个数组的排序。

二、时空复杂度

时间复杂度:

直接排序算法的时间复杂度主要由两层循环决定。

外层循环:外层循环的次数是 n-1,其中 n是数组的长度。这是因为在进行 n-1次选择后,剩下的最后一个元素已经有序了。

内层循环:内层循环用于在未排序的部分中寻找最小元素的索引。在最坏情况下,每次选择都需要遍历剩余未排序的元素。内层循环的次数是n,n-1,n-2,…,1。其平均时间复杂度为。

综合考虑外层和内层循环(只要考虑n的次数大的复杂度),直接排序的时间复杂度为

平均/最好/最差时间复杂度均为

空间复杂度:

直接排序是一种原地排序算法,它只需要常数级别的额外空间来存储少量的辅助变量,如循环中的索引和临时变量。因此,直接排序的空间复杂度为 O(1),即常数级别的额外空间。文章来源地址https://www.toymoban.com/news/detail-798301.html

到了这里,关于C语言经典算法之直接排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包