排序算法

前言

每次做笔记都喜欢加点前言,好像很高大上的样子。最近在研究爬虫,其中涉及到深度广度遍历算法。想想这几年已经把大学学的数据结构算法设计都忘的一干二净了。想着不能这么废下去了,慢慢来,一点一点补。
还是那句话,只要想学习了,什么时候都不晚,教操作系统的教授说过的话,真的是可以一辈子调侃的话了。先从最基础的算法回忆起,学C的时候学的排序算法:简单选择排序和冒泡排序。

简单选择排序

对于简单选择排序,我的理解是每次拿出一个值,和剩下的所有值进行比较,选出最小(大)的值,每轮循环结束,将比较值与最值进行交换,当所有的值都被拿出来与其他值比较后,即为有序数列。
例子:升序排序
初始值的状态:6 3 5 2 1 7
一轮循环结束:_1_ 3 5 2 _6_ 7
二轮循环结束:1 _2_ 5 _3_ 6 7
三轮循环结束:1 2 _3_ _5_ 6 7
四轮循环结束:1 2 3 5 6 7
五轮循环结束:1 2 3 5 6 7
一轮循环中:6和3 5 2 1 7都进行比较,1是最小值,循环结束,然后将6和1交换位置,这样最小值被选出。
一轮循环中:3和5 2 6 7都进行比较,2是最小值,循环结束,然后将3和2交换位置,这样最小值被选出。
依次循环得出有序数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] choose(int[] num) {
int temp;
for (int i = 0; i < num.length - 1; i++) {
int index = i;
for (int j = i + 1; j < num.length; j++) {
if (num[index] > num[j]) {
index = j;
}
}
if (index != i){
temp = num[i];
num[i] = num[index];
num[index] = temp;
}
}
return num;
}

该算法平均时间复杂度为(n-1)+(n-2)+…+1=n(n-1)/2=O(n2)

冒泡排序

冒泡排序的思想和选择差不多,冒泡的思想每次都从下往上两两比较,互换位置,就像气泡不停往上冒一样,每次循环选出一个最值放到队头。
例子:升序排序
初始值的状态:6 3 5 2 1 7
第一次:6 3 5 2 1 7
第二次:6 3 5 1 2 7
第三次:6 3 1 5 2 7
第四次:6 1 3 5 2 7
第五次:1 6 3 5 2 7
一轮循环结束:1 6 3 5 2 7
第一次:1 6 3 5 2 7
第二次:1 6 3 2 5 7
第三次:1 6 2 3 5 7
第四次:1 2 6 3 5 7
二轮循环结束:1 2 6 3 5 7
。。。
三轮循环结束:1 2 3 6 5 7
。。。
四轮循环结束:1 2 3 5 6 7
。。。
五轮循环结束:1 2 3 5 6 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] bubble(int num[]) {
//优化标志位,若内层一次循环未发生交换则说明数组已为有序
boolean flag = true;
//外层控制循环次数
for (int i = 0; i < num.length && flag; i++) {
flag = false;
//内层从队尾往上遍历
for (int j = num.length - 1; j > i; j--) {
if (num[j] < num[j - 1]) {
int temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
sortNum++;
flag = true;
}
}
}
return num;
}

这里加上一个flag标示,表示若在内层一次循环中,未发生任何交换,则说明数列已有序。排序可结束。
冒泡排序的平均时间复杂度为(n-1)+(n-2)+…+1=n(n-1)/2=O(n2)

坚持原创技术分享,您的支持将鼓励我继续创作!