C++数据结构-高效排序算法

---

希尔排序

对于基本的几种排序方法：插入，选择，冒泡。他们的复杂度均为$O(n^2)$。算法运行所需时间增加的速度通常比数组本身增加的速度要快。

希尔排序通过将原数组分为及几个子数组，先分别将这几个子数组排序，再把排序好的子数组进行排序，可以大大提高效率，排序方法可使用任意简单排序，这里使用插入排序

用伪代码来表示

将数组data分为h个子数组
  for i = 1-h
    对子数组hi排序
  排序数组data

对于h的值的把控，是需要思考的问题。如果h过大，子数组就会过多，即使子数组已经排序好，也无法显著提高效率；反之，如果h过小，子数组的元素就会过多，算法效率也会降低。

希尔排序的核心是把数组data巧妙的分割为几个子数组，方法通常是：

从原始数组，每隔hi个元素提取一个元素，作为子数组的一部分，这样就能在逻辑上将数组分割

如下图，通过这种方式，data数组的大部分无序状态被消除了，在最后一次迭代中，数组更接近于它的最终形式

那么该如何选择最佳增量值h呢？

这里直接给出结论，一般认为满足以下条件的增量序列比较合适：
$$\begin{gathered} h_1=1 \\ {h}_{i+1}=3h+1 \end{gathered}$$
当h>=n时，停止即得h1。例如当n=10000时，则增量序列为
$$1,4,13,40,121,364,1093,3280$$
虽然希尔排序的复杂度已经比$O(n^2)$要好得多，但是要远远没有达到$O(nlogn)$

代码实现

template<class T>
void ShellSort(T data[],int arrSize){
    int i,j,hCht,h;
    int increments[20],k;
    for(h=1,i=0;h<arrSize;i++){
        increments[i]=h;
        h=3*h+1;
    }
    for(i--;i>=0;i--){
        h=increments[i];
        for(hCht=h;hCht<2*h;hCht++){
            for(j=hCht;j<arrSize;){
                T tmp=data[j];
                k=j;
                while(k-h>0&&tmp<data[k-h]){
                    data[k]=data[k-h];
                    k-=h;
                }
                data[k]=tmp;
                j+=h;
            }
        }
    }
}

堆排序

堆是具有以下两个属性的二叉树：

• 每个节点的值不会小于其子节点的值
• 树是完全平衡的，最底层的叶子结点都位于最左边的位置上

堆中的元素不会完全按序排序，但是唯一可以确定的是，根节点是最大的元素。堆排序从堆开始，将最大的元素放在数组末尾，然后重建少了一个元素的堆。在新堆中，将最大的元素移到正确的位置上，然后为其他元素恢复堆属性。通过这样的循环就能完成排序。

时间复杂度为O(nLogn)

template<class T>
void moveDown(T data[],int first,int last){
    int largest=2*first+1;
    while(largest<=last){
        if(largest<last && data[largest]<data[largest+1])
            largest++;
        if(data[first]<data[largest]){
            mySwap(data[first],data[largest]);
            first=largest;
            largest=2*first+1;
        }else
            largest=last+1;
    }
}

template<class T>
void heapsort(T data[],int size){
    for(int i=size/2-1;i>=0;i--)
        moveDown(data,i,size-1);
    for(int i=size-1;i>=1;i--){
        swap(data[0],data[i]);
        moveDown(data,0,i-1);
    }
}

快速排序

原始数组以一个边界值为基准划分为两个数组，第一个数字中所有的元素都小于边界值，第二个则都大于边界值。然后不断的迭代下去，直到划分为只包含一个元素的数组，此时就不需要排序了。

他的核心要点就在于边界值的选取，最好的情况是将数组划分为两个长度相差不大的数组。但是也可能因为选择了不合适的边界值导致极端情况，比如一个子数组1个元素，而其他元素都在另外一个子数组里。

在下列程序中，是选择位于数组中间的元素为边界值

template<class T>
void quicksort(T data[],int first,int last){
    int low=first+1,upper=last;
    swap(data[first],data[(first+last)/2]);
    T bound = data[first];
    while(low<=upper){
        while(data[low]<bound)
            low++;
        while(bound<data[upper])
            upper--;
        if(low<upper)
            swap(data[low++],data[upper--]);
        else low++;
    }
    swap(data[upper],data[first]);
    if(first<upper-1)
        quicksort(data,first,upper-1);
    if(upper+1<last)
        quicksort(data,upper+1,last);
}

以下程序在快速排序之前，对数组进行了预处理，将最大的元素放在了数组的末尾，这是因为，如果边界值正好是最大的元素，这会导致low的值超过数组的末端

template<class T>
void quicksort(T data[],int n){
    int i,max;
    if(n<2)
        return;
    for(i=1,max=0;i<n;i++){
        if(data[max]<data[i])
            max=i;
    }
    swap(data[n-1],data[max]);
    quicksort(data,0,n-2);
}

最好的情况：每次都能将数组分为两个长度相同的子数组，他的递归树应该是相对平衡的，树的高度为$h=log2(n)+1$，时间复杂度：
$$n+2\frac{n}{2}+4\frac{n}{4}+8\frac{n}{8}+..+n\frac{n}{n}=n(lo{g}_{2}n+1)$$
最坏的情况：每次都将数组分为一个长度为1的子数组和另外一个数组，其划分需要进行
$$n-2+n-3+n-4+n-5+...+1$$
时间复杂度为$O(n^2)$，平均情况下$O(nlogn)$更加常见。

快速排序的缺陷就在于划分的过程难以控制

归并排序

主要过程是将多个已经排好序的子数组合并为一个排好序的数组。他本身也是递归的，直到子数组的元素少于2个时，一分为二就会停止。伪代码如下

mergesort(data[],first,last){
  if first < last
    mid = (first + last) / 2;
	  mergesort(data,first,mid);
  	mergesort(data,mid+1,last);
  	merge(data,first,last);
}

他的时间复杂度也是$O(nlogn)$，他的缺点在于合并过程需要额外的存储空间，这对于大量的数据来说是巨大的缺点。

基数排序

他的排序思路如下图

复杂度为$O(d(r+n))$

void radixsort(long data[],int n){
    int d,j,k,factor;
    const int radix=10;
    const int digit=10;
    queue<long> queue[radix];
    for(d=0,factor=1;d<digit;factor*=radix,d++){
        for(j=0;j<n;j++){
            queue[(data[j]/factor)%radix].push(data[j]);
        }
        for(j=k=0;j<radix;j++)
            while(!queue[j].empty()){
                data[k++]=queue[j].front();
                queue[j].pop();
            }
    }
}

计数排序

排序思路如下图

//计数排序
void countingsort(long data[],const long n){
    long i;
    long largest = data[0];
    long* tmp=new long[n];
    for(i=0;i<n;i++){
        if(largest<data[i]){
            largest=data[i];
        }
    }
    unsigned long* count=new unsigned long[largest+1];
    for(i=0;i<n;i++){
        count[data[i]]++;
    }
    for(i=1;i<=largest;i++){
        count[i]=count[i-1]+count[i];
    }
    for(i=n-1;i>=0;i--){
        tmp[count[data[i]]-1]=data[i];
        count[data[i]]--;
    }
    for(i=0;i<n;i++)
        data[i]=tmp[i];
}