2018年Coding被腾讯收购后变成了腾讯开发者平台,一直不温不火。今年一月份有又要改名为新Coding,真是命途多舛,还好提供的服务一直可以满足我的需求。虽然偶尔服务器宕机,但是速度快呀,Coding pages还是真香。由于今年网站再次改版,之前的pages要停止服务了,貌似也没有通知一声,昨天修复了一下,看了下留言,我的小站还是有人浏览的。所以决定还是要好好经营下去。

最近看了一些书,有了一些新的感悟。学习是要有输出的,只有自己能把一个东西讲清楚才算真正学会了,那么就把最近研究和学习的一些东西给写下来吧。

大学学过的一些很基础的排序算法

冒泡排序

掌握一种算法不是把它的实现代码给背下来,而是理解他的思想。这样就可以做到以不变应万变。
冒泡排序的思想是:在一个n个数的乱序数组中,遍历整个数组(n-1)轮,每次遍历位数减少1,每次选择出一个最大的数放在数组的末尾,这样在经过(n-1)轮遍历之后,数组中所有的元素都是有序的。
原理:
冒泡排序

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubble(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j + 1] < arr[j]) {
arr[j + 1] = arr[j + 1] ^ arr[j];
arr[j] = arr[j + 1] ^ arr[j];
arr[j + 1] = arr[j + 1] ^ arr[j];
}
}
System.out.println("第" + (i) + "趟排序:" + Arrays.toString(arr));
}
}

上面我使用了一个不引入第三个变量,实现交换两个变量的值的技巧,一个数对另一个数进行两次异或运算得到的结果是这个数本身,交换a和b的值的方法:

1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

那么不管是最好的情况还是最坏的情况,实际判断的次数是不会减少的,是否可以优化呢?答案是肯定的,如果在最好的情况下,可以发现,在第一趟排序中所有的数都没有发生交换。
所以可以进行如下优化,当在一轮遍历中,如果没有两个数进行交换,就可以认为整体数组是有序的,优化之后的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void bubble(int[] arr) {
boolean flag = false;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j + 1] < arr[j]) {
flag = true;
arr[j + 1] = arr[j + 1] ^ arr[j];
arr[j] = arr[j + 1] ^ arr[j];
arr[j + 1] = arr[j + 1] ^ arr[j];
}
}
System.out.println("第" + (i) + "趟排序:" + Arrays.toString(arr));
// 在一趟排序中,若没有发生过交换,说明已经排好序了。
if (!flag) {
break;
} else {
flag = false;
}
}
}

选择排序

选择排序相对冒泡排序而言,交换的次数减少了,所以效率也提高了一些。选择排序的思想是:
经过(n-1)轮遍历,依次找到每个位置上该放的值。第1次遍历找到最小的值a,把它当到第一位;第2次遍历找到除最小值a以外的最小值b,把它放到第二位··· 直到(n-1)次遍历,找到最小值把它放到(n-1)位,即第倒数二位。此时数组为全局有序。
原理:
选择排序

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectSort(int[] arr) {
// 选择排序 时间复杂度O(n^2)
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}

插入排序

选择排序的思想是找位置,与选择排序不同,插入排序的思想是找一个有序的区间,保证这个区间内是有序的。通过一次次的遍历,逐渐扩大这个有序区间,直到区间大小等于数组大小,即数组全局有序。所谓逐渐扩大,即把待插入的数,插入到有序区间内属于这个数的恰当位置。

原理:
插入排序

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {

// 定义待插入的数
int insertVal = arr[i];
//即arr[i]前面这个数的下标
int insertIndex = i - 1;

//给insertVal找到插入的位置
//说明
//1.insertIndex >= 0保证在给insertVal找插入位置,不越界
//2.insertVal < arr[insertIndex]待插入的数,还没有找到插入位置
//3.就需要将arr[insertIndex]后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}

//当退出while循环时,说明插入的位置找到,insertIndex + 1
arr[insertIndex + 1] = insertVal;
System.out.println("第" + i + "轮插入");
System.out.println(Arrays.toString(arr));
}
}