数据结构 排序

本文将介绍各种排序算法。

一、直接插入排序

  • 每一轮排序中，将新元素插入到已排序好的序列中的合适位置
  • 时：o(n2)
  • 空：o(1)
  • 稳定
  • 适用于顺序表、链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 直接插入排序
 */
void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

二、冒泡排序

  • 每一轮排序中，依次比对相邻的两项，按大小交换位置，直至将最大元素 “沉底”
  • 时：o(n2)
  • 空：o(1)
  • 稳定
  • 适用于顺序表、链表
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 冒泡排序
 */
void bubbleSort(int[] arr) {
    int length = arr.length;
    for (int right = length - 1; right > 0; right--) {  // right表示每次排序的终点
        for (int i = 1; i <= right; i++) {
            if (arr[i - 1] > arr[i]) {
                swap(arr, i, i - 1);
            }
        }
    }
}

三、简单选择排序

  • 每一轮排序中，扫描待排序序列，找到最小元素，将其交换到已排序序列的末尾
  • 时：o(n2)
  • 空：o(1)
  • 不稳定
  • 适用于顺序表、链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 简单选择排序
 */
void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i; j < arr.length; j++) {
            if (arr[j] <= arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

四、快速排序

  • 递归地对序列进行 “左大右小” 的划分，直至每个部分只有一个元素
  • 时：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
35
/**
 * 快速排序
 */
void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

void quickSort(int[] arr, int low, int height) {
    if (low >= height) {
        return;
    }
    int flag = partition(arr, low, height);  // 枢轴
    quickSort(arr, low, flag - 1);
    quickSort(arr, flag + 1, height);
}

/**
 * 划分
 * <p>以low所指的元素为枢轴，对low到height的数组进行 "左大右小" 的划分
 */
int partition(int[] arr, int low, int height) {
    int temp = arr[low];
    while (low < height) {
        while (low < height && arr[height] >= temp) {
            height--;
        }
        arr[low] = arr[height];
        while (low < height && arr[low] <= temp) {
            low++;
        }
        arr[height] = arr[low];
    }
    arr[low] = temp;
    return low;
}

五、归并排序

  • 先划分（递归地将序列二分），再合并（递归地将拆分成的子项两两合并）
  • 时：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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 归并排序
 */
void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}

void mergeSort(int[] arr, int low, int height) {
    if (low >= height) {
        return;
    }
    int mid = (low + height) / 2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, height);
    merge(arr, low, mid, height);
}

void merge(int[] arr, int low, int mid, int height) {
    int[] tempArr = Arrays.copyOf(arr, arr.length);
    int index = low;
    int i = low, j = mid + 1;
    while (i <= mid && j <= height) {
        if (tempArr[i] <= tempArr[j]) {
            arr[index] = tempArr[i];
            i++;
        } else {
            arr[index] = tempArr[j];
            j++;
        }
        index++;
    }
    while (i <= mid) {
        arr[index] = tempArr[i];
        i++;
        index++;
    }
    while (j <= height) {
        arr[index] = tempArr[j];
        j++;
        index++;
    }
}