1.选择排序(了解)

算法思路:

每轮选取当前未排序的元素中最小的元素交换到未排序部分的最开头,经过若干步骤就能排序完整个数组。即:先选出最小的,然后选出第二小的,依次类推。

算法实现:

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
49
50
51
52
53
54
55
56
57
58
59
60
package edu.sort;

import java.util.Arrays;

/**
* @auther xiaochen
* @create 2022-08-15 8:58
*/
public class SelectionSort {
public static void main(String[] args) {
int[] nums = {3, 5, 7, 1, 9, 2, 8, 6};
SelectionSort sort = new SelectionSort();
int[] sortArray = sort.sortArray(nums);
System.out.println(Arrays.toString(sortArray));
}

/**
* 选择排序
*
* @param nums
* @return
*/
public int[] sortArray(int[] nums) {
int len = nums.length;
//[0,i]表示有序区间,该区间所有元素排序完毕
for (int i = 0; i < len - 1; i++) {
//当前最小值的索引,初始假设是i
int minIndex = i;

//选择[i,len-1]里的最小元素,和索引i位置的元素交换
//即将未排序部分的最小元素放到未排序部分的开头
for (int j = i + 1; j < len; j++) {
//找到了更小的值,将最小元素索引进行更新
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}

//将最小元素与索引i位置元素交换
swap(nums, i, minIndex);


}
return nums;


}

/**
* 交换元素
* @param nums
* @param index1
* @param index2
*/
public void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}

总结:

  • 算法思想:
    1. 贪心算法:每次决策都选当前最优,当前最优则全局最优。但是这种思想不是任何时候都适用。
    2. 减治思想:外层循环每次都能排定一个元素,问题规模逐渐减小,直到全部解决。即大而化小,小而化无
    3. 优点:交换次数最少

复杂度分析:

  • 时间复杂度:O(N2),N为数组长度。
  • 空间复杂度:O(1),只使用到了常数个临时变量。

2.插入排序(熟悉)

算法思路:

每次将一个元素插入到一个有序的数组里,使之成为一个更长的有序数组,有限次操作之后,数组整体有序。

img

图片来自「力扣」第 147 题:对链表进行插入排序

算法实现:

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
package edu.sort;

import java.util.Arrays;

/**
* @auther xiaochen
* @create 2022-08-15 9:22
*/
public class InjectionSort {
public static void main(String[] args) {
int[] nums = {3, 5, 7, 1, 9, 2, 8, 6};
InjectionSort sort = new InjectionSort();
int[] sortArray = sort.sortArray(nums);
System.out.println(Arrays.toString(sortArray));
}

/**
* 插入排序,稳定排序,在接近有序的情况下,表现比较好
* @param nums
* @return
*/
public int[] sortArray(int[] nums) {
int len = nums.length;

//将num[i]插入到区间[0,i]使之仍然是有序数据,初始有序数组区间为为[0,0]
for (int i = 0; i < len; i++) {
//使用一个临时变量保存nums[i],然后将i之前的元素后移,然后插入i
int temp = nums[i];
int j = i;
//nums[j - 1] > temp是寻找插入位置
//j > 0是边界条件
while (j > 0 && nums[j - 1] > temp) {
//元素后移
nums[j] = nums[j - 1];
j--;
}
//插入操作
nums[j] = temp;
}
return nums;
}
}

总结:

  • 插入排序在“几乎有序”的数组和“短数组”中表现良好,因此在小区间内执行排序任务的时候可以使用插入排序。
  • 由于我们的内层循环的判断条件是nums[j-1] > temp,所以在数组几乎有序的情况下,插入排序的时间复杂度可以达到O(N)。

复杂度分析:

  • 时间复杂度:O(N2),N为数组长度。
  • 空间复杂度:O(1),只使用到了常数个临时变量。

