基础排序算法

基础排序算法

1 基本知识

1.1 排序的定义

排序是计算机内经常进行的一种操作,其目的是将一组无序的记录序列调整为“有序”的记录序列某些题目的做法经常与排序有关

1.2 朴素做法-选择排序

最简单的思路就是执行这样的操作:每次从数组中找最大的那个数然后输出该值。怎么实现呢,请看代码。

  • 例1.2.1(有缺陷)
for (int i=0;i<n;i++)
{
    int minn=INT_MAX,min_i;    //INT_MAX是一个宏,代表int类型最大值
    for (int j=0;j<n;j++)
    {
        if (array[j]<minn)
        {
                minn=array[j];
                min_i=j;
        }
    }
    cout<<array[min_i]<<' ';
    array[min_i]=INT_MAX;
}

上述代码有什么缺陷😕?

  1. 此方法仅适合排序之后立即输出内容,如果需要操作排序之后的内容,需要额外开一个空间。
  2. 排序完成总共需要n*n次操作。
  3. 操作稍微复杂了些(常数大)。

于是我们需要一个更简单点的操作:每次操作将当前下标元素与其后面的元素比较如果后面元素比它大就交换两个元素

  • 例1.2.2
for (int i=0;i<n-1;i++)
    for (int j=i+1;j<n;j++)
        if (array[j]<array[i]) swap(array[i],array[j]);    //交换

这样改进后,每次操作结束后当前下标元素,操作减少到了$n \times (n+1) / 2$次,并且不需要额外的内存空间。这样的排序方法,称为选择排序

选择排序

1.3 冒泡排序

由选择排序的比较思想延伸,我们可以这样对一个数组操作:对一个数组进行遍历每次比较当前数与后面的一个数前数大于后数就交换它们。这样最大的数就会在数组的最后一个位置。操作n-1遍便可以完成排序,请看代码。

  • 例1.3.1
for (int i=n-1;i;i--)
    for (int j=0;j<i;j++)
        if (array[j]>array[j+1]) swap(array[j],array[j+1]);    //交换

越小的元素会经由交换慢慢“浮”到数列的顶端,因此这样的排序方法就叫冒泡排序

冒泡排序

1.4 插入排序

在打斗地主的时候,我们需要把自己的牌进行排序。牌是一张一张摸来的,我们只需要保证牌一直都是有序的就可以了,这样的排序方法叫做插入排序

具体操作:

  1. 开一个额外的数组temp(保持目前有序的数组)。
  2. 遍历数组,对每个元素x进行操作:
  3. 在temp中找到第一个大于x的位置p。
  4. 把temp数组从p开始的元素全部后移一位。
  5. 最后temp[p]=x。
  6. 最后排序结果即为temp。

请看代码。

  • 例1.4.1
int cnt=0;    //记录temp数组中元素的个数
for (int i=0;i<n;i++)
{
    int p,x=array[i];
    for (p=0;p<cnt;p++)
        if (temp[p]>x) break;
    for (int j=cnt-1;j>=p;j--)    //避免数据丢失
        temp[j+1]=temp[j];
    temp[p]=x;
    cnt++;
}

这个算法非常的不错,在移动时选择了从后往前将每个元素向后移动,避免了移动造成后面一个元素的数据丢失。

插入排序

1.5 三个排序方法的时间复杂度和空间复杂度

  • 选择排序:时间$O(n^2)$,空间$O(1)$。
  • 冒泡排序: 时间$O(n^2)$,空间$O(1)$。
  • 插入排序:时间$O(n^2)$,空间$O(n)$或$O(1)$(请自行实现)。

上述三个排序并称为简单排序

1.6 归并排序

归并排序是基于分治思想的排序。

具体操作

  1. 调用函数mergesort(l,r)。(对数组下标l-r的元素排序
  2. 当l<r时,l-r的元素分为两半l-mid,mid+1-r。
  3. 调用函数mergesort(l,mid+1),mergesort(mid+1,l)。
  4. 将两个排好序的数组合并,覆盖l-r的元素。

为何上述操作中没有明显的排序操作但是还是能排序😕?

这是因为当数组的长度为1时,这个数组一定有序。如何完成合并数组的操作😕?

我们需要借助一个额外的数组p,从两个已经排好序的数组中一个一个取元素放到数组p,然后再将数组p的数据放到原数组中,请看代码。

  • 例1.6.1
void mergesort(int l,int r)
{
    if (l>=r) return;    //空区间或者只有一个元素的区间

    int mid=(l+r)/2;
    mergesort(l,mid); 
    mergesort(mid+1,r);

    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r)
    {
        if (array[i]<array[j]) p[k++]=array[i++];
        else p[k++]=array[j++];
    }

    while (i<=mid) p[k++]=array[i++];
    while (j<=r) p[k++]=array[j++];

    for (int i=l;i<=r;i++)
            array[i]=p[i];
}
//注:输入数据时,从下标1开始输入。

