1、选择排序

1.1、选择排序思路

选择排序( select sorting)也是一种简单的排序方法。

它的基本思想是:第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1]arr[n - 1]中选取最小值,与arr[1]交换,第三次从arr[2]arr[n-1]中选取最小值,与arr[2]交换,…,第 i 次从arr[i-1]arr[n-1]中选取最小值与arr[i-1]交换,…,第n-1次从arr[n-2]arr[n-1]中选取最小值,与arr[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

1.2、思路分析图

image-20210330140137749

1.3、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int minValue = arr[i];
// 这里需要从 i + 1下标开始
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < minValue) {
minValue = arr[j];
minIndex = j;
}
}
//退出循环后,交换arr[i]与后面数组中找到的最小值
//这里注意,如果minIndex = i,那么证明当前arr[i]是后面数组的最小值
//此时不需要发生交换
if(minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = minValue;
}
}
}

1.4、测试

在main方法中创建一个数组,使用选择排序进行排序

1
2
3
int[] arr = {101,88,777,1,-100,108};
selectSort(arr);
System.out.println(Arrays.toString(arr));

排序结果如下

image-20210330142416210

2、插入排序

2.1、插入排序算法介绍

插入排序属于内部排序法,是对要排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的

2.2、基本思想

插入排序的基本思想是:把n个待排序元素看为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中有 n - 1 个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,然后把它插入到有序表的适当位置,使之成为新的有序表

2.3、思路图

image-20210330142927006

2.4、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
int insertIndex = i - 1;
//1 insertIndex >= 0保证数组下标不越界
//2 insertVal < arr[insertIndex]证明insertVal还没有找到待插入位置
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
//让数组元素往后挪一位
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
}
}

3、快速排序

3.1、介绍

快速排序(Quick sort)是对冒泡排序的一种改进;

基本思想是:通过一趟排序将要排序的数据分割为独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据都变为有序序列。

3.2、示意图

image-20210330144811648

3.3、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int temp = 0;
//确定中轴值
int pivot = arr[(left + right) / 2];
//开始循环,当边界无法严格形成区间时,退出循环
//while循环的目的是:让比pivot小的值全部移动到pivot左边
//比pivot大的值全部移到pivot右边
while(l < r) {
//在左边找到一个比pivot大的值
while(arr[l] < pivot) {
l += 1;
}
//在右边找到一个比pivot小的值
while(arr[r] > pivot) {
r -= 1;
}
//如果l >= r,说明pivot左边的值已经全部小于等于pivot
//右边的值全部大于等于pivot
if(l >= r) {
break;
}
//使用一个临时变量,交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换后发现arr[l] = pivot
if(arr[l] == pivot) {
r -= 1;
}
if(arr[r] == pivot) {
l += 1;
}
}
//如果l == r,必须让l ++
if(l == r) {
l += 1;
r -= 1;
}
//向左递归
if(left < r) {
quickSort(arr,left,r);
}
if(right > l) {
quickSort(arr,l,right);
}
}