数据结构复习——内部排序

内部排序算法总结

在数据结构的书中谈到的内部排序的算法有很多，但就其性能来说，很难说出最好的方法，每种方法都有自己的优缺点，就其排序的时间复杂度来说主要有下面三种类别：
1.简单的排序算法，时间复杂度为$O(n^2)$O(n2)
2.先进的排序方法，时间复杂度为$O(nlogn)$O(nlogn)
3.基数排序，时间复杂度为$O(d\cdot n)$O(d⋅n)
先直接给出一些干货吧

下面我将对这三种类型的排序算法来进行分析，文中给出的大部分是伪代码，主要是描述算法思想。第一次写博客，如有不好的地方还请大家多多包涵(≥◇≤)

1.$O(n^2)$O(n2)型

1.直接插入排序

插入排序的一个主要思想是将当前该插入的元素关键字与排列中的元素关键字进行逐个比较，找到合适的位置进行插入，利用了数组元素中的下标为0的元素作为监视哨，将每次需要插入的元素先放到监视哨中，然后从尾端开始逐个向前比较。
例如：以数组存储 { 49, 38, 65, 97, 76, 13, 27, 49 }，并进行插入排序。

void insertsort(sqlist& L)
{
    for(i=2;i<L.length;i++)
    {
        L[0]=L[i];//将变量放入监视哨中
        j=i-1;
        while(compare(L[i].key,L[j].key)&&j)//自定义的排序方式
        {
                L[j+1]=L[j];//记录后移
                j--;//继续向前比较
        }
        L[j+1]=L[0];//找到合适位置后插入
    }
}

算法分析：
1.时间上，该程序显然具有两重循环，且循环的次数与序列的个数n有关，则时间复杂度为$O(n^2)$O(n2)，
2.空间上，为了实现排序过程，该程序仅使用的辅助空间为L[0]作为数据记录，没有新增的辅助空间，故空间复杂度为$O(1)$O(1)
3.该算法对于n较小时比较适合操作，n很大时采用折半插入能减少比较的次数，但算法的移动次数还是不变，故算法复杂度还是$O(n^2)$O(n2)
4.要注意的一点是：这个算法每趟排序后各个数字位置不是最终确定的位置！

2.选择排序

选择排序的基本思想是，通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的元素和第i个元素发生交换，则可知在每一趟排序的过程中，我们都能确定一个最小元素的位置。

//这里给出一种链式存储结构下的选择排序
void select(lklist* &head)
{
    lklist *p,*q,*s;
    int min,t;
    if(head==NULL||head->next==NULL) return;
    else
    {
        for(p=head;p!=NULL;p=p->next)
        {
            min=p->data;
            for(q=p->next;q!=NULL;q=q->next)
            {
                if(min>q->data)
                {
                    min=q->data;
                    s=q;
                }
            }
            if(s!=p)//证明发生了交换
            {
                t=s->data;
                s->data=p->data;
                p->data=t;
            }
        }
    }
}

该算法在链式存储下的操作还是有点复杂的，当时拿到这个题目写的时候还不是很自信，可以看出相比数组下的操作还是会麻烦一些。

3.冒泡排序

简单来说，冒泡排序的原理就是相邻的两个元素的关键字进行比较，小的元素向上冒，大的元素向下沉,遇到不满足的情况就会发生交换，因此在每趟排序后，都能确定该趟排序最后一个元素。

void Bubblesort(ElemType L[])
{
    i=L.lenth;
    while(i>1)
    {
        swapflag=0;//判断该趟排序是否有元素发生交换
        for(j=1;j<i;j++)
        {
            if(L[j+1]>L[j])
            {
                swap(L[j+1],L[j]);//交换元素
                swapflag=1;
            }
        }
        if(!swapflag)
        break;//若已经无元素发生交换，则该表有序，退出循环
    }
}

在该算法中，我们也可以很清楚的看到两重循环，其算法复杂度也为$O(n^2)$O(n2)，在添加了swapflag标志位后，我们能提前判断该序列是否有序，减少循环的次数。空间上也不需要开辟辅助空间，适合于n比较小的情况，可以很快在n个待排序的数据中选择前k个最大值。

2.$O(nlogn)$O(nlogn)型

1.希尔排序

希尔排序的方法又称之为“减小增量排序”，适用于n比较大的情况，他的排序思想就相当于分割子序列，实现子序列的基本有序后，再进行一次全排列就达到了效果，看上去好像比之前的算法麻烦，但是如果n很大，序列分布的散度很大时，在实现基本有序化后，全排列时的交换次数其实就很少了。
还是插入排序的例子：在这里看看shell排序的原理吧，其实希尔排序就是多次不同增量下的插入排序的推广。

void Shellsort(ElemType a[],int n)
{
    for(d=n/2;d>=1;d=d/2)//d是增量，每次增量减半
    {
       for(i=d+1;i<=n;i++)
        for(j=i-d;j>0&&a[j]>a[j+d];i-=d)
            swap(a[j],a[j+d]);
            //相差d的相邻元素进行比较交换
    }
}

该算法看上去好像是三个循环，但是事实上，每次都是折半的排序，因此当n很大的时候，可以趋向于$O(nlogn)$O(nlogn)，该算法是按照我的逻辑理解写的，如有错误还请批评指正，其实更多的是理解图中的含义。

2.快速排序

