排序算法

warning: 这篇文章距离上次修改已过243天,其中的内容可能已经有所变动。

sort.jpgsort.jpg

【内容简要】

  1. 排序的基本概念
  2. 插入排序:直接插入排序;折半插入排序;希尔排序
  3. 交换排序:冒泡排序;快速排序
  4. 选择排序:简单选择排序;堆排序
  5. 2路归并排序
  6. 基数排序
  7. 外部排序
  8. 各种排序算法的比较
  9. 排序算法的应用

一 、排序的基本概念

根据数据元素是否完全在内存中,可以将排序算法分为两类:

  • 内部排序:排序期间元素全部存放在内存中的排序,包括插入排序,交换排序,选择排序,归并排序,基数排序
  • 外部排序:排序期间元素无法全部同时存放在内存中,必须在内外存之间不断移动的排序,包括多路归并排序

排序算法的稳定性是指经过排序后,能使关键字相同的元素保持原顺序中的相对位置不变

二、插入排序

基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列,直到全部序列插入完成

1.直接插入排序

void InsertSort(int a[],int n)
{
    //将a[0]作为哨兵
    int i,j;
    for(i=2;i<=n;i++)
    {
        if(a[i]<a[i-1])
        {
            a[0]=a[i];
            for(j=i-1;a[0]<a[j];j--)
                a[j+1]=a[j];
            a[j+1]=a[0];
        }
    }
}

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

  • 最好情况:元素已经有序,$O(n)$
  • 最坏情况:元素逆序,$O(n^2)$

空间复杂度:$O(1)$
稳定性:稳定
适用性:适用于顺序存储和链式存储的线性表

2.折半插入排序

要求排序表为顺序表
改进思想:由于是顺序存储的线性表,所以查找有序子表时可以采用折半查找来实现,进而减小比较元素的次数

void InsertSortByHalf(int a[],int n)
{
   int i,j;
   for(i=2;i<=n;i++)
   {
       if(a[i]<a[i-1])
       {
           a[0]=a[i];
           int low=1,high=i-1;//二分查找
           while(low<=high)
           {
               int mid=low+high>>1;
               if(a[mid]>a[0])high=mid-1;
               else low=mid+1;
           }
           for(j=i-1;j>=high+1;j--)
               a[j+1]=a[j];
           a[j+1]=a[0];
       }
   }
}

虽然减小了比较的次数,但是元素的移动次数并未改变,关键字比较次数和初始序列无关,最好的时间复杂度为$O(nlog_2n)$ ,时间复杂度仍为$O(n^2)$,也是稳定的排序

3.希尔排序

基本思想:将待排序表分割为若干形如L[i,i+d,i+2d...,i+kd]的子表,即把相隔某个增量的记录组成一个子表,对各个子表进行直接插入排序,当整个表中的元素基本有序时,再对全体记录进行一次直接插入排序

void ShellSort(int a[],int n)
{
    int i,j;
    for(int d=n/2;d>=1;d=d/2)//步长变化
    {
        for(i=d+1;i<=n;i++)
        {
            if(a[i]<a[i-d])
            {
                a[0]=a[i];
                for(j=i-d;j>0&&a[0]<a[j];j-=d)
                    a[j+d]=a[j];
                a[j+d]=a[0];
            }
        }
    }
}

时间复杂度:$O(n^2)$ ,依赖于增量序列函数

空间复杂度:$O(1)$
稳定性:不稳定
适用性:仅适用于顺序存储的线性表

三、交换排序

根据序列中两个元素关键字的比较结果来对换两个记录在序列中的位置

1.冒泡排序

基本思想:从前向后或从后向前两两比较相邻元素的值,若为逆序,则交换,直到序列比较完,称为一次冒泡,结果将最小或最大的元素交换到序列第一或最后位置,最多进行n-1次冒泡即可排好序

void BubbleSort(int a[],int n)
{
    for(int i=1;i<=n;i++)
    {
        bool flag=false;
        for(int j=n;j>i;j--)
            if(a[j-1]>a[j])
            {
                swap(a[j-1],a[j]);
                flag=true;
            }
        if(!flag)return;//本次遍历没有发生交换,说明已经有序
    }
}

每趟结束都会确定一个元素的最终位置

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

  • 最好情况:元素已经有序,$O(n)$
  • 最坏情况:元素逆序,$O(n^2)$

空间复杂度:$O(1)$
稳定性:稳定
适用性:适用于顺序存储和链式存储的线性表

2.快速排序

