希尔排序(不稳定)

算法思想:(以从小到大为例)

   希尔排序使用了一个 h1,h2,h3,……,ht 的增量序列.用增量 Hk 对数据元素的一趟排序下来，所有相隔 Hk 的元素都已经被排好序，即：对于任意位置 i，A[i]<=A[i+hk]恒成立。待使用增量为1的那一趟排序之后，所有的元素都保持有序状态。

核心代码  

//此处增量序列取:1,3,5int hk;for(hk=5;hk>0;hk/=2){    for(i=hk;i<=N;i++){      int tmp=A[i];    //将大于TMP的元素赋给A[j-hk]，从而避免元素之间的直接交换，提升速度    for(j=hk;j-hk>=0;j-=hk)                    if(tmp

增量序列：

1.Hibbard增量序列

2.Sedgewick增量序列

(目前，我只接触到这两种增量序列)

复杂度分析:(这部分不会)

时间复杂度:最坏情况下，时间复杂度为O(N^2)；其他的时间复杂度分析依赖于增量序列的选择。

空间复杂度:空间复杂度为O（1）

堆排序

(需要用到堆的知识)

算法思想:

  利用数组存储元素，建立最大二叉堆；依次删除最大元，并通过下滤保证堆的堆序性质，将最大元保存在数组的尾部，直到二叉堆的元素全部删除；此时数组内的元素就完成了从小到大的排序。

核心代码:

#include
     
      //该函数用来保证堆的结构性和堆序性质void PercDowm(int *a,int i,int n){    int tmp;//tmp用来存储当前树根i的值    int child = 0;    for (tmp = a[i]; 2 * i + 1 < n; i = child){	child = 2 * i + 1;		//判断节点i的子树是否存在，若存在，找到子树上的最大元	if (child != n - 1 && a[child] < a[child + 1]) child++;		if (tmp < a[child]) a[i] = a[child];	else break;    }    a[i] = tmp;}int main(void){    ElementType A[200],tmp;    int n=0;    std::cin>>n;        for(int i=0;i
      
       >A[i];        //循环来构造最大二叉堆    for(i=n/2;i>=0;i--)        PercDowm(A,i,n);    //删除最大元，重新构造最大二叉堆    for(i=n-1;i>0;i--){        tmp=A[0];A[0]=a[i];a[i]=tmp;        PercDown(A,0,i);    }        for(i=0;i
       
        <
        
         <<" ";    std::cout<
        
       
      
     

复杂度分析:

时间复杂度:O（N*logN）

理论上是这样，但实际上堆排序慢于希尔排序