排序算法-09-排序1 排序 (25分)-第二部分

作者:神秘网友 发布时间:2020-09-07 19:43:47

排序算法-09-排序1 排序 (25分)-第二部分

排序算法-09-排序1 排序 (25分)-第二部分
  • 题目
    09-排序1 排序 (25分)
  • 排序算法-09-排序1 排序 (25分)-第一部分
    http://blog.csdn.net/bobo1356/article/details/71749720
  • 基本思想
    分而治之的思想。归并排序也是先分解后归并,归并的时候也做了一部分工作。而快速排序,是选取一个基准元素(povit),然后把数组分为两部分,通过交换,使得基准元素的左边都小于基准元素,右边都大于基准元素。
    基准元素一次性就排在了真正正确的地方。然后再递归地处理基准元素左边和右边就可以了。不需要在合并的时候进行操作。
    快排的一个关键点是选择基准元素
    如果基准元素每次都正好选在正中间,那么 T(N) = 2*T(N/2) + O(N) = O(N*logN)。
    但是如果基准元素每次都选择在最边上,那么 T(N) = T(N-1)+O(N) = O(N^2)。这样快排就退化为很慢的算法了。
    一种选择基准元素的方式是:选择数组左端、右端、中间的中位数作为基准元素。
  • 代码
#include <stdio.h>
#define ElementType long
#define maxn 100001
#define threshold 10

ElementType A[maxn];

void Swap(ElementType A[], int i, int j);
ElementType Median3(ElementType A[], int left, int right);
void Quick_sort(ElementType A[], int N);

int main(int argc, const char * argv[]) {
    int N,i;
    scanf("%d",&N);
    for(i=0; i<N; i++){
        scanf("%ld",&A[i]);
    }

    Quick_sort(A, N);

    printf("%ld",A[0]);
    for(i=1; i<N; i++){
        printf(" %ld",A[i]);
    }
    printf("\n");
    return 0;
}

void Swap(ElementType A[], int i, int j){
    ElementType tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

ElementType Median3(ElementType A[], int left, int right)
{
    int mid = (left + right)/2; 
    //下面使得 A[left]、 A[mid]、 A[right] 按序排列 
    if(A[left] > A[mid])    Swap(A, left, mid);
    if(A[left] > A[right])  Swap(A, left, right);
    if(A[mid] > A[right])   Swap(A, mid, right);
    //之后只需要考虑A[left+1] - A[right-2] 
    Swap(A,mid,right-1);
    return A[right-1];
} 

void Qsort(ElementType A[], int left, int right)
{
    int length = right-left+1;
    if(length <= 1) return;
    else if(length < threshold) Insert_sort(A+left, length);
    else{
        ElementType povit;
        int lo = left, hi = right-1;
        povit = Median3(A, left, right);

        while(1){
            while(A[++lo] < povit);
            while(A[--hi] > povit);
            if(lo > hi) break;
            else    Swap(A,lo,hi);
        }

        Swap(A, right-1, lo);   //将povit换到正确的位置上 

        Qsort(A,left, lo-1);    //递归解决左边 
        Qsort(A,lo+1,right); 
    }
}

void Quick_sort(ElementType A[], int N)
{
    Qsort(A, 0, N-1);
}


  • 运行结果
    排序算法-09-排序1 排序 (25分)-第二部分
    我们可以看到快速排序真的蛮快的。
  • 小结
    快速排序是不稳定的算法,最坏时间复杂度为O(N^2),但是当基准元素选取的比较好的时候,时间复杂度为O(N*logN)。空间复杂度为O(1)。
    我在上面的一个优化是:当数组长度小于一个阈值(我这儿为10)时,采用插入排序。
  • 核心代码
#include<stdlib.h>
int cmp(const void *a, const void *b)       
{  
    return(*(ElementType*)a-*(ElementType*)b);     
}
qsort(A,N,sizeof(ElementType),cmp);
  • 运行结果
    排序算法-09-排序1 排序 (25分)-第二部分
    哇,我发现我自己写的快排竟然比库函数还快一点,狠开心。
  • 大概思想
    可以用循环的方式来实现归并排序。具体就是刚开始两两归并,然后规模依次乘2,直到规模大于数组长度。
    具体的归并时要注意,先归并长度足够的元素,最后处理剩余的元素。
  • 代码
void Merge(ElementType A[],ElementType tmpA[], int L, int R, int rightEnd)
{
    int tmp = L,leftEnd = R-1,size = rightEnd-L+1;
    while(L<=leftEnd && R<=rightEnd)
    {
        if(A[L] <= A[R])    tmpA[tmp++] = A[L++];
        else                tmpA[tmp++] = A[R++];
    }
    while(L<=leftEnd)       tmpA[tmp++] = A[L++];
    while(R<=rightEnd)      tmpA[tmp++] = A[R++];

    int i;
    for(i=0; i<size; i++)   A[rightEnd-i] = tmpA[rightEnd-i];

}
//将A[]中的N个元素归并到tmpA[]中,其中length表示当前有序子列的长度 
void Merge_pass(ElementType A[], ElementType tmpA[], int N, int length)
{
    int i;
    for(i=0; i<=N-2*length; i+=2*length)
    {
        Merge(A, tmpA, i, i+length, i+2*length-1);
    }
    //归并最后两个列 
    if(i+length < N)    Merge(A, tmpA, i, i+length, N-1);
    else{//如果最后只剩一个子列 
        for(; i<N; i++) tmpA[i] = A[i];     
    }               
}

void Merge_sort(ElementType A[], int N)
{
    int length = 1;
    ElementType *tmpA;
    tmpA = malloc(sizeof(ElementType) * N);
    if(tmpA != NULL)
    {
        while(length < N)
        {
            Merge_pass(A, tmpA, N, length);
            length *= 2;
            Merge_pass(tmpA, A, N,length);
            length *= 2;
        }
        free(tmpA);
    } else{
        printf("空间不足\n");
    }

}

  • 运行结果
    排序算法-09-排序1 排序 (25分)-第二部分
  • 小结
    非递归排序用循环实现,比递归排序更快一些。时间复杂度还是O(N*logN)。

排序算法-09-排序1 排序 (25分)-第二部分相关教程

  1. C语言之插入排序
  2. C语言之选择排序
  3. linux内核中的排序接口--sort函数
  4. 归并排序
  5. 简单选择排序
  6. 快速排序
  7. 深度学习基础系列(三)之用 sklearn 实现 KNN算法
  8. 布隆过滤器Bloom Filter算法的Java实现(用于去重)