基本思想:基于分治,在待排序表中任取一个元素作为枢纽,通过一次排序后,将待排序表分为独立的两个部分,左边部分都比枢纽值小,右边部分大于等于枢纽值,即将此个枢纽值放在了最终的位置上,对每个部分分别递归进行,直至每个部分内只有一个元素或为空为止
所有内部排序算法中平均性能最好的排序算法

int Partition(int a[],int low,int high)//一趟划分
{
    int k=a[low];//选取表中第一个元素作为枢纽值
    while(low<high)
    {
        while(low<high&&k<=a[high])high--;
        a[low]=a[high];
        while(low<high&&k>=a[low])low++;
        a[high]=a[low];
    }
    a[low]=k;
    return low;
}
void QuickSort(int a[],int low,int high)
{
    if(low<high)
    {
        int pos=Partition(a,low,high);
        QuickSort(a,low,pos-1);
        QuickSort(a,pos+1,high);
    }
}

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

  • 最好情况:每次进行最平衡的划分,$O(nlog_2n)$
  • 最坏情况:每次划分极不平衡,即一个部分为n-1,一个部分为0,$O(n^2)$

空间复杂度:$O(log_2n)$
和递归工作栈的深度相关

  • 最好情况:$O(log_2n)$
  • 最坏情况:$O(n)$
    稳定性:不稳定

适用性:适用于顺序存储的线性表

四、选择排序

1.简单选择排序

基本思想:第i趟排序即从排序表L[i...n]中选择关键字最小的的元素与之交换,每一趟可确定一个元素,经过n-1趟就可使得整个顺序表有序,执行次数与初始序列没有关系

void SelectSort(int a[],int n)
{
    int k;
    for(int i=0;i<n-1;i++)
    {
        k=i;
        for(int j=i+1;j<n;j++)
            if(a[j]<a[k])k=j;
        if(k!=i)swap(a[i],a[k]);
    }
}

时间复杂度:$O(n^2)$
空间复杂度:$O(1)$
稳定性:不稳定
适用性:适用于顺序存储和链式存储的线性表

2.堆排序

满足L(i)>=L(2i)&&L(i)>=L(2i+1)的堆,称为大根堆;
满足L(i)<=L(2i)&&L(i)<=L(2i+1)的堆,称为小根堆;
大小根堆都是一棵完全二叉树

void HeadAdjust(int k,int len)//下坠
{
    a[0]=a[k];
    for(int i=2*k;i<=len;i=i*2)
    {
        if(i<len&&a[i]<a[i+1])i++;
        if(a[0]>=a[i])break;
        else a[k]=a[i],k=i;
    }
    a[k]=a[0];
}
void BuildMaxHeap(int len)
{
    for(int i=len/2;i>0;i--)
        HeadAdjust(i,len);
}
void HeapSort(int len)
{
    BuildMaxHeap(len);
    for(int i=len;i>1;i--)
    {
        swap(a[1],a[i]);
        HeadAdjust(1,i-1);
    }
}

时间复杂度:$O(nlog_2n)$
空间复杂度:$O(1)$
稳定性:不稳定

五、归并排序

基本思想:将长度为n的排序表拆分为n个子表,进行两两归并,得到$\lceiln/2\rceil$个长度为2或1的有序表,继续两两归并...,直到得到一个长度为n的有序表为止,这种排序方法称为2路归并排序,排序次数与初始次序无关

void merge_sort(int a[],int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);

    int i=l,j=mid+1,t=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])temp[t++]=a[i++];
        else temp[t++]=a[j++];
    }
    while(i<=mid)temp[t++]=a[i++];
    while(j<=r)temp[t++]=a[j++];
    for(int i=l,j=0;i<=r;i++,j++)a[i]=temp[j];
}

时间复杂度:$O(nlog_2n)$
空间复杂度:$O(n)$
稳定性:稳定

六、Tips

Data Structure Visualization这个网站则提供了一种将数据结构和算法进行可视化的功能,并开发了交互式的动画展示,便于理解和掌握数据结构+算法
Data Structure Visualization入口

Big-O Cheat Sheet这个网站则把常见的数据结构和算法的各种复杂度进行了对比+整理+归纳,并制备了精美的表格,可供查阅+复习+背诵,一目了然
Big-O Cheat Sheet入口

补充:

  1. 通过一趟排序,能够确定一个元素的最终位置的排序:交换类(冒泡,快速排序),选择类(简单选择,堆排序)
  2. 关键字比较次数与原始序列无关:简单选择排序,折半插入排序
  3. 排序趟数与原始序列有关:交换类排序
none
最后修改于:2021年09月14日 18:55

添加新评论