3.归并排序(重点

算法思路:

  • 基本思路:借助额外空间,合并两个有序数组,使之成为一个更长的有序数组。
  • 算法思想:分治思想。

大佬建议:「归并排序」是理解「递归思想」的非常好的学习材料,大家可以通过理解:递归完成以后,合并两个有序数组的这一步骤,想清楚程序的执行流程。即「递归函数执行完成以后,我们还可以做点事情」。因此,「归并排序」我个人觉得非常重要,一定要掌握。

作者:liweiwei1419
链接:https://leetcode.cn/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/

算法实现:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package edu.sort;

import java.util.Arrays;

/**
* @auther xiaochen
* @create 2022-08-15 9:51
*/
public class MergeSort {


public static void main(String[] args) {
int[] nums = {3, 5, 7, 1, 9, 2, 8, 6};

sort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
// 归并排序


public static void sort(int[] nums, int left, int right) {
//只有一个元素,肯定是有序的,递归出口
if (left == right) {
return;
}
//将数组分成两半
int mid = left + ((right - left) >> 1);
//对左边进行排序
sort(nums, left, mid);
//对右边进行排序
sort(nums, mid + 1, right);
//归并
merge(nums, left, mid + 1, right);
}


public static int[] merge(int[] nums, int leftPtr, int rightPtr, int rightBound) {
//辅助数组,用于每次存储每次排序好的数组
int[] help = new int[rightBound - leftPtr + 1];

int i = 0;

int mid = rightPtr - 1;

//左部分数组的开始指针
int p1 = leftPtr;
//右部分数组的开始指针
int p2 = rightPtr;

//将两个数组进行归并
while (p1 <= mid && p2 <= rightBound) {
help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
//要么p1越界,要么p2越界
while (p1 <= mid) {
help[i++] = nums[p1++];
}

while (p2 <= rightBound) {
help[i++] = nums[p2++];
}
//把排序好的数组刷回去
for (i = 0; i < help.length; i++) {
nums[leftPtr + i] = help[i];
}
return nums;
}


}

总结:

  • 将无序数组拆分,排序后再合并成大的有序数组。

复杂度分析

  • 时间复杂度:O(N log N),这里 NN 是数组的长度;
  • 空间复杂度:O(N),辅助数组与输入数组规模相当。

4.冒泡排序

算法思路:

两两交换,⼤的放在后⾯,第⼀次排序后最⼤值已在数组末尾。因为两两交换,需要 n-1 趟排序(⽐如10个数,需要9趟排序)

算法实现:

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 class BubbleSort {
public static void main(String[] args) {
int[] nums = {2,5,4,9,1,6,8};
System.out.println(Arrays.toString(nums));
sort(nums);
System.out.println(Arrays.toString(nums));

}

public static void sort(int[] nums) {

int len = nums.length;


//外层循环控制排序的趟数,一共n - 1趟
for (int i = 0; i < len - 1; i++) {

// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
boolean flag = true;

//内层循环控制比较的次数
for (int j = 0; j < len - i - 1; j++) {
//如果前一位比后一位大,则交换
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;

flag = false;
}
}
//如果当前趟没有元素交换,则证明数组已经排好序
if (flag) {
break;
}
}
}
}

复杂度分析:

  • 时间复杂度:O(N2)
  • 空间复杂度:O(1)

5.快速排序

算法思路:

数组中找⼀个元素(节点),⽐它⼩的放在节点的左边,⽐它⼤的放在节点右边。⼀趟下来,⽐节点⼩的在
左边,⽐节点⼤的在右边。不断执⾏这个操作….

算法实现:

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
49
50
51
52
53
54
55
56
57
public class QuickSort {
public static void main(String[] args) {
int[] nums = {2,5,4,9,1,6,8};
System.out.println(Arrays.toString(nums));
quickSort(nums,0,nums.length-1);
System.out.println(Arrays.toString(nums));
}

/**
*
* @param nums 待排序数组
* @param left 数组第一个元素
* @param right 数组最后一个元素
*/
public static void quickSort(int[] nums, int left, int right) {
int i = left;
int j = right;


//选取数组中间元素为基准
int pivot = nums[left + (right - left) / 2];

//
while (i <= j){
//寻找左边第一个比基准大的节点
while (pivot > nums[i]){
i++;
}
//寻找右边第一个比基准小的节点
while (pivot < nums[j]){
j--;
}

//此时找到了左边第一个比基准大的节点和右边第一个比基准小的节点
//将它们交换
if (i <= j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
//记得更新i和j的值
i++;
j--;
}
//递归对基准左边的数组排序,直到左边只剩一个数(递归出口)
if (left < j){
quickSort(nums,left,j);
}
//递归对基准右边的数组排序,直到右边只剩一个数(递归出口)
if (right > i){
quickSort(nums,i,right);
}


}
}

}

复杂度分析:

时间复杂度:O(N log N)
空间复杂度:O(logN),这里占用的空间主要来自递归函数的栈空间。