说到快速排序，其实在c++STL和java中有封装好的quicksort函数，可以直接来用，在这里我们是主要理解分治和递归的思想，每一趟排序都是
任选一个元素的关键字(如L[1].key)作为标准，将序列分成两部分。通过交换实现左半部分的结点的关键字小于等于该元素的关键字，右半部分的结点的关键字大于等于该元素的关键字。 然后, 对左右两部分分别进行类似的处理，直至排好序为止。可以看看 洛谷P1177的快速排序模板题，来练练手。
快速排序展示十分麻烦，有个比较好的视频解释可以去看看

void quicksort(SqList &L,int left,int right)
{
    i=left;
    j=right;
    p=a[left];
    while(i<j)
    {
        //这两个循环不太懂不妨想想退出循环是什么情况
        while(i<j&&a[j]>p) j--;
        swap(a[i],a[j]);
        while(i<j&&a[i]<p) i++;
        swap(a[i],a[j]);
    }
    quickSort(a, left, i-1);
    quickSort(a, j+1, right);
}

该算法利用分治递归的思想，将排序交换的区间一次次减半，快速排序过程可以看成一棵二叉树, 二叉树中每一层与n有关，趟数与$log_{2}(n)$log2​(n)有关。
注意：当待排序的数据已有序时，其时间复杂度是$O(n^2)$O(n2)，这样一来快速排序的效率也就降低了。
但是该排序算法是需要开辟一个栈空间来实现递归的，其栈的最大深度为$\lfloor log_{2}(n)\rfloor+1$⌊log2​(n)⌋+1其空间复杂度为$O(logn)$O(logn)，同时排序过程中的元素交换会使得排序不稳定。

3.堆排序

堆排序的建立主要是将无序数组看成是一颗完全二叉树，然后通过树的方式来调整，一般分为最大堆和最小堆，在c++STL中可以通过优先队列priority_queue来建立堆。（即根结点的权值大于（小于）左右子树，同时他的左右子树也是一个堆，递归定义的方式来描述）
关于堆排序的描述确实不太好说，这里给一个链接

void  sift ( elemtype r[],int i, int m){ //筛选算法
     //把完全二叉树r[i]..r[m]调整成一个堆
     //初值：i的左右子树均是堆
    int j=i*2; //j指向左孩子
    r[0]=r[i]    //将r[i]暂存到r[0]中
    while  (j<=m)  { 
       if ( j<m && r[j].key<r[j+1].key ) j++;
     // 左孩子与右孩子进行比较, 找较大孩子，确定筛选的方向 
   if ( r[0].key < r[j].key )  
           {    r[i] = r[j];  i=j;  j=2*i;   } //继续筛选
      else     j=m+1; //筛选完毕
   }
   r[i] = r[0];
} 

void heatsort (elemtype r[],int n ){  
     // 将r[1]..r[n]进行堆排序
       for (j=n/2;j>=1;j--)
            Sift (r, j, n)  //建堆，得最大值r[1]
       for (j=n;j>=2;j--){ 
           r[0]=r[1]; r[1]=r[j]; r[j]=r[0];   
               //堆顶（根）结点与最后结点的值对换
           sift (r,1, j-1) ;   //调整堆
        }
}
//该算法未经测试会存在一些问题，如有问题请提出批评指正。

sift(j,n)的时间是$O(log_{2}n)$O(log2​n)，堆排序的时间=建立堆+（n-1)次调整堆，时间复杂度为$O(nlogn)$O(nlogn)而空间上只需要一个暂存元素的r[0],其空间复杂度为$O(1)$O(1)，堆排序的过程中父子和左右孩子之间会有交换因此不能维持排序的稳定性。

3.归并排序

归并排序主要是将两个或两个以上的有序数组合并成一个有序数组，也可以利用这个算法将一个数组多次分半有序化后，进行合并，然后实现排序。选择这张紫书的经典例子主要是想提醒一下该图中最后部分奇数个元素的归并值得注意。

void merge(int r[],int s[],int x,int m,int y)
{
   int i=x;
   int j=m+1;
   int k=x;
   while(i<=m&&j<=y)//将表的左右两部分合并到s数组
   {
       if(r[i]<r[j])
           s[k++]=r[i++];
       else
           s[k++]=r[j++];
   }
   //由于左右表的长度不一样，循环退出后，表长中的剩余元素继续导入s数组。
   while(i<=m)
        s[k++]=r[i++];
   while(j<=y)
        s[k++]=r[j++];
}

void mergesort(int r[],int s[],int x,int y)
{
    if(x==y)
    {
        for(i=x;i<y;i++)
        {
            r[i]=s[i];//从辅助的数组赋值会原数组。
        }
    }
    else
    {
        m=(s+t)/2;
        mergesort(r,s,x,m);
        mergesort(r,s,m+1,y);
        merge(r,s,x,m,y);
    }
}

在该程序中可以看出，实现归并算法需要开辟和待排数组同等的空间，利用分治递归的思想能够实现，相比其他同等的算法，归并算法是一种稳定的算法。

3.$O(d\cdot n)$O(d⋅n)型

1.基数排序

基数排序和前面的排序方法最大的不同在于，基数排序的算法，不是基于比较的算法，而是基于多关键字的排序思想，这是一种按位来排序的算法，该算法中还包含有队列的方法，在按关键字排序时，必须保证有先进先出的原则，因此他的每一趟排序并不是随意的。这个算法主要时掌握其思想，具体算法我就不给了。
例：对{ 278, 109, 63, 930, 589, 184, 505, 269, 8, 83 }
用基数排序法进行排序。