各类常用排序代码及复杂度

下午就要考数据结构了呀有点慌....所以看看排序抱抱佛脚..于是...写了堆排序就停不下来了呢...

所以就把上课老师讲的排序都写了一遍..交题都过了可是复杂度可能会有些小问题..

//-------------------------堆排序------------------------//
//时间复杂度 平均 O(nlogn) 最坏 O(nlogn)
//空间复杂度 O(1)

#include <bits/stdc++.h>
using namespace std;

int a[1000006],n;

void PercDown(int a[],int i,int n)    //O(logn)
{
    if(2 * i + 1 >= n) return ;
    else if(2 * i + 2 >= n){
        if(a[i * 2 + 1] > a[i]) swap(a[i* 2 + 1] , a[i]);
    } 
    else{
        int p = i * 2 + 1,q = i * 2 + 2;
        if(a[p] > a[q]) swap(p,q);
        if(a[i] < a[q]){
            swap(a[q],a[i]);
            PercDown(a,q,n);
        }
    }
}
//(i + 1) * 2 (+ 1) - 1 = 2 * i + 1 || 2 * i + 2;
void HeapSort(int a[],int n)
{
    for(int i = n/2;i >= 0;--i){    //建堆（大根堆）
        PercDown(a,i,n);
    }
    for(int i = n-1;i >= 0;--i){    //更新大根堆
        swap(a[0],a[i]);
        PercDown(a,0,i);
    }
}

//-------------------------快速排序------------------------//
//时间复杂度 平均 O(nlogn) 最坏 O(n^{2})
//空间复杂度 O(logn)

#include <bits/stdc++.h>
using namespace std;

int a[1000006];

void QuickSort(int a[],int l,int r)        
{ 
    int i,j,p;
    p = a[l];
    i = l,j = r;
    while(i < j){
        while(i < j && a[j] >= p){    //先移动右指针寻找大于哨兵的值
            j--;
        } 
        if(i != j){
            a[i] = a[j];
        } 
        else break;
        while(i < j && a[i] <= p){    //后移动左指针寻找小于哨兵的值
            i++;
        }
        if(i != j){
            a[j] = a[i];
        }
        else break;
    }
    a[j] = p;    //指针相碰，指针位置就是哨兵的最终位置

    if(l < j) QuickSort(a,l,j);
    if(j+1 < r)QuickSort(a,j+1,r);
}

//-----------------------直接插入排序----------------------//
//时间复杂度 平均 O(n^{2}) 最坏 O(n^{2})
//空间复杂度 O(1)

#include <bits/stdc++.h>
using namespace std;

int a[1000006];

void InsertSort(int a[],int n)
{
    for(int i = 1;i < n;++i){
        int p = a[i];
        for(int j = i;j >= 0;--j){
            if(a[j-1] > p) a[j] = a[j-1];
            else{
                a[j] = p;
                break;
            }
        }
    }
}

//-------------------------希尔排序------------------------//
//时间复杂度 平均 O(nlogn) 最坏 O(n^{2})
//空间复杂度 O(1)

#include <bits/stdc++.h>
using namespace std;

int a[1000006];

void ShellSort(int a[],int n)
{
   for(int d = n/2;d > 0;d/=2){        //以n/2为增量序列
       for(int p = d;p < n;++p){
           int tmp = a[p];
           int i = p;
           for(i = p;i >= d && a[i-d] > tmp; i-=d)  
                a[i] = a[i-d];
            a[i] = tmp;
       }
   }
}