算法读书笔记第2章-2

继续介绍排序---希尔排序, 归并排序, 快速排序, 堆排序
(1)希尔排序:也是一种插入排序,但是时间效率有所提高,是因为权衡了子数组的规模和有效性
①基本思想:先将整个待排序的分割成若干个子序列(具有一定的增量)分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。实质就是分组插排

void ShellSort(int a[], int n)
{
    int h = 1;
    while(h < n/3){
        h = 3*h + 1;
    }
    while(h > 0){
        for(int i = h; i < n; ++i){
            for(int j = i; j >= h; j-=h){
                    if(a[j] < a[j-h])
                        swap(a[j],a[j-h]);
            }
        }
        h = h/3;
    }
}

③时间复杂度:O(N3/2)~O(N7/6)
④额外空间复杂度：O(1)
⑤不稳定

（2）归并排序
①基本思想:类似于一棵树,不断的划分,直到划分到一个数,不可再划分停止,之后开始向上递归合并
②核心代码:

void Merge(int a[], int l, int mid, int r)
{
    int i = 0;
    int p1= l;
    int p2 = mid+1;
    int help[maxn];
    while(p1<=mid && p2 <= r)
    {
        help[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
    }
    while(p1 <= mid)
    {
        help[i++] = a[p1++];
    }

    while(p2 <= r)
    {
        help[i++] = a[p2++];
    }
    int k = 0;
    for(int i = l; i <= r; ++i)
    {
        a[i] = help[k++];
    }
}

void MergeSort(int a[],int l,int r)
{
    if(l == r)
        return ;
    int mid = l + (r-l)/2;
    MergeSort(a,l,mid);
    MergeSort(a,mid+1,r);
    Merge(a,l,mid,r);
} 

③时间复杂度:O(n*logn)
④额外空间复杂度:O(n),需要生成一个help数组
⑤稳定
(3)快速排序
①基本思想:选定一个元素作为标准,之后划分大于,小于,等于这个数的三个区域,之后递归即可
②核心代码:

vector<int> Partition(int a[], int l, int r)
{
    vector<int> ans;
    int less = l-1;
    int more = r;
    int pos = l;
    while(pos < r)
    {
        if(a[pos] < a[r])
            swap(a[++less],a[pos++]);
        else if(a[pos] > a[r])
            swap(a[--more],a[pos]);
        else
            pos++;
    }
    swap(a[more],a[r]);
    ans.push_back(less+1);
    ans.push_back(more);
    return ans;
}

void QuickSort(int a[], int l, int r)
{
    if(l < r)
    {
        int pos =l+rand()%(r-l+1);
        swap(a[pos],a[r]);
        vector<int> p = Partition(a,l,r);
        QuickSort(a,l,p[0]-1);
        QuickSort(a,p[1]+1,r);
    }

}

③时间复杂度:O(n*logn)
④额外空间复杂度:O(logn),记录树的断点
⑤不稳定

(3)堆排序
①基本思想:建立大根堆,就是优先队列,之后剪枝,调堆
②核心代码:

void HeapInsert(int a[], int index){
    while(a[index] > a[(index-1)/2])
    {
        swap(a[index],a[(index-1)/2]);
        index = (index-1)/2;
    }
}

void Heapify(int a[], int index, int size){
    int left = index*2 + 1;
    while(left < size)
    {
        int largest  = left+1 < size && a[left+1] > a[left] ? left+1 : left;
        largest = a[largest] > a[index] ? largest : index;
        if(largest == index) break;
        swap(a[largest],a[index]);
        index = largest;
        left = index*2 + 1;
    }

}

void HeapSort(int a[],int n){
    for(int i = 0; i < n; ++i)
    {
        HeapInsert(a,i);
    }
    int size = n;
    swap(a[0],a[--size]);
    while(size > 0)
    {
        Heapify(a,0,size);
        swap(a[0],a[--size]);
    }
}

③时间复杂度:O(n*logn)
④额外空间复杂度:O(1),原地调序
⑤不稳定
#笔记##读书笔记#