必须掌握的八种基本排序算法
一、冒泡排序:
- 1.1 原理:
?这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
??1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
??2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
??3. 针对所有的元素重复以上的步骤,除了最后一个。
??4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
文章图片
冒泡排序
- 1.2 代码
private static void sort(int[] array) throws Exception {
if (array == null || array.length == 0) {
throw new Exception("the array is null or no element...");
}
System.out.println("冒泡排序优化前...");
int n = array.length;
for (int i = 0;
i < n;
i++) {
for (int j = 0;
j < n - i - 1;
j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
System.out.println("第" + (i + 1) + "轮后: " + Arrays.toString(array));
}
}第1轮后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
第2轮后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
第3轮后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
第4轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第5轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第6轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第7轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第8轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第9轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
从上述的log打印中,可以看出来:在第4轮时就已经排好序了,所以从第5轮到第9轮均是无用操作。
private static void optimizeSort(int[] array) throws Exception {
if (array == null || array.length == 0) {
throw new Exception("the array is null or no element...");
}
System.out.println("冒泡排序优化后...");
int n = array.length;
for (int i = 0;
i < n;
i++) {
// 设定一个排序完成的标记
// 若为 true,则表示此次循环没有进行交换,即待排序列已经有序,排序已然完成
boolean success = true;
for (int j = 0;
j < n - i - 1;
j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
success = false;
}
}
if (success) {
break;
}
System.out.println("第" + (i + 1) + "轮后: " + Arrays.toString(array));
}
}
第1轮后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
第2轮后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
第3轮后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
第4轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
1.3 复杂度
- 时间复杂度:
两层循环,第1次遍历n次(n个元素),第二次遍历n-1次,... 依次类推。因此,表达式如下:
[图片上传失败...(image-6c19e2-1576217576910)]
- 空间复杂度:
没有利用新的数组来帮助完成排序算法,我们认为其空间复杂度为[图片上传失败...(image-4d7de1-1576217576910)]
【必须掌握的八种基本排序算法】https://www.runoob.com/w3cnote/quick-sort.html
推荐阅读
- 热闹中的孤独
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 放屁有这三个特征的,请注意啦!这说明你的身体毒素太多
- 一个人的旅行,三亚
- 布丽吉特,人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事,我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量