关于排序算法
2021-05-01 13:07:26 #数据结构与算法  #数据结构与算法  #CPP 

插入排序

直接插入排序

从小到达排列，在第p趟，将位置p上的元素f(p)与它之前的元素进行比较，f(p)小则将之前的元素向后移动一位，直到找到合适的位置并插入

1
2
3
4
5
6
7
8
9
10
11
template<typename Object>
void
insertionSort(std::vector<Object> &x) {
    for (int p = 1; p < x.size(); ++p) {
        Object tmp = std::move(x[p]);
        int j;
        for (j = p; j > 0 && tmp < x[j - 1]; --j)
            x[j] = std::move(x[j - 1]);
        x[j] = std::move(tmp);
    }
}

STL 中的插入排序

针对排序对象不是简单的整数，而是自定义的对象，因此需要特定的比较函数；同时一般用迭代器处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename Iterator, typename Comparator>
void
insertSort(const Iterator &begin, const Iterator &end, Comparator lessThan) {
    if (begin == end)
        return;

    Iterator j;

    for (Iterator p = begin + 1; p != end; ++p) {
        auto tmp = std::move(*p);
        for (j = p; j != begin && lessThan(tmp, *(j - 1)); --j)
            *j = std::move(*(j - 1));
        *j = std::move(tmp);
    }
}

性能分析：

时间复杂度：

希尔排序

按照序列的下标，设置增量，根据增量对序列做增量分组，对每组使用直接插入排序；缩小增量重新做增量分组，使用直接插入排序；重复进行

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename Object>
void
shellSort(std::vector<Object> &x) {
    for (int gap = x.size() / 2; gap > 0; gap /= 2)
        for (int i = gap; i < x.size(); ++i) {
            Object tmp = std::move(x[i]);
            int j = i;

            for (; j >= gap && tmp < x[j - gap]; j -= gap)
                x[j] = std::move(x[j - gap]);
            x[j] = std::move(tmp);
        }
}

性能分析：

最坏情况：

使用 Hibbard 增量优化后：

选择排序

选择排序

每n趟在待排序元素中选取关键字最小的元素，并于序列中第n-1个元素互换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename Object>
void
selectSort(std::vector<Object> &x) {
    for (int i = 0; i < x.size() - 1; ++i) {
        int select = i;
        for (int j = i + 1; j < x.size(); ++j)
            if (x[j] < x[select])
                select = j;

        if (select != i)
            std::swap(x[select], x[i]);
    }
}

性能分析：

空间复杂度：

时间复杂度：

堆排序

每一趟在待排序元素中选取关键字最小/最大的元素加入有序子序列

通过优先队列实现

通过构建一个小根堆，将待排序队列的元素依次插入小根堆中，根结点是最小的元素，且每次deleteMin后，会自动调整小根堆，将现存的最小元素放入根结点

性能分析：

时间复杂度：

空间：为了构建这样的优先队列，成员函数array的大小是略大于待排序数组的

交换排序

冒泡排序

重复走访需要排序的序列，按照升序交换相邻两个元素的位置，重复直至没有需要再交换的元素

1
2
3
4
5
6
7
8
template<typename Object>
void
BubbleSort(std::vector<Object> &x) {
    for (int i = 0; i < x.size() - 1; ++i)
        for (int j = 0; j < x.size() - 1 - i; ++j)
            if (x[j] > x[j + 1])
                std::swap(x[j], x[j + 1]);
}

性能分析：

时间复杂度：

快速排序

对待排序序列任意选取一项，则有小于所选项的一组、等于所选项的一组和大于所选项的一组；递归的将第一组和第三组排序，将这三组连接起来

  1. 如果序列中元素个数是 1 或 0，则返回
  2. 从序列中挑出一个元素（一般取中心位置的元素），称为枢纽元（pivot）
  3. 重新排序序列，所有元素比枢纽元小的摆放在枢纽元前面，所有元素比枢纽元大的摆在枢纽元的后面（相同的数可以到任一边）。在这个分区退出之后，该枢纽元就处于数列的中间位置。这个称为分区（partition）操作
  4. 递归地（recursive）把小于枢纽元元素的子数列和大于枢纽元值元素的子序列排序

简单的递归排序算法

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
template<typename Object>
void
SORT(std::vector<Object> &items) {
    if (items.size() > 1) {
        std::vector<Object> smaller;
        std::vector<Object> same;
        std::vector<Object> larger;

        auto chosenItem = items[items.size() / 2];

        for (auto i:items) {
            if (i < chosenItem)// 这里可以使用Object的比较函数
                smaller.template emplace_back(std::move(i));
            else if (i > chosenItem)
                larger.template emplace_back(std::move(i));
            else
                same.template emplace_back(std::move(i));
        }
        SORT(smaller);
        SORT(larger);

        std::move(std::begin(smaller), std::end(smaller), std::begin(items));
        std::move(std::begin(same), std::end(same), std::begin(items) + smaller.size());
        std::move(std::begin(larger), std::end(larger), std::end(items) - larger.size());
    }
}

实际的快速排序

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
47
48
49
template<typename Object>
void
quickSort(std::vector<Object> &x) {
    quickSort(x, 0, x.size() - 1);
}

