排序算法

CreateTime 2019-04-25
UpdateTime 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;
}

原地归并排序

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

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

参考资料