排序算法

稳定排序与不稳定排序

如果排序后原本相等的两个数的相对位置发生了变化，则说明算法不是稳定排序算法。

冒泡排序

如果相邻的两个元素逆序，则交换。

冒泡排序是稳定排序算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def bubble_sort(nums: List[int]):
    n = len(nums)
    swapped = True

    while swapped:
        swapped = False
        for i in range(1, n):
            if nums[i] < nums[i - 1]:
                swapped = True
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void bubble_sort(vector<int> &nums) {
    int n  = nums.size();
    bool swapped = true;

    while (swapped) {
        swapped = false;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                swapped = true;
                swap(nums[i], nums[i - 1]);
            }
        }
    }
}

选择排序

选择 $a[i]$ 之后比 $a[i]$ 小的最小值与 $a[i]$ 进行交换。

选择排序是不稳定排序算法，如序列 $[3_1,3_2,2]$ 排序后变为了 $[2,3_2,3_1]$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def selection_sort(nums: List[int]):
    n = len(nums)

    for i in range(n - 1):
        k = i

        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j

        if k != i:
            nums[i], nums[k] = nums[k], nums[i]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void selection_sort(vector<int> &nums) {
    int n = nums.size();

    for (int i = 0; i < n - 1; ++i) {
        int k = i;

        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[k]) {
                k = j;
            }
        }

        if (k != i) {
            swap(nums[i], nums[k]);
        }
    }
}

插入排序

插入排序即将当前位置的数插入到之前已经有序的数之中。

插入排序是稳定排序算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def insertion_sort(nums: List[int]) -> None:
    n = len(nums)

    for i in range(1, n):
        t = nums[i]
        j = i - 1

        while j >= 0 and nums[j] > t:
            nums[j + 1] = nums[j]
            j -= 1

        nums[j + 1] = t

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void insertion_sort(vector<int> &nums) {
    int n = nums.size();

    for (int i = 1; i < n; ++i) {
        int t = nums[i], j = i - 1;

        while (j >= 0 && nums[j] > t) {
            nums[j + 1] = nums[j];
            --j;
        }

        nums[j + 1] = t;
    }
}

快速排序

将某个位置的数 $nums[i]$ 作为关键字，小于等于 $nums[i]$ 放在 $nums[i]$ 的左边，大于等于 $nums[i]$ 的数放在 $nums[i]$ 的右边。

快速排序是不稳定排序算法，如序列 $[3,2_1,2_2]$ 排序后后变为了 $[2_2,2_1,3]$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def partition(nums: List[int], lo: int, hi: int) -> int:
    pivot = nums[lo]

    while lo < hi:
        while lo < hi and nums[hi] >= pivot:
            hi -= 1
        nums[lo] = nums[hi]

        while lo < hi and nums[lo] <= pivot:
            lo += 1
        nums[hi] = nums[lo]

    nums[lo] = pivot

    return lo

def quick_sort(nums: List[int], lo: int, hi: int) -> None:
    if lo < hi:
        pos = partition(nums, lo, hi)

        quick_sort(nums, lo, pos - 1)
        quick_sort(nums, pos + 1, 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


int partition(vector<int> &nums, int lo, int hi) {
    int pivot = nums[lo];

    while (lo < hi) {
        while (lo < hi && nums[hi] >= pivot) {
            --hi;
        }
        nums[lo] = nums[hi];

        while (lo < hi && nums[lo] <= pivot) {
            ++lo;
        }
        nums[hi] = nums[lo];
    }

    nums[lo] = pivot;

    return lo;
}

void quick_sort(vector<int> &nums, int lo, int hi) {
    if (lo < hi) {
        int pos = partition(nums, lo, hi);

        quick_sort(nums, lo, pos - 1);
        quick_sort(nums, pos + 1, hi);
    }
}

归并排序

归并排序是稳定排序算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def merge(nums: List[int], tmp: List[int], lo: int, mid: int, hi: int) -> None:
    i, j, k = lo, mid + 1, 0

    while i <= mid or j <= hi:
        if i <= mid and (j > hi or nums[i] <= nums[j]):
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1
        k += 1

    nums[lo: hi + 1] = tmp[:k]

def merge_sort(nums: List[int], tmp: List[int], lo: int, hi: int) -> None:
    if lo < hi:
        mid = lo + ((hi - lo) >> 1)

        merge_sort(nums, tmp, lo, mid)
        merge_sort(nums, tmp, mid + 1, hi)

        merge(nums, tmp, lo, mid, 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


void merge(vector<int> &nums, vector<int> &tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = 0;

    while (i <= mid || j <= hi) {
        if (i <= mid && (j > hi || nums[i] <= nums[j])) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }

    copy(tmp.begin(), tmp.begin() + k, nums.begin() + lo);
}

void merge_sort(vector<int> &nums, vector<int> &tmp, int lo, int hi) {
    if (lo < hi) {
        int mid = lo + ((hi - lo) >> 1);

        merge_sort(nums, tmp, lo, mid);
        merge_sort(nums, tmp, mid + 1, hi);

        merge(nums, tmp, lo, mid, hi);
    }
}

基数排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


def radix_sort(nums: List[int]) -> None:
    n = len(nums)
    output = [0] * n
    max_val = max(nums)
    exp = 1

    while max_val // exp:
        count = [0] * 10
        for x in nums:
            count[(x // exp) % 10] += 1
        for i in range(1, 10):
            count[i] += count[i - 1]

        for x in reversed(nums):
            count[(x // exp) % 10] -= 1
            output[count[(x // exp) % 10]] = x

        nums[:] = output

        exp *= 10

 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


void radix_sort(vector<int> &nums) {
    int n = nums.size();
    vector<int> output(n);
    int max_val = *max_element(nums.begin(), nums.end());
    int exp = 1;

    while (max_val / exp) {
        vector<int> count(10);

        for (const int &x : nums) {
            count[(x / exp) % 10] += 1;
        }

        for (int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; --i) {
            output[--count[(nums[i] / exp) % 10]] = nums[i];
        }

        copy(output.begin(), output.end(), nums.begin());

        exp *= 10;
    }
}