各种排序(一)

2019-12-07 16:00:36来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

各种排序(一)

$\Lager\text{各种排序(一)}$

  • 本文中 $n$ 代表着待排序序列的长度。
  • 算法是否稳定:若 $a_i = a_j ?, ?i < j$,排序后若$i < j$ 则稳定,反之不稳定。(可能有点歧义凑活看)

冒泡排序

又叫气泡排序,起泡排序,泡沫排序
这应该是最简单的排序算法了吧。

时间复杂度:$O(n ^ 2)$
算法是否稳定:是

在未排好序之前一直扫描序列,每次将最大数的放到序列的最后,所以最多 $n-1$ 次扫描后序列就排好序了。

for(int i=1;i<n;++i) {//n-1轮扫描
    bool okay=true;
    for(int j=1;j<=n-i;++j) {//[n-i+2,n]都已经排好序了。
        if(a[j]>a[j+1]) {
            swap(a[j],a[j+1]);
            okay=false;
        }
    }
    if(okay==true) break;
}

上几张动图,帮助理解。

鸡尾酒排序

冒泡排序的一种优化,在一些特殊情况下有用。

时间复杂度:$O(n ^ 2)$
算法是否稳定:是

有两种操作:

  • 将序列中最大的数放到最后
  • 将序列中最小的数放到最前

在未排好序之前将上面两种操作交替进行。

int left=1,right=n;//[left,right]需要排序。
while(left<right) {//最多进行到left=right就停止
    bool okay=true;
    for(int i=left;i<right;++i) {//将序列中最大的数放到最后
        if(a[i]>a[i+1]) {
            swap(a[i],a[i+1]);
            okay=false;
        }
    }
    if(okay==true) break;
    --right;//[right+1,n]已经排好序了
    for(int i=right;i>left;--i) {
        if(a[i]<a[i-1]) {
            swap(a[i],a[i-1]);
            okay=false;
        }
    }
    ++left;//[1,left-1]已经排好序了
    if(okay==true) break;
}

选择排序

在未排好序之前一直扫描序列,每次将最小数的放到序列的最前,所以最多 $n-1$ 次扫描后序列就排好序了。

时间复杂度:$O(n ^ 2)$
算法是否稳定:否

与冒泡排序的不同:冒泡排序每扫一次序列会进行多次交换,将不符合顺序的都交换。选择排序每扫一次序列只会进行一次交换,将最小的元素与最前的元素交换。

for(int i=1;i<n;++i) {//最多扫n-1次
    bool okay=true;
    int minn=0x7fffffff,flag;
    for(int j=i;j<=n;++j) {
        if(a[j]<minn) {
            minn=a[j];flag=j;//找最小的并记录下位置。
            okay=false;
        }
    }
    if(okay==true) break;
    std::swap(a[i],a[flag]);//将最小的元素与最前的元素交换
}

放张图理解一下

{5,8,5,2,9},可知选择排序不稳定。

插入排序

流程就像是打牌的摸牌阶段。

操作将一个数插入到一个排好序的序列中时期仍然排好序即可。

时间复杂度:$O(n ^ 2)$
算法是否稳定:是

for(int i=2;i<=n;++i) {//[1,i-1]已经排好了序
    int temp=a[i],j=i-1;
    while(j>0&&a[j]>temp) {//将第i张牌插入其中
        a[j+1]=a[j];
        j--;
    }
    a[j+1]=temp;
}

上张动图理解一下

二分插入排序

在插入排序的基础上使用二分查找来确定当前数应该插入到哪里。
这是优化吗?我为什么感觉比插入排序还慢。

时间复杂度:$O(n(log n + n))$
算法是否稳定:是否

for(int i=2;i<=n;++i) {
    int left=1,right=i-1,temp=a[i];
    while(left<=right) {//二分查找当前数插入到哪里
        int mid=(left+right)>>1;
        if(a[mid]>temp) right=mid-1;
        else left=mid+1;
    }
    for(int j=i-1;j>=left;--j) a[j+1]=a[j];
    a[left]=temp;//插进去
}

对于if(a[mid]>temp) right=mid-1;

  • 如果加了等号的话,不稳定排序
  • 如果不加等号的话,是稳定排序

原文链接:https://www.cnblogs.com/poi-bolg-poi/p/12001054.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:lower_bound()和upper_bound()

下一篇:北华大学网络赛题