排序算法总结

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

冒泡排序

思路:两两比较,大的沉底。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
2
3
4
5
6
7
8
9
public static void swap(int[] nums, int i, int j) {
// 当i==j时,nums[i]和nums[j]是相同的地址,会把自己清零
if (i == j) {
return;
}
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}

插入排序

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

i是这一轮正在找下标为i的数的位置

时间复杂度: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 - 1; 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

i为这一轮在选下标为i的数应该是谁

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 - 1; 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)

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

  • mergeSort(int[] nums):主函数用来调用mergeSortPart
  • mergeSortPart(int[] nums, int lo, int hi):递归调用自己,直到只有自己一个数了才两两合并,1+1合并成2,2+2合并成4

  • merge(int[] nums, int lo, int mid, int hi):把nums[lo, mid]和nums[mid+1, hi]用p1,p2作为索引,谁小取谁填到新的数组helper[n]中 n = hi - lo + 1,如果有一方取完则直接全部复制另一方剩下的,最后将helper[0, n - 1]对应地复制回nums[lo, hi]中。

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

  • 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
34
35
36
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];
// 注意p1,p2是nums中的下标,p1[lo, mid],p2[lo+1, hi]
int p1 = lo, p2 = mid + 1;
// i是new int[]中的下标,[0,n-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有++ 就不用helper[i++]
for (i = 0; i < length; i ++) {
nums[lo + i] = helper[i];
}
}

快速排序

思路:

  • quickSort函数:调用quickSortPart函数,实现快排。
  • quickSortPart函数:调用partition函数返回某一个数的相等区间,partition后返回等于区域下标后在小于区域和大于区域中递归调用自己,直到小于区域和大于区域都只有一个数。
  • partition函数:首先随机选一个数作为基准点,int pivot = nums[(int) (lo + length * Math.random())];,partition的实现看成往小于区域和大于区域发货,小于区域的初始界限less = lo - 1,大于区域的初始界限more = hi + 1,小于区域的界限右边粘着的是等于区域,从左到右依次是小于区域、等于区域、未知区域、大于区域,cur遍历每个数,如果nums[cur]<pivotswap(nums, cur++, ++less),如果nums[cur] == pivot则直接cur++,如果nums[cur] > pivotswap(nums, cur, --more),注意cur不能++,因为more的前一个数属于未知区域,还需要再考察这个数。

时间复杂度:O(nlogn)

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

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

记一个结论 随机得到一个在[lo, hi]之间的数:(int)(lo + length * Math.random()) = (int) (lo + (hi - lo + 1) * Math.random()) = (int)(lo + length) * 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
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]
int pivot = nums[(int) (lo + length * Math.random())];
int less = lo - 1, more = hi + 1;
int cur = lo;
while (cur < more) {
// 小于的话,和小于边界右边的第一个数交换位置,less++
// 小于边界右边的第一个数一定是等于区域的数,所以直接cur++
if (nums[cur] < pivot) {
swap(nums, cur++, ++less);
// 等于的话,直接cur++就可以了
} else if (nums[cur] == pivot) {
cur++;
// 大于的话,和大于边界左边的第一个数交换位置,more--
// 大于边界左边的第一个数是未知的,所以要再考察cur不能++
} else {
swap(nums, cur, --more);
}
}
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()堆排序:先将n个数建堆建成大根堆,每次堆的头和堆的最后一个数交换,最后一个最大的数固定,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
38
public static void heapSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
for (int i = 1; i <= nums.length - 1; i++) {
heapInsert(nums, i);
}
int lastHeapIndex = nums.length - 1;
while (lastHeapIndex >= 1) {
swap(nums, 0, lastHeapIndex--);
heapify(nums, 0, lastHeapIndex);
}
}

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 lastHeapIndex) {
int leftIndex = 2 * i + 1;
int rightIndex = leftIndex + 1;
while (leftIndex <= lastHeapIndex) {
int maxIndex = rightIndex <= lastHeapIndex && nums[rightIndex] > nums[leftIndex]
? rightIndex : leftIndex;
maxIndex = nums[maxIndex] > nums[i] ? maxIndex : i;
if (maxIndex == i) {
return;
}
swap(nums, maxIndex, i);
// 下一次的i和leftIndex/rightIndex
i = maxIndex;
leftIndex = 2 * i + 1;
rightIndex = leftIndex + 1;
}
}
谢谢小天使请我吃糖果
0%