归并排序的时间复杂度稳定为$O(nlogn)$,空间复杂度为$O(n)$。

归并排序

1.7 快速排序

假设你正在使一群人由身高低到高的顺序排序,你可以这样操作

  1. 随机选一个人。
  2. 比他矮的人到他左边,比他高的人到他右边。
  3. 对他左边,右边的人重复所有操作。

这样的排序方法称为快速排序。可以明显看出,操作2是整个方法的核心。请看代码来理解。

  • 例1.7.1(有缺陷)
int t[maxn];    //临时数组
void quicksort(int l,int r)
{
    if (l>=r) return;    //空区间或者只有一个元素的区间

    int flag=array[l];
    int p=l,q=r;

    for (int i=l;i<=r;i++)
    {
        if (array[i]<flag) t[p++]=array[i];
        if (array[i]>flag) t[q--]=array[i];
    }

    //现在,[l,p-1]全是比flag小的,[q+1,r]全是比flag大的

    for (int i=l;i<=p-1;i++)
        array[i]=t[i];
    for (int i=p;i<=q;i++)    //与flag值相同的元素
        array[i]=flag;
    for (int i=q+1;i<=r;i++)
        array[i]=t[i];

    quicksort(l,p-1); 
    quicksort(q+1,r);
}

整个程序运行的非常不错,为什么标着有缺陷😕?

可以这样假设有这样的一个数组[1 2 3 4 5 6 7 8],进行操作:

  1. 操作后1 [2 3 4 5 6 7 8]。
  2. 再操作后1 2 [3 4 5 6 7 8]。
  3. 可以发现每次操作只排出了一个元素,差不多是$O(n^2)$的时间复杂度,更吓人的是,这个数组就是已经排好序了的!

问题出现在flag,因为flag的值是固定的。那么怎么选择flag的值😕?

选择数组中间的值?❌也不完全对,特殊的数据同样会让你的时间复杂度到达$O(n^2)$。正确的做法是取随机数。

int flag=array[rand()%(r-l+1)+l];    //rand%(r-l+1)+l表示随机取[l,r]的一个数

如果每次都能取到数组中位数,排序算法的时间复杂度为$O(nlogn)$,随机取flag,时间复杂度是有保证的,平均时间复杂度为$O(nlogn)$。

在实践上,快速排序是最快的排序方法,因此得名。快速排序的空间复杂度为$O(n)$或者$O(1)$(请自行实现)

快速排序

1.8 C++STL sort

C++的algorithm库提供了sort函数,sort函数实际上是一个混合使用排序的函数,根据数据规模来确定一个最快的排序方法。

如何使用sort函数?现在有一个数组a,从下标0开始存了n个数据,则应如下使用:

sort(a,a+n);

可以看出使用方法应为sort(排序起始地址,排序结束地址的后一个地址),你也可以想象成是一个左闭右开区间。

sort可以对各种类型的数组或者C++STL容器进行排序,前提是这些数据类型定义了<运算符。如果没有,可以写一个cmp函数作为sort函数的第三个参数或者在结构体内重载运算符。

1.9 基于比较的排序方法

上述的排序方法都是基于比较的排序方法基于比较的排序方法最快只能达到$O(nlogn)$的时间复杂度

下面介绍一个不基于比较的排序方法。

1.10 计数排序

计数排序是一种非比较排序 所以它的速度要比上述的排序快非常多,但它的缺点是比较占内存。

思路:

  1. 创建一个大小为待排数组最大数的一个数组。
  2. 将待排数组的数据作为刚刚创建的数组的下标,并把相应下标的元素加一,这样将待排数组遍历一便就会将数据和个数都记录在我们创建的数组里,接下来只要将创建的数组遍历一遍,将数据非零的元素的下标输出就可以了。
int sz[maxn];    //maxn的大小为待排数组最大数+1
for (int i=0;i<n;i++)    //待排序数组大小为n
    sz[arr[i]]++;
for (int i=0;i<maxn;i++)
{
    if (sz[i])
        for (int j=0;j<sz[i];j++)
            cout<<i<<endl;
}

计数排序的时间复杂度均为$O(n+maxn)$。

计数排序


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。