排序算法总结

关于冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序的总结。

冒泡排序

思路:两两比较,大的沉底。i是轮数,在进行第i轮的时候确定了最大的i个值;如果一轮下来都没有交换证明已经有序

时间复杂度:O(n²),最好时间复杂度O(n)

空间复杂度:O(1)

稳定性:可以实现成稳定的

写冒泡排序自己的错误:

  • 因为循环中有j+1作为索引,所以j的边界结束值是j == nums.length - 2 - i,而不是nums.length - 1 - i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] nums) {
boolean sorted = true;
for (int i = 0; i <= nums.length - 1; i ++) {
for (int j = 0; j <= nums.length - 2 - i; j ++) {
if (nums[j] > nums[j + 1]) {
sorted = false;
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
if (sorted) return;
}
}

插入排序

思路:像小孩子插扑克牌一样,要一张张比,把第1张和第0张比较,把第2张和[0,1]张比较,从后往前把第i张牌和第i-1,i-2…张牌比较,比前面的小就和前面的数交换位置,插第i张的时候前面i-1张都已经有序了

时间复杂度:O(n²),最好时间复杂度O(n)

空间复杂度:O(1)

稳定性:可以实现成稳定的

1
2
3
4
5
6
7
8
9
10
11
public static void insertionSort(int[] nums) {
for (int i = 1; i < nums.length; i ++) {
for (int j = i; j >= 1; j --) {
if (nums[j] < nums[j - 1]) {
int tmp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = tmp;
}
}
}
}

选择排序

思路:遍历[0,n-1]位置选出最小的和nums[0]交换位置,再遍历[1,n-1]位置选出第二小的和nums[1]交换…第i轮(i从0开始)选数的时候前i个位置[0,i-1]的数都已经是在正确的位置上了,待选的范围是[i, n-1],第i轮选完[0.i]都在正确位置上了

时间复杂度:O(n²),最好时间复杂度O(n²)

空间复杂度:O(1)

稳定性:无法实现成稳定的

写选择排序自己的错误:

  • 在全局定义了minIndex的起始值是0,后面忘记了应该是i,而不是一直是0,应该把minIndex放在for循环中赋值,每次进入for循环都有不同的minIndex
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void selectionSort(int[] nums) {
for (int i = 0; i <= nums.length - 2; i ++) {
int minIndex = i;
for (int j = i; j < nums.length; j ++) {
minIndex = nums[j] < nums[minIndex] ? j : minIndex;
}
if (minIndex != i) {
int tmp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = tmp;
}
}
}

归并排序

思路:分治后从下往上两两归并,借助mergeSortPart分别将左边和右边sort,再将两边merge起来。

时间复杂度:O(nlogn),最好时间复杂度O(nlogn)

空间复杂度:O(n)

稳定性:可以实现成稳定的

写归并排序的时候自己的几个错误:

  • p2的起始值是mid + 1而不是mid
  • 前面i已经在全局中被定义了,后面写for (int i = 0; i < nums.length; i ++)又习惯性地加了int,重复定义了变量。
  • int mid = lo + ((hi - lo) >> 1);要注意>>的优先级。
  • 注意i的范围是[0, n - 1],nums下标的范围是[lo, hi]
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
public static void mergeSort(int[] nums) {
if (nums == null || nums.length < 2) return;
mergeSortPart(nums, 0, nums.length - 1);
}

public static void mergeSortPart(int[] nums, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + ((hi - lo) >> 1);
mergeSortPart(nums, lo, mid);
mergeSortPart(nums, mid + 1, hi);
merge(nums, lo, mid, hi);
}

public static void merge(int[] nums, int lo, int mid, int hi) {
int length = hi - lo + 1;
int[] helper = new int[length];
int p1 = lo, p2 = mid + 1;
int i = 0;

while (p1 <= mid && p2 <= hi) {
helper[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
while (p1 <= mid) {
helper[i++] = nums[p1++];
}
while (p2 <= hi) {
helper[i++] = nums[p2++];
}

for (i = 0; i < length; i ++) {
nums[lo + i] = helper[i];
}
}

快速排序

思路:

  • partition函数:随机取一个基准点,把基准点和最后一个数交换,partition函数的目的是要将[lo,hi]从左到右分为小于基准点区域、等于基准点区域、大于基准点区域三个区域,然后返回等于区域的左右下标给quickSortPart函数。partition的实现看成往小于区域和大于区域发货。
  • quickSortPart函数:调用partition函数,partition后返回等于区域下标后在小于区域和大于区域中递归调用自己,直到小于区域和大于区域都只有一个数。
  • quickSort函数:调用quickSortPart函数,实现快排。

时间复杂度:O(nlogn)

空间复杂度:O(logn)(因为递归深度是logn,用用来记录切分点)

稳定性:无法实现成稳定的

记一个结论 随机得到一个在[lo, hi]之间的数:(int)(lo + length * Math.random()) = (int) (lo + (hi - lo + 1) * Math.random())

注意:用位运算交换两个数有一个问题,就是当lo == hi的时候,是同一个数,就会将这个数清零(nums[lo] == nums[hi]不会,lo == hi会)

1
2
3
4
5
6
public static void swap(int[] nums, int lo, int hi) {
if (lo == hi) return; // 要排除lo == hi的情况
nums[lo] = nums[lo] ^ nums[hi];
nums[hi] = nums[lo] ^ nums[hi];
nums[lo] = nums[lo] ^ nums[hi];
}

写快排的时候自己的几个错误:

  • swap(int[] nums, int lo, int hi)函数没有去除lo == hi的情况,使得一旦同一个数自己和自己发生交换就会清零。
  • swap(nums, (int) (lo + length * Math.random()), hi);写成swap(nums, int(lo + length * Math.Random()), hi);一个是类型转换的括号要打在int上,一个是random()是小写。
  • 不要忘记随机选一个数和最后一个数nums[hi]换作为基准点,nums[hi]一直呆在大于队列中,最后不要忘了把nums[hi]nums[more]调换,放回到等于队列中。
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
public static void quickSort(int[] nums) {
if (nums == null || nums.length < 2) return;
quickSortPart(nums, 0, nums.length - 1);
}

public static void quickSortPart(int[] nums, int lo, int hi) {
if (lo >= hi) return;
int[] equalRange = partition(nums, lo, hi);
quickSortPart(nums, lo, equalRange[0] - 1);
quickSortPart(nums, equalRange[1] + 1, hi);
}

public static int[] partition(int[] nums, int lo, int hi) {
int length = hi - lo + 1;
// 随机选取基准点和最后一个数交换
// Math.Random() [0,1) -> (hi-lo+1) * Math.Random() [0,hi-lo+1)
// lo + (hi-lo+1) * Math.random() [lo, lo+hi-lo+1)=[lo, hi+1)=[lo,hi]
swap(nums, (int) (lo + length * Math.random()), hi);
int less = lo - 1;
int more = hi; // more从hi开始,保护nums[hi]在大于区域中不会被换掉,最后再替换
int cur = lo;
while (cur < more) {
// 小于的话,和小于边界右边的第一个数交换位置,less++
// 小于边界右边的第一个数一定是等于区域的数,所以直接cur++
if (nums[cur] < nums[hi]) {
swap(nums, cur ++, ++ less);
// 等于的话,直接cur++就可以了
} else if (nums[cur] == nums[hi]) {
cur ++;
// 大于的话,和大于边界左边的第一个数交换位置,more--
// 大于边界左边的第一个数是未知的,所以要再考察cur不能++
} else {
swap(nums, cur, -- more);
}
}
swap(nums, more ++, hi);
return new int[]{less + 1, more - 1};
}

public static void swap(int[] nums, int lo, int hi) {
if (lo == hi) return;
nums[lo] = nums[lo] ^ nums[hi];
nums[hi] = nums[lo] ^ nums[hi];
nums[lo] = nums[lo] ^ nums[hi];
}

堆排序

完全二叉树 = 堆 = 优先级队列

思路:

  • 完全二叉树是一种逻辑结构,实际存储在数组中,nums[i]的左节点是nums[2 * i + 1],右节点是nums[2 * i + 2],父节点是nums[(i - 1) / 2]
  • heapInsert()建堆函数:当堆中插入一个新节点(第i号节点nums[i])时,向上和父节点比大小,若大则换,不断调整成大根堆
  • heapify()调整函数:节点上的某个值变小后要下沉,若左右两个孩子中最大的比我大则和我交换,不断下沉直到[0, heapSize - 1]范围恢复成一个大根堆。
  • heapSort()堆排序:每次堆的头和堆的最后一个数交换,最后一个最大的数固定,heapSize --,由于头被换成了一个比较小的数,于是要做一次heapify()调成大根堆,再重复每次将堆的头和堆的最后一个数交换。

时间复杂度:O(nlogn)

空间复杂度:O(1)

稳定性:无法实现成稳定的

记一个结论:把完全二叉树逻辑结构存在数组实际结构中,nums[i]的左节点是nums[2 * i + 1],右节点是nums[2 * i + 2],父节点是nums[(i - 1) / 2]

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
public static void heapInsert(int[] nums, int i) {
while (nums[i] > nums[(i - 1) / 2]) {
swap(nums, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}

public static void heapify(int[] nums, int i, int heapSize) {
int leftIndex = 2 * i + 1;
while (leftIndex <= heapSize - 1) {
int maxIndex = leftIndex + 1 <= heapSize - 1 && nums[leftIndex + 1] > nums[leftIndex] ? leftIndex + 1 : leftIndex;
maxIndex = nums[maxIndex] > nums[i] ? maxIndex : i;
if (maxIndex == i) return;
swap(nums, maxIndex, i);
i = maxIndex;
leftIndex = 2 * i + 1;
}
}

public static void heapSort(int[] nums) {
if (nums == null || nums.length < 2) return;
for (int i = 1; i < nums.length; i ++) {
heapInsert(nums, i);
}
int heapSize = nums.length;
while (heapSize >= 2) {
swap(nums, 0, -- heapSize);
heapify(nums, 0, heapSize);
}
}

public static void swap(int[] nums, int i, int j) {
if (i == j) return;
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
谢谢小天使请我吃糖果
0%