排序算法

创建时间 2019-04-25
更新时间 2022-05-31
分类
计算机科学
标签
数据结构

概述

排序的过程，实际上是减少逆序数的过程。

排序算法稳定性：假设待排序的序列中，存在相同的关键字，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的时间复杂度为 O(n^2)，冒泡排序是稳定的。

冒泡排序算法的结束条件：如果一趟排序中没有发生元素交换，那么就可以结束。

以下为相关 C++ 代码：

void bubble_sort(int array[], int begin, int end)
{
    auto temp = 0;
    for (int i = begin; i <= end; i++)
    {
        auto flag = false;
        for (int j = begin + 1; j <= end - i; j++)
        {
            if (array[j - 1] > array[j])
            {
                flag = true;
                temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
        }
        if (!flag)
            return;
    }
}

鸡尾酒排序

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

以下为相关 C++ 代码：

void cocktail_sort(int array[], int begin, int end)
{
    auto left = begin;
    auto right = end;

    while (left < right)
    {
        auto flag = false;
        for (auto i = left; i < right; i++)
        {
            if (array[i] > array[i + 1])
            {
                flag = true;
                auto temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
        right--;

        if (!flag)
            return;

        flag = false;
        for (auto i = right; i > left; i--)
        {
            if (array[i] < array[i - 1])
            {
                flag = true;
                auto temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
            }
        }
        left++;

        if (!flag)
            return;
    }
}

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的交换操作介于 0 和 (n-1) 次之间。选择排序的比较操作为\frac{n(n-1)}{2}次。选择排序的赋值操作介于 3(n-1) 次之间。

比较次数 O(n^{2})，比较次数与关键字的初始状态无关，总的比较次数 N=(n-1)+(n-2)+...+1=n\times (n-1)/2。交换次数 O(n)，最好情况是，已经有序，交换 0 次；最坏情况是，逆序，交换 n-1 次。交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。

以下为相关 C++ 代码：

void select_sort(int array[], int begin, int end)
{
    auto left = begin;
    auto right = end;
    auto max_index = begin;
    for (auto i = end; i >= begin; i--)
    {
        max_index = begin;
        for (auto j = begin + 1; j <= i; j++)
        {
            if (array[j] > array[max_index])
                max_index = j;
        }
        auto temp = array[max_index];
        array[max_index] = array[i];
        array[i] = temp;
    }
}

堆排序

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

  • 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
  • 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆节点的访问

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

  • 父节点i的左子节点在位置 2i+1;
  • 父节点i的右子节点在位置 2i+2;
  • 子节点i的父节点在位置 \lfloor (i-1)/2 \rfloor;

以下为相关 C++ 代码：

void adjust_heap(int array[], int begin, int end)
{
    auto dad = begin;
    auto son = dad * 2 + 1;

    while (son <= end)
    {
        if (son + 1 <= end && array[son] < array[son + 1])
            son++;
        if (array[son] < array[dad])
            return;

        auto temp = array[dad];
        array[dad] = array[son];
        array[son] = temp;

        dad = son;
        son = dad * 2 + 1;
    }
}

void heap_sort(int array[], int begin, int end)
{
    for (auto i = (end - begin + 1) / 2 - 1; i >= 0; i--)
        adjust_heap(array, i, end);

    for (auto i = end; i > begin; --i)
    {   
        auto temp = array[i];
        array[i] = array[begin];
        array[begin] = temp;
        adjust_heap(array, begin, i - 1);
    }
}

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到\displaystyle O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

以下为相关 C++ 代码：

void insert_sort(int array[], int begin, int end)
{
    for (int i = begin + 1; i <= end; i++)
    {
        auto key = array[i];
        auto j = i - 1;
        for (; j >= begin; j--)
        {
            if (array[j] <= key)
                break;
            array[j + 1] = array[j];
        }
        array[j + 1] = key;
    }
}

希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个记录恰被分成一组，算法便终止。

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。

以下为相关 C++ 代码：

void shell_sort(int array[], int begin, int end)
{
    for (int gap = (end - begin) / 2; gap > 0; gap /= 2)
    {
        for (int i = begin + gap; i <= end; i++)
        {
            auto key = array[i];
            auto j = i - gap;
            for (; j >= begin; j -= gap)
            {
                if (array[j] <= key)
                    break;
                array[j + gap] = array[j];
            }
            array[j + gap] = key;
        }
    }
}

快速排序

快速排序（Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n个项目要O(n\log n)次比较。在最坏状况下则需要O(n^{2})次比较，但这种状况并不常见。事实上，快速排序\Theta (n\log n)通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

以下为相关 C++ 代码：

void quick_sort(int array[], int begin, int end)
{
    if (begin >= end) return;
    auto pivot = array[begin];

    auto left = begin;
    auto right = end;

    while (left < right) {
        while (left < right && array[right] >= pivot) {
            right --;
        }
        array[left] = array[right];

        while (left < right && array[left] < pivot) {
            left ++;
        }
        array[right] = array[left];
    }
    array[left] = pivot;
    quick_sort(array, begin, left - 1);
    quick_sort(array, left + 1, end);
}

随机快速排序

考虑到快速排序在列表已经有序或者大部分有序的情况下，效率接近于 O(n^2)，所以可以使用随机选取主元的方式来解决这个问题，因为以上快速排序选择区间中的第一个元素作为主元，那么只需要从区间中随机选取一个主元，与第一个元素交换即可。这样的话，由于主元是随机的，绝大多数情况下，不会出现最差的情况，也就是每次随机都取到第一个元素。

以下为相关 C++ 代码：

void random_quick_sort(int array[], int begin, int end)
{
    if (begin >= end) return;

    std::default_random_engine engine(time(nullptr));
    std::uniform_int_distribution<> dis(begin, end);

    auto index = dis(engine);
    auto pivot = array[index];

    auto left = begin;
    auto right = end;

    while (left < right) {
        while (left < right && array[right] >= pivot) {
            right --;
        }
        array[left] = array[right];

        while (left < right && array[left] < pivot) {
            left ++;
        }
        array[right] = array[left];
    }
    array[left] = pivot;
    random_quick_sort(array, begin, left - 1);
    random_quick_sort(array, left + 1, end);
}

归并排序

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n\log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

递归法（Top-down）

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

迭代法（Bottom-up）

原理如下（假设序列共有 n个元素）：

  • 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含 1 ~ 2 个元素
  • 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含 3 ~ 4 个元素
  • 重复步骤2，直到所有元素排序完毕，即序列数为1

递归形式的代码：

void merge_sort_recursive(int array[], int begin, int end)
{
    if (begin >= end)
        return;
    auto length = end - begin + 1;
    auto mid = (end - begin) / 2 + begin;

    merge_sort_recursive(array, begin, mid);
    merge_sort_recursive(array, mid + 1, end);

    auto list = new int[length];
    std::copy(array + begin, array + end + 1, list);

    auto begin1 = 0;
    auto end1 = mid - begin;
    auto begin2 = end1 + 1;
    auto end2 = length - 1;

    int index = begin;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (list[begin1] < list[begin2])
        {
            array[index++] = list[begin1++];
        }
        else
        {
            array[index++] = list[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        array[index++] = list[begin1++];
    }
    while (begin2 <= end2)
    {
        array[index++] = list[begin2++];
    }
    delete[] list;
}

非递归形式的代码：

void merge_sort_iterate(int array[], int begin, int end)
{
    if (begin >= end)
        return;

    auto source = array;
    auto length = end - begin + 1;

    array = new int[length];
    auto list = source;

    for (auto segment = 1; segment < length; segment *= 2)
    {
        for (auto i = begin; i <= end; i += segment * 2)
        {
            auto begin1 = i;
            auto begin2 = i + segment;
            auto end1 = begin2 - 1;
            auto end2 = end1 + segment;
            int index = begin1;

            while (begin1 <= end1 && begin2 <= end2)
            {
                if (list[begin1] < list[begin2])
                {
                    array[index++] = list[begin1++];
                }
                else
                {
                    array[index++] = list[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                array[index++] = list[begin1++];
            }
            while (begin2 <= end2)
            {
                array[index++] = list[begin2++];
            }
        }
        auto temp = array;
        array = list;
        list = temp;
    }
    if (array != source){
        std::copy(list + begin, list + end + 1, source);
        list = array;
    }
    delete[] list;
}

原地归并排序

前面得归并排序，在归并之前要将数组中得数据拷贝到另一个相同大小得数组。然后再通过比较，将排序好的数据写入原数组。也就是说在排序过程中需要额外的空间来存储数据。如果数据量过大，那么这个算法实际上很难奏效。

原地归并排序，是通过 手摇算法 来进行归并，这样就不需要额外的空间来存储整个数组了。不过手摇算法需要大量的交换产生，造成了一些性能消耗。

参考资料