常见的排序算法

插入排序，快排，归并排序

让我们以两个常见的java库函数讲起:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Arrays;
import java.util.concurrrenet.ThreadLocalRandom;
/*
第一个函数就是在第一个库里面
可以直接被我们打印出来
方便最后的封装
*/
//ie:
int[] arr = new[]{1, 2, 3, 4};
System.out.println(Arrays.toString(arr));
//输出结果为1, 2, 3, 4

//第二个函数是在第二个库中
//可以在给定范围内生成一个随机数字
int num = ThreadLocalRandom.current().nextInt(0, 100);
//在[0, 100)中随机随机生成
  • BubbleSort(冒泡排序):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void BubbleSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr.length - 1 - i; j++){
                if(arr[j] > arr[j + 1]){
                    swap(arr, j, j + 1);
                }
            }
        }
    }
public static void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

很简单，主要思想就是每遍历完一遍数组那么都会有一个数被排到正确的位置

ie. arr = {2, 5, 3, 8} 遍历完第一遍时，arr[0]上就是正确的排序位置.

  • Insertion sort(插入排序):
1
2
3
4
5
6
7
8
9
10
11
12
13
public class InsertionSort {
		public static int Sort(int[] array) {
				for(int i = 1; i < array.length; i++) {
						cur = array[i];
						j = i - 1;
						while(j >= 0 && array[j] > cur) {
								array[j + 1] = array[j];
								j--;
						}
						array[j + 1] = cur;
				}
		}
}

Quick sort(快排)：是一种分治算法(Divide and conquer) 大问题——>小问题

首先找一个pivot(目标元素)
把小的排到pivot之前，大的排到pivot之后
把一整个数组分成无数个子数组然后进行排序，直到子数组的长度小于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
public static void QuickSort(int[] arr, int left, int right){
		if(left <= right){return;}//如果子数组小于1，则 left <= right
		int patitionIndex = partition(arr, left, right);
		QuickSort(arr, left, partitionIndex - 1);
		QuickSort(arr, partitionIndex + 1, right);
}

public static int partition(int[] arr, left, right){
		int pivot = arr[right];
		int leftIndex = left;
		int rightIndex = right - 1;
		while(true){
				while(leftIndex < right && arr[leftIndex] < pivot){
						leftIndex ++;
				}
				while(rightIndex >= left && arr[rightIndex] >= pivot){
						rightIndex --;
				}
				if(leftindex > rightIndex){
						swap(arr, leftIndex, rightIndex);
				}
		}
		swap(arr, right, leftiIndex);
		return leftIndex;
}

public static void swap(int[] arr, left, right){
		int tmp = arr[right];
		arr[right] = arr[left];
		arr[left] = tmp;
}

MergeSort(归并排序)

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 Sort(int[] arr){
		MergeSort(arr, 0, arr.length - 1);
}

public static void MergeSort(int[] arr, int start, end){
		if(start == end){
			return;
		}
		int mid = (start + end) / 2;
		MergeSort(arr, start, mid);
		MergeSort(arr, mid + 1, end);
		Merge(arr, start, mid + 1, end);
}

public static void Merge(int[] arr, int start1, int start2, int end){
		int len1 = start2 - start1;
		int[] tmp = new int[len1];
		System.arraycopy(arr, start1, tmp, 0, len1);
		int p1 = 0;
		int p2 = start2;
		for(int i = 0; i <= end; i ++){
				if(tmp[p1] < arr[p2]){
						arr[i] = tmp[p1];
						p1 ++;
						if(p1 == len1){break;}
				}else{
						arr[i] = arr[p2];
						p2 ++;
						if(p2 > end){
								while(p1 < len1){
										i ++;
										array[i] = tmp[p1];
										p1 ++;
								}
						}
				}
		}
}

归并排序有一种我个人认为更舒服的写法，其实也就是利用左闭右开的基本思想，然后将输入的数组整体赋值给tmp

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
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

class MergeSort{
    public static void main(String[] args){
        int[] arr = new int[50];
        for(int i = 0; i < 50; i++){
            arr[i] = ThreadLocalRandom.current().nextInt(0, 100);
        }
        System.out.println(Arrays.toString(arr));
        Sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void Sort(int[] arr){
        mergeSort(arr, 0, arr.length);
    }
    public static void mergeSort(int[] arr, int start, int end){
        if(end - start <= 1) {return;}
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid, end);
        Merge(arr, start, mid, end);
    }

    public static void Merge(int[] arr, int start, int mid, int end){
        int[] tmp = arr.clone();
        System.arraycopy(arr, start, tmp , 0, end - start);
        int p1 = start;
        int p2 = mid;
        int p3 = start;
        while(p1 < mid && p2 < end){
            if(tmp[p1] > tmp[p2]){
                arr[p3++] = tmp[p2++];
            } else {
                arr[p3++] = tmp[p1++];
            }
        }
        while(p1 < mid){
            arr[p3++] = tmp[p1++];
        }

        while(p2 < end){
            arr[p3++] = tmp[p2++];
        }
    }
}

最后, 时间空间复杂度如下

排序算法 最佳时间复杂度 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性
冒泡排序 (Bubble Sort) O(n) O(n²) O(n²) O(1) 稳定
插入排序 (Insertion Sort) O(n) O(n²) O(n²) O(1) 稳定
快速排序 (Quick Sort) O(n log n) O(n log n) O(n²) O(log n) 不稳定
归并排序 (Merge Sort) O(n log n) O(n log n) O(n log n) O(n) 稳定

注：

  • 稳定性指排序算法是否保持相等元素的相对顺序
  • 快排最差时间复杂度O(n²)出现在选择的pivot总是最大或最小元素的情况
  • 归并排序的空间复杂度为O(n)，因为需要额外的数组来合并结果

致谢

特别感谢以下人士和平台对本文内容的启发与帮助：

  • YouTube上的”图灵星球”频道
  • YouTube上的”阿婧不会写代码”
  • 小红书上的”zhou-london”

他们的精彩内容和讲解为本文和我的学习提供了宝贵的参考。今后会经常更新私人blog: https://shuyisteve.pages.dev/