➤ 算法 | 排序算法归纳

(Updated: )

先来几张图

image-20230406125316219

image-20230406125838826

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] bubbleSort(int[] arr) {    
    for (int i = 1; i < arr.length; i++) {
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {            
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = false;
            }
        }
        if (flag) break; // 优化：如果 arr 已是排好序的则 break，时间复杂度为 O(n)
    }
    return arr;
}
  • 算法描述：比较相邻元素，第一个比第二个大则交换，每次都可以将最大的数移到末尾，不断重复
  • 稳定性：稳定
  • 时间复杂度：最好 O(n)，最差 O(n^2)，平均 O(n^2)
  • 空间复杂度：O(1)
  • 排序方式：内部排序

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minId = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minId]) {
                minId = j;
            }
        }
        if (minId != i) {
            int tmp = arr[i];
            arr[i] = arr[minId];
            arr[minId] = tmp;
        }
    }
    return arr;
}
  • 算法描述：不断地从未排序序列中找到最大或最小元素，然后将其存放到未排序序列的末尾或开头，不断重复
  • 稳定性：不稳定
  • 时间复杂度：最好 O(n^2)，最差 O(n^2)，平均 O(n^2)
  • 空间复杂度：O(1)
  • 排序方式：内部排序

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preId = i - 1;
        int cur = arr[i];
        while (preId >= 0 && cur < arr[preId]) {
            arr[preId + 1] = arr[preId];
            preId--;
        }
        arr[preId + 1] = cur;
    }
    return arr;
}
  • 算法描述：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
  • 稳定性：稳定
  • 时间复杂度：最好 O(n)，最差 O(n^2)，平均 O(n^2)
  • 空间复杂度：O(1)
  • 排序方式：内部排序

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int cur = arr[i];
            int preId = i - gap;
            while (preId >= 0 && arr[preId] > cur) {
                arr[preId + gap] = arr[preId];
                preId -= gap;
            }
            arr[preId + gap] = cur;
        }
        gap /= 2;
    }
    return arr;
}
  • 算法描述：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序
  • 稳定性：不稳定
  • 时间复杂度：最好 O(nlogn)，最差 O(n^2)，平均 O(nlogn)
  • 空间复杂度：O(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
public static int[] mergeSort(int[] arr) {
    if (arr.length < 1) return arr;
    int mid = arr.length / 2;
    int[] arr_1 = Arrays.copyOfRange(arr, 0, mid);
    int[] arr_2 = Arrays.copyOfRange(arr, mid, arr.length);
    return merge(mergeSort(arr_1), mergeSort(arr_2));
}
public static int[] merge(int[] arr_1, int[] arr_2) {
    int len_1 = arr_1.length, len_2 = arr_2.length;
    int[] sorted_arr = new int[len_1 + len_2];
    int idx = 0, idx_1 = 0, idx_2 = 0;
    while (idx_1 < len_1 && idx_2 < len_2) {
        if (arr_1[idx_1] < arr_2[idx_2]) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 ++;
        } else {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 ++;
        }
        idx ++;
    }
    if (idx_1 < len_1) {
        while (idx_1 < len_1) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 ++;
            idx ++;
        }
    } else {
        while (idx_2 < len_2) {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 ++;
            idx ++;
        }
    }
    return sorted_arr;
}
  • 算法描述：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表
  • 稳定性：稳定
  • 时间复杂度：最好 O(nlogn)，最差 O(nlogn)，平均 O(nlogn)
  • 空间复杂度：O(n)
  • 排序方式：外部排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pos = partition(arr, low, high);
        quickSort(arr, low, pos - 1);
        quickSort(arr, pos + 1, high);
    }
}
public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int pointer = low;
    for (int i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            int tmp = arr[i];
            arr[i] = arr[pointer];
            arr[pointer] = tmp;
            pointer++;
        }
    }
    int tmp = arr[pointer];
    arr[pointer] = arr[high];
    arr[high] = tmp;
    return pointer;
}
  • 算法描述：通过从数组中选择一个中心元素将数组划分成两个子数组，在划分数组时，将比中心元素小的元素放在左子数组，将比中心元素大的元素放在右子数组；左子数组和右子数组也使用相同的方法进行划分，这个过程一直持续到每个子数组都包含一个元素为止；最后，将元素组合在一起以形成排序的数组
  • 稳定性：不稳定
  • 时间复杂度：最好 O(nlogn)，最差 O(nlogn)，平均 O(nlogn)
  • 空间复杂度：O(logn)
  • 排序方式：内部排序

堆排序

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
static int heapLen;
public static int[] heapSort(int[] arr) {
    heapLen = arr.length;
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapLen --;
        heapify(arr, 0);
    }
    return arr;
}
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
public static void buildMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, i);
    }
}
public static void heapify(int[] arr, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (right < heapLen && arr[right] > arr[largest])
        largest = right;
    if (left < heapLen && arr[left] > arr[largest])
        largest = left;
    if (largest != i) {
        swap(arr, largest, i);
        heapify(arr, largest);
    }
}
  • 算法描述：利用堆这种数据结构所设计的一种排序算法，堆的性质：即子结点的值总是小于（或者大于）它的父节点
  • 稳定性：不稳定
  • 时间复杂度：最好 O(nlogn)，最差 O(nlogn)，平均 O(nlogn)
  • 空间复杂度：O(1)
  • 排序方式：内部排序

😅 计数排序

😅 桶排序

😅 基数排序