admin管理员组文章数量:1531374
2024年6月26日发(作者：)
基于比较的排序算法有哪些
七种排序算法[1]分别是：
•
四种基本排序算法：冒泡排序，选择排序，插入排序，
希尔排序。
•
三种高级排序算法：归并排序，快速排序，堆排序。
这七种排序算法都是比较排序算法，这种算法的特点顾名思义
就是排序是依赖于元素间两两比较的结果[2]。
任何比较算法在最坏的情况下都要经过Ω(nlgn)次比
较。
1. 冒泡排序
顾名思义，冒泡排序的整个过程就像碳酸饮料 中的小气泡，
慢慢浮到最上面。只不过在冒泡排序中浮上去的是最大的数而
已。
简要思路： 遍历数组，每次比较相邻的两个元素 arr[i],
arr[i + 1]，如果 arr[i + 1] < arr[i] ，就把 arr[i + 1]
和 arr[i] 调换位置。
冒泡排序有这样的排序特性：
•
每次都只排好一个元素。
•
最坏情况时间复杂度为O(n^2)。
•
平均情况时间复杂度为O(n^2)。
•
需要额外空间O(1)。
•
所需时间与输入数组的初始状态无关。
算法示例
public static void bubbleSort(int[] arr) {
int n = ;
// 每一次循环，都把最大的元素冒泡到对应的位置
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
// 如果后一个比前一个小，那么就把大的放后
面
if (less(arr, j + 1, j)) exch(arr, j, j +
1);
}
}
}
2. 选择排序
其实选择排序，直观上来说和冒泡排序差不多，只不过么有了
相邻元素频繁交换的操作，但是却保留了冒泡排序频繁访问数
组的特点。
简要思路:对于每一个循环，我们在剩余的未排序数中找到最
小数对应的下标，遍历一次后再把对应的数放到合适的位置。
选择排序有这样的排序特性：
•
每次循环都只排好一个元素。
•
最坏情况时间复杂度为Theta (n^2)。
•
平均情况时间复杂度为Theta (n^2)。
•
需要额外空间为O(1)。
•
所需时间和输入数组的初始状态无关。
算法示例
public static void selectionSort(int[] arr) {
版权声明：本文标题：基于比较的排序算法有哪些 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1719415341a777293.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论