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

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

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

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

那么就让我们开始吧!

相关概念

  • 平均时间复杂度
  • 最坏时间复杂度
  • 空间复杂度
  • 稳定性
    • 对于相等元素,排序后相对关系是否改变
  • 排序方式
    • In-place:占用常数内存,不占用额外内存
    • Out-place:占用额外内存

常见的排序算法

《排序算法 —— 跟WilliamYan一起学算法》


冒泡排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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;
            }
        }
    }
}

选择排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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;
        }
    }
}

插入排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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;
    }
}

归并排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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

快速排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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


计数排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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;
    }
}

基数排序

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

动图演示

《排序算法 —— 跟WilliamYan一起学算法》

时间复杂度 $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/zh/sorting "数据结构和算法动态可视化"


点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据