C语言:排序

devtools/2024/12/23 20:51:12/

1. 插入排序 (Insertion Sort)

插入排序是一种简单直观的排序算法,它的工作原理类似于整理扑克牌。它的基本思想是将数组分为已排序部分和未排序部分,每次从未排序部分取出一个元素,插入到已排序部分的合适位置。

步骤
  1. 从数组的第二个元素开始(假设第一个元素是已排序部分)。
  2. 将当前元素与已排序部分的元素从后向前比较,找到合适的位置插入。
  3. 重复上述过程,直到所有元素都被插入到合适的位置。
示例代码(C语言):
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
性能分析
  • 时间复杂度
    • 最好情况:O(n)(数组已经有序)。
    • 最坏情况:O(n^2)(数组逆序)。
    • 平均情况:O(n^2)
  • 空间复杂度O(1)(原地排序)。
  • 稳定性:稳定(不改变相同元素的相对顺序)。
适用场景
  • 适用于小规模数据或部分有序的数据。

2. 选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法,它的工作原理是每次从未排序部分选择最小(或最大)的元素,放到已排序部分的末尾。

步骤
  1. 将数组分为已排序部分和未排序部分。
  2. 从未排序部分中找到最小元素,与未排序部分的第一个元素交换位置。
  3. 重复上述过程,直到所有元素都被排序。
示例代码(C语言):
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换最小元素到已排序部分的末尾int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}
性能分析
  • 时间复杂度
    • 最好、最坏、平均情况:O(n^2)
  • 空间复杂度O(1)(原地排序)。
  • 稳定性:不稳定(交换操作可能改变相同元素的相对顺序)。
适用场景
  • 适用于小规模数据,尤其是内存受限的场景。

3. 快速排序 (Quick Sort)

快速排序是一种高效的排序算法,基于“分治法”的思想。它通过选择一个“基准元素”(pivot)将数组分为两部分:小于基准的部分和大于基准的部分,然后递归地对两部分进行排序。

步骤
  1. 选择一个基准元素(通常是数组的第一个或最后一个元素)。
  2. 将数组分为两部分:一部分小于基准,另一部分大于基准。
  3. 递归地对两部分进行快速排序。
示例代码(C语言):
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 partition(int arr[], int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准元素放到正确位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}
性能分析
  • 时间复杂度
    • 最好情况:O(n log n)(每次分区均匀)。
    • 最坏情况:O(n^2)(每次分区极不均匀,例如数组已经有序)。
    • 平均情况:O(n log n)
  • 空间复杂度O(log n)(递归栈的深度)。
  • 稳定性:不稳定(分区操作可能改变相同元素的相对顺序)。
适用场景
  • 适用于大规模数据的排序,尤其是随机数据的排序。

4. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法,它的工作原理是通过重复地遍历数组,依次比较相邻元素并交换顺序错误的元素。每一轮遍历都会将未排序部分的最大元素“冒泡”到末尾。

步骤
  1. 从数组的第一个元素开始,依次比较相邻元素。
  2. 如果前一个元素大于后一个元素,交换它们。
  3. 重复上述过程,直到没有需要交换的元素。
示例代码(C语言):
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
性能分析
  • 时间复杂度
    • 最好情况:O(n)(数组已经有序)。
    • 最坏情况:O(n^2)
    • 平均情况:O(n^2)
  • 空间复杂度O(1)(原地排序)。
  • 稳定性:稳定(不改变相同元素的相对顺序)。
适用场景
  • 适用于小规模数据,尤其是教学和理解排序算法的场景。

对比总结

算法时间复杂度空间复杂度稳定性特点
插入排序O(n^2)O(1)稳定适合小规模数据或部分有序数据
选择排序O(n^2)O(1)不稳定简单直观,适用于小规模数据
快速排序O(n log n)O(log n)不稳定高效,适用于大规模数据
冒泡排序O(n^2)O(1)稳定简单易于理解

http://www.ppmy.cn/devtools/144789.html

相关文章

《机器学习》第四章信息熵 信息增益率决策树怎么写

信息熵 信息熵是信息论中用来度量信息含量不确定性的一种指标。简单来说&#xff0c;熵越大&#xff0c;表示信息的不确定性越高&#xff0c;信息量越大&#xff1b;熵越小&#xff0c;表示信息的不确定性越低&#xff0c;信息量越小。 所以&#xff0c;信息熵是大好还是小好…

【Lua热更新】下篇

上篇链接&#xff1a;【Lua热更新】上篇 文章目录 三、xLua热更新&#x1f4d6;1.概述&#x1f4da;︎2.导入xLua框架&#x1f516;3. C#调用Lua3.1Lua解析器3.2Lua文件夹的重定向3.3Lua解析器管理器3.4全局变量获取3.5全局函数获取3.6映射到List和Dictionary3.7映射到类3.8映…

如何在谷歌浏览器中开启安全浏览

在数字化时代&#xff0c;网络安全变得愈发重要。作为全球最受欢迎的网络浏览器之一&#xff0c;谷歌浏览器提供了多种功能来保护用户的在线安全。本文将详细介绍如何在谷歌浏览器中开启安全浏览&#xff0c;并额外提供一些有用的页面滚动设置、地址栏快捷搜索和跟踪防护的相关…

中宇联与亚马逊云科技共同推出Well-Architected联合解决方案

数字化转型正如火如荼地进行&#xff0c;云计算已逐渐成为企业发展的核心动力。亚马逊云科技积极承担起数字经济时代基础设施提供者及企业成长的高质量伙伴角色&#xff0c;全心全意深化客户服务&#xff0c;赋能企业迈向成功之路。基于多年服务各行各业客户的经验总结&#xf…

JAVA没有搞头了吗?

前言 今年的Java程序员群体似乎承受着前所未有的焦虑。投递简历无人问津&#xff0c;难得的面试机会也难以把握&#xff0c;即便成功入职&#xff0c;也往往难以长久。于是&#xff0c;不少程序员感叹&#xff1a;互联网的寒冬似乎又一次卷土重来&#xff0c;环境如此恶劣&…

k8s迁移——岁月云实战笔记

新系统使用rockylinux9.5&#xff0c;旧系统虚拟机装的是centos7 1 目标服务器 1.1 禁止swap swapoff -a vi /etc/fstab #/dev/mapper/rl-swap none swap defaults 0 0 #执行&#xff0c;swap一行都是0 free -h 1.2 关闭防火墙 只是为了减…

CV-OCR经典论文解读|An Empirical Study of Scaling Law for OCR/OCR 缩放定律的实证研究

论文标题 An Empirical Study of Scaling Law for OCR OCR 缩放定律的实证研究 论文链接&#xff1a; An Empirical Study of Scaling Law for OCR论文下载 论文作者 Miao Rang, Zhenni Bi, Chuanjian Liu, Yunhe Wang, Kai Han 内容简介 本论文在光学字符识别&#xf…

CUDA基础编程:开启深度学习 GPU 加速之门

文章结尾有最新热度的文章,感兴趣的可以去看看。 本文是经过严格查阅相关权威文献和资料,形成的专业的可靠的内容。全文数据都有据可依,可回溯。特别申明:数据和资料已获得授权。本文内容,不涉及任何偏颇观点,用中立态度客观事实描述事情本身 文章有点长(字),期望您能坚…