2. 排序算法基础
2022/1/7 12:03:49
本文主要是介绍2. 排序算法基础,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 引言
我们通常所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。排序算法大体可分为两种:
比较排序:主要有冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等,时间复杂度为O(nlogn) ~ O(n^2)
非比较排序:主要有计数排序,基数排序,桶排序等,时间复杂度可以为O(n)
2. 比较排序
下表给出了常见比较排序算法的性能:
1. 排序算法的稳定性
排序算法稳定性的简单形式化定义为:如果Ai = Aj,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序
不变。对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法进行分析从而得到稳定的特性。需要注意的是,排序算法是否为稳
定的是由具体算法决定的,不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。例如,对于冒泡排序,原本是稳定的排序算法,
如果将记录交换的条件改成A[i] >= A[i + 1],则两个相等的记录就会交换位置,从而变成不稳定的排序算法。
排序算法稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,前一个键排序的结果可以为后一个键排序所用。基数排序就是这样,先按低位
排序,逐次按高位排序,低位排序后元素的顺序在高位也相同时是不会改变的。
2. 冒泡排序
冒泡排序是最基础的排序算法,它重复地访问要排序的元素,依次比较相邻两个元素大小,如果他们的顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。这个算
法的名字的由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
实现步骤:
1. 比较相邻的元素,如果前一个比后一个大,则调换它们的位置;
2. 对每一对相邻元素做同样的工作,从开始第一对到结尾最后一对,每次最大的元素会依次排列到最后;
3. 针对所有的元素重复以上的步骤,除了已经排好序的元素,直到没有任何一对元素需要比较。
代码实现:
#include <stdio.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void BubbleSort(int A[], int n) { for (int j = 0; j < n - 1; j++) // 每次最大元素就像气泡一样"浮"到数组的最后 { for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移 { if (A[i] > A[i + 1]) // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法 { Swap(A, i, i + 1); } } } } int main() { int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大冒泡排序 int n = sizeof(A) / sizeof(int); BubbleSort(A, n); printf("冒泡排序结果:"); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
这篇关于2. 排序算法基础的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程
- 2024-12-24Java就业项目资料:新手入门必备教程