template<typename Object>
const Object &median3(std::vector<Object> &x, int left, int right) {// 三数中值分割法
    int center = (left + right) / 2;

    if (x[center] < x[left])
        std::swap(x[center], x[left]);
    if (x[right] < x[left])
        std::swap(x[right], x[left]);
    if (x[right] < x[center])
        std::move(x[right], x[center]);

    std::swap(x[center], x[right - 1]);
    return x[right - 1];
}

template<typename Object>
void
quickSort(std::vector<Object> &x, int left, int right) {
// 截至范围是10的截至技术
    if (left + 10 <= right) {
        auto pivot = median3(x, left, right);

        int i = left, j = right - 1;
        while (tr) {
            while (x[++i] < pivot) {}// 找出从左开始，大于枢纽元的元素
            // 切记不可写成
            // while (x[i] < pivot) ++i;
            // 如果这样写，当x[i]==pivot==x[j]时
            // 会陷入死循环
            // 下同
            while (x[--j] > pivot) {}// 找出从右开始，小于枢纽源的元素
            if (i < j)
                std::swap(x[i], x[j]);
            else
                break;
        }
        std::swap(x[i], x[right - 1]);

        quickSort(x, left, i - 1);// 将小于等于枢纽元的元素排序
        quickSort(x, i + 1, right);// 将大于等于枢纽元的元素排序
    } else
        insertSort(x, left, right)// 调用插入排序整理子数组
}

归并排序

建立在归并操作上的排序算法，通过合并两个已排序的序列到第三个空白序列来实现

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤 3 直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

自顶向下递归，到底层以后，每个需要比较的序列只有一个元素，取其中较小的元素放入缓存序列后，然后复制另一个序列中的剩余元素，如此自底向上往复

每个需要比较的序列只有一个元素：从逻辑上看如此，实际上通过传参时的下标来标定被排序序列，划分出此阶段需要对比的两个序列

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
47
48
49
template<typename Object>
void
mergeSort(std::vector<Object> &x) {
    std::vector<Object> tmp(x.size());
    mergeSort(x, tmp, 0, x.size() - 1);
}

template<typename Object>
void
mergeSort(std::vector<Object> &x, std::vector<Object> &tmp,
          int left, int right) {
    if (left < right) {
        int center = (left + right) / 2;
        mergeSort(x, tmp, left, center);
        mergeSort(x, tmp, center + 1, right);
        merge(x, tmp, left, center + 1, right);
    }
}

template<typename Object>
void
merge(std::vector<Object> &x, std::vector<Object> &tmp,
      int leftPos, int rightPos, int rightEnd) {
    // 左序列终点
    int leftEnd = rightPos - 1;
    // 缓存序列起点
    int tmpPos = leftPos;
    // 参加排序的元素的总数
    int numElements = rightEnd - leftPos + 1;

    while (leftPos <= leftEnd && rightPos <= rightEnd)
        // 挑选较小的元素放入缓存序列
        if (x[leftPos] <= x[rightPos])
            tmp[tmpPos++] = std::move(x[leftPos++]);
        else
            tmp[tmpPos++] = std::move(x[rightPos++]);

    // 复制左序列的剩余元素
    while (leftPos <= leftEnd)
        tmp[tmpPos++] = std::move(x[leftPos++]);

    // 复制右序列的剩余元素
    while (rightPos <= rightEnd)
        tmp[tmpPos++] = std::move(x[rightPos++]);

    // 转移排序后的元素至原序列中
    for (int i = 0; i < numElements; ++i, --rightEnd)
        x[rightEnd] = std::move(tmp[rightEnd]);
}

性能分析：

时间复杂度：

计数排序

要求：待排序序列的元素必须是具有确定范围的整数

  1. 找出待排序序列中最大和最小元素，计算差值并 +1 得到c
  2. 设置计数序列C，长度为c
  3. 统计待排序序列中每个值为i的元素的个数n，并存入计数序列C的第i个位置
  4. 填充目标数组：将每组n个值为i的元素填充入目标数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void
countingSort(std::vector<int> &x) {
    int min = *std::min_element(x.cbegin(), x.cend());
    int max = *std::max_element(x.cbegin(), x.cend());
    int size = max - min + 1;

    std::vector<int> tmp(size);

    for (int i:x)
        tmp[i - min]++;
        // 数组首元素下标是0，如果待排序序列有负数
        // 需要调整到0

    x.clear();
    for (int i = 0; i < size; ++i) {
        while (tmp[i]--)
            x.emplace_back(i + min);// 将被调整的负数恢复至原样
    }
}

性能分析：

时间复杂度：

桶排序

设置多个桶，利用映射关系，将符合条件的元素放入对应桶中，排序桶中元素和合并桶

尽可能将N个元素均匀分配到K个桶中

计数排序可以看作是每个桶只存储单一元素的桶排序

基数排序

  1. 将元素的数据按照位数切割成不同的数字
  2. 将个位做升序比较，放入对应桶中
  3. 完成后升序取出，放回序列
  4. 按十位做升序比较，放入对应桶中
  5. 完成后升序取出，放回序列
  6. ……

排序算法性能

数据结构性能