📚 八大排序算法合集——两万字,8张动图,450行代码。大厂面试必备。
🌲 配套源码地址:《八大排序》源码,提取码:5ehp
哈喽,大家好,我是一条~
今天给大家带来《糊涂算法》专栏的第二期内容——排序算法的讲解。相信无论是初学者学习还是大厂面试,都少不了排序算法这关,即使没学过算法,对冒泡排序也不会陌生。
今天,一条就带大家彻底跨过**「排序算法」这道坎,保姆级教程建议收藏**。⭐️
古语云:“兵马未动,粮草先行”。想跟着一条一块把「排序算法」弄明白的,建议先准备好以下代码模板。
📢 观看本教程需知道基本循环语法、两数交换、双指针等前置知识。
📚 建议先看完代码和逐步分析后再尝试自己写。
Java
工程,本文全篇也基于Java语言实现代码。MainTest
测试类中编写测试模板。/** * 测试类 * Author:一条 * Date:2021/09/23 */
public class MainTest {
public static void main(String[] args) {
//待排序序列
int[] array={6,10,4,5,2,8};
//调用不同排序算法
// BubbleSort.sort(array);
// 创建有100000个随机数据的数组
int[] costArray=new int[100000];
for (int i = 0; i < 100000; i++) {
// 生成一个[0,100000) 的一个数
costArray[i] = (int) (Math.random() * 100000);
}
Date start = new Date();
//过长,先注释掉逐步打印
//BubbleSort.sort(costArray);
Date end = new Date();
System.out.println("耗时:"+(end.getTime()-start.getTime())/1000+"s");
}
}
该段代码内容主要有两个功能:
10w
个数排好序需要的时间。更加具象的理解时间复杂度的不同从这里开始都是非比较排序。
假如输入一个数x
,如果我们可以找到比该数小的数有几个,那么就可以直接将x
放入到对应的输出数组的位置。
比如测试序列中的x=5
,,比5
小的有2
个,那么毫无疑问5
就该排在第三位。
public class CountSort {
public static void sort(int[] array) {
System.out.println("计数排序开始--------");
//计算最大值和最小值,用于确定count[]的长度
int max = array[0], min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
//count[]用于存储每个元素出现的次数
int[] count = new int[max - min + 1];
//统计出现的频次
for (int i : array) {
count[i - min] += 1;//数的位置 上+1
}
//创建最终返回的数组,和原始数组长度相等,但是排序完成的
int[] result = new int[array.length];
int index = 0;//记录最终数组的下标
//先循环每一个元素 在计数排序器的下标中
for (int i = 0; i < count.length; i++) {
//遍历循环出现的次数
for (int j = 0; j < count[i]; j++) {//count[i]:这个数出现的频率
result[index++] = i + min;//以为原来减少了min现在加上min,值就变成了原来的值
}
System.out.println(Arrays.toString(result));
}
}
}
输出结果
逐步分析
说实话,这个速度都惊到我了。计数排序的时间复杂度是O(n)
,缺点是限制值域为[0,k]
的整数。
正常计数排序是从0
开始的,本文实现的代码从min
开始,已优化。
点击查看更多排序算法
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/skylibiao/article/details/120494707
内容来源于网络,如有侵权,请联系作者删除!