袋熊的树洞

日拱一卒，功不唐捐

0%

常用排序算法总结

Posted on Edited on

在介绍排序算法之前，先约定数组表示为 $A$，大小为 $N$，数组下标从 $0$ 开始，排序的数组是从小到大排列

插入排序

在数组是反序的情况下，时间复杂度为 $O(N^2)$，在数组已排序的情况下，时间复杂度为 $O(N)$

1
2
3
4
5
6
7
8
9
10
11
void insertion_sort(int *nums, int n)
{
    int p, tmp;
    for (int i=1; i<n; i++)
    {
        tmp = nums[i];
        for (p=i; p > 0 && nums[p-1] > tmp; p--)
            nums[p] = nums[p-1];
        nums[p] = tmp;
    }
}

归并排序

时间复杂度为 $O(NlogN)$

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
void merge(int *nums, int *tmp, int left_start, int right_start, int right_end)
{
    int left_pos, right_pos, pos;

    left_pos = left_start;
    right_pos = right_start;
    pos = left_start;
    while (left_pos < right_start && right_pos <= right_end) {
        if (nums[left_pos] <= nums[right_pos])
            tmp[pos++] = nums[left_pos++];
        else
            tmp[pos++] = nums[right_pos++];
    }

    while (left_pos < right_start) {
        tmp[pos++] = nums[left_pos++];
    }
    while (right_pos <= right_end) {
        tmp[pos++] = nums[right_pos++];
    }

    // copy array tmp back to array nums
    for (int i=left_start; i<=right_end; i++)
        nums[i] = tmp[i];
}

void msort(int *nums, int *tmp, int left, int right)
{
    if (left < right)
    {
        int center = (left + right) / 2;
        msort(nums, tmp, left, center);
        msort(nums, tmp, center+1, right);
        merge(nums, tmp, left, center+1, right);
    }
}

void merge_sort(int *nums, int n)
{
    int *tmp = new int[n];
    msort(nums, tmp, 0, n-1);
    delete[] tmp;
}

快速排序

平均时间复杂度为 $O(NlogN)$，最坏的情形下，时间复杂度为 $O(N^2)$

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
int partition(int *nums, int left, int right)
{
    int i = left - 1;
    int tmp;
    int pivot = nums[right];

    for (int j=left; j<=right-1; j++) {
        if (nums[j] <= pivot) {
            i = i + 1;

            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

    i = i + 1;
    tmp = nums[i];
    nums[i] = pivot;
    nums[right] = tmp;

    return i;
}

void qsort(int *nums, int left, int right)
{
    if (left < right) {
        int p = partition(nums, left, right);
        qsort(nums, left, p-1);
        qsort(nums, p+1, right);
    }
}

void quick_sort(int *nums, int n)
{
    qsort(nums, 0, n-1);
}