首页 教程算法正文

跟WilliamYan一起学算法 -- 排序算法

排序

欢迎来到《跟WilliamYan一起学算法》!今天我们来学习排序算法。

排序算法是编程学习中基础的一环,在日后的学习中经常会用到。

其实对于大部分使用c++的人来说,c++ STL 中的sort()函数已经很好用了,但是我仍然认为大家需要了解一下排序的底层原理和实现。

那么就让我们开始吧!


另:本文排版更好的版本可见 小组总站


相关概念

  • 平均时间复杂度

  • 最坏时间复杂度

  • 空间复杂度

  • 稳定性

    • 对于相等元素,排序后相对关系是否改变

  • 排序方式

    • In-place:占用常数内存,不占用额外内存

    • Out-place:占用额外内存

常见的排序算法

分类

[^算法分类]: 1-7 基于比较  8-10 不基于比较


冒泡排序

[^冒泡排序]: 冒泡排序(Bubble sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

冒泡排序是一种稳定的排序算法

动图演示

冒泡排序演示

时间复杂度 $O(n^2)$

空间复杂度 $O(1)$

代码

void BubbleSort(int arr[], int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

选择排序

[^选择排序]: 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

选择排序是一种不稳定的排序算法

动图演示

选择排序演示

时间复杂度 $O(n^2)$

空间复杂度 $ O(1)$

代码

void SelectSort(int arr[], int len)
{
    int i = 0, j = 0, k = 0;
    for (i = 0; i < len - 1; i++)
    {
        k = i;
        for (j = i + 1; j < len; j++)
        {
            if (arr[k] > arr[j])
            {
                k = j;
            }
        }
        if (k != i)
        {
            int tmp = arr[k];
            arr[k] = arr[i];
            arr[i] = tmp;
        }
    }
}

插入排序

[^插入排序]: 插入排序(Insertion sort)是一种简单直观且稳定的排序算法。它的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。

插入排序是一种不稳定的排序算法

动图演示

插入排序演示

时间复杂度 $O(n^2)$

空间复杂度 $ O(1)$

代码

void InsertSort(int arr[], int len)
{
    for (int j = 1; j < len; j++)
    {
        int key = arr[j];
        int i = j - 1; 
        while (i >= 0 && key < arr[i])
        {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = key;
    }
}

归并排序

[^归并排序]: 归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

归并排序是一种稳定的排序算法

动图演示

归并排序演示

时间复杂度 $O(n\times \log_{2}n)$

空间复杂度 $ O(n)$

代码

#ifndef MAXN
#define MAXN 10000000
#endif

int tmp[MAXN];
void MergeSort(int arr[],int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    MergeSort(arr,l,mid); MergeSort(arr,mid+1,r);
    int i=l,j=mid+1;
    for(int k=l;k<=r;k++) tmp[k]=(j>r||(i<=mid&&arr[i]<arr[j]))?arr[i++]:arr[j++];
    for(int k=l;k<=r;k++) arr[k]=tmp[k];
}

#ifdef MAXN
#undef MAXN
#endif

快速排序

快速排序是一种不稳定的排序算法

动图演示

快速排序演示

时间复杂度 $O(n\times \log_{2}n)$

空间复杂度 $ O(\log_{2}n)$

代码

public static void QuickSort(int[] arr,int l,int r){
    int i,j,temp,t;
    if(l>r){
        return;
    }
    i=l;
    j=r;
    temp = arr[l];
    while (i<j) {
        while (temp<=arr[j]&&i<j) {
            j--;
        }
        while (temp>=arr[i]&&i<j) {
            i++;
        }
        if (i<j) {
            t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
        }

    }
     arr[l] = arr[i];
     arr[i] = temp;
    QuickSort(arr, l, j-1);
    QuickSort(arr, j+1, r);
}//此为java代码,c++代码类似

在线试题见洛谷P1177


计数排序

[^计数排序]: 计数排序(Counting sort)亦称桶排序,是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

桶排序是一种稳定的排序算法

动图演示

桶排序演示

时间复杂度 $O(n+k)$

空间复杂度 $ O(n+k)$

代码

void BucketSort(int arr[], int len, int maxnum)
{
    int i, j;
    int *buckets = new int[maxnum+10];

    for (int i = 0; i < maxnum; i++)
        buckets[i] = 0;

    for (i = 0; i < len; i++)
        buckets[arr[i]]++;

    for (i = 0, j = 0; i < maxnum; i++)
    {
        while ((buckets[i]--) > 0)
            arr[j++] = i;
    }
}

基数排序

[^基数排序]: 基数排序(Radix sort)是通过值的部份信息,将要排序的元素分配至某些”桶”中,以达到排序的作用,

基数排序是一种稳定的排序算法

动图演示

基数排序演示

时间复杂度 $O(n \times k)$

空间复杂度 $ O(n+k)$

代码

int getDigit(int i, int d)
{
    int val;
    while (d--)
    {
        val = i % 10;
        i /= 10;
    }
    return val;
}

void RadixSort(int arr[], int l, int r, int digit)
{
    int radix = 10;
    int i = 0, j = 0;
    int *count = new int[radix];
    int *bucket = new int[r - l + 1];

    for (int d = 1; d <= digit; d++)
    {
        for (i = 0; i < radix; i++)
            count[i] = 0;

        for (i = l; i <= r; i++)
        {
            j = getDigit(arr[i], d);
            count[j]++;
        }

        for (i = 1; i < radix; i++)
            count[i] = count[i] + count[i - 1];

        for (i = r; i >= l; i--)
        {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }

        for (i = l, j = 0; i <= r; i++, j++)
            arr[i] = bucket[j];
    }
}

排序的稳定性

若$arr[i]==arr[j],i<j$,排序后$arr[i]$仍在$arr[j]$前方,则认为该排序算法稳定

对于不稳定排序算法,可以通过「第二关键字」使其变得稳定。

逆序对

定义

对于序列$A$ ,满足 $i < j , A_i > A_j$ 的一对 $\left( A_i,A_j \right)$ 被称作逆序对

逆序对数 = 排成升序所需最少相邻交换次数 = 排成升序的冒泡排序交换次数

求逆序对数量

直接枚举

int countInversion(int arr[], int len)
{
    int count = 0;
    int i, j;
    for (i = 0; i < len; i++)
        for (j = i + 1; j < len; j++)
            if (arr[i] > arr[j])
                count++;
    return count;
}

利用归并排序法

#ifndef MAXN
#define MAXN 10000000
#endif

int v[MAXN];
int merge_countInversion(int arr[], int l, int r)
{
    if (l == r)
        return 0;
    int mid = (l + r) >> 1;
    int ans = merge_countInversion(arr, l, mid) + merge_countInversion(arr, mid + 1, r);
    int p = l, j = l, k = mid + 1;
    while (j <= mid && k <= r)
    {
        if (arr[j] > arr[k])
        {
            ans += mid - j + 1;
            v[p++] = arr[k++];
        }
        else
            v[p++] = arr[j++];
    }
    while (j <= mid)
        v[p++] = arr[j++];
    while (k <= r)
        v[p++] = arr[k++];
    for (int i = l; i <= r; i++)
        arr[i] = v[i];
    return ans;
}

#ifdef MAXN
#undef MAXN
#endif

总结

排序算法是为了让无序的数据组合变成有序的数据组合。

有序的数据组合最大的优势是,如果序列是有序的,当你进行数据定位时会非常简单。从而在代码设计时避免很多不必要的麻烦,因为无序数据在进行推断数据前后关系的时候会非常繁琐。

在NOIP初赛的时候,会考到很多有关排序的内容,因此这部分也是需要牢记的。

©2019 William Yan

=[本笔记动图来源]: https://visualgo.net    “数据结构和算法动态可视化”

评论