算法笔记#1:快速排序

算法笔记#1:快速排序一个不起眼的算法笔记_台州oj3751:快速排序

大家好,欢迎来到IT知识分享网。

写在最前:

 

        教材上描述了几种排序方法,其中重点讲解了冒泡法排序。而冒泡法排序的原理虽简单,但放到计算机上实际运算却是个不小的工程。

先来回顾一下冒泡法排序的基本步骤:

void sort(int a[],int n)
{
    int i,j,t;
    for(i=1;i<n;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if(a[j]>a[j+1])
            {
                t=a[j+1];
                a[j+1]=a[j];
                a[j]=t;
            }
        }
    }
}

        在定义冒泡法排序的函数中我们可以看到用了两次for循环,也就是说,所需要的循环遍数为n(n-1)/2次,根据时间复杂度的计算公式可以得出,冒泡法排序的时间复杂度是O(n²)。效率低不说,如果遇到了来坑你的出题者,故意把数组元素往大了出,很有可能就会出现Runtime Error。

快速排序法的基本思路:

简单介绍一下快速排序法的基本思路:任意选取一个数据作为关键数据(一般都选择第一个),然后在数组内由后向前进行搜索,把比关键数据小的数放在其前,比关键数据大的数放在其后。这个过程称为一趟快速排序。

一趟快速排序算法一般包括以下步骤:

1.定义一个待排序数组a[0]…..a[n]。

2.设置两个变量i、j,令i=0、j=n-1。

3.定义变量key,用于储存关键数组,即key=a[0]。

4.从a[j]开始向前搜索(由后向前,包括a[j]),找到第一个小于key的元素,并与key交换。

5.从a[0]开始向后搜索(由前向后,包括a[0]),找到第一个大于key的元素,并与key交换。

6.重复上述第4、5步,直到i==j。

        简单的来说,就是在最开始确定一个关键元素key,这个关键元素key的值永远不变,每次由前向后,或者是由后向前的搜索都是将数组内元素和key进行比较,最后的目的是为了把key放在中间,小的放前面(由后向前找小于),大的放后面(由前向后找大于)。每次交换过后,i、j的值都发生相应的改变,变为交换之前,key所处的位置。

       那么将key放在中间之后,key之前和key之后的元素并没有按照规律排序。那么在一趟快速排序的基础上,可以以key为分界点,将数组分割,使用递归,将key之前和key之后的函数进行快排。

定义快速排序的函数:

void quicksort(int a[],int first,int end)
{
    int i=first,j=end,key=a[first];
    while(i<j)
    {
        while(i<j&&a[j]>=key)
        j--;
        a[i]=a[j];
        while(i<j&&a[i]<=key)
        i++;
        a[j]=a[i];
    }
    a[i]=key;
    if(first<i-1)
    quicksort(a,first,i-1);
    if(end>i+1)
    quicksort(a,i+1,end);
}

       那么在快速排序的过程中我们可以发现,每一趟快排结束之后,数组都被分成了两部分,即由n个元素的序列分为了2个n/2的排序问题,然后再进行递归调用完成剩余步骤。排序的效率为O(nlogn),比冒泡法的效率高很多。

p.s.:快速排序函数其实在stdlib.h里有现成的,可以直接拿来用(但我不会用那玩意=^=)。

接下来看一道例题:

TZOJ3751

描述

给定n个整数,请使用快速排序算法对其进行从小到大排序。

输入

输入数据有多组,每组包含2行,第一行为正整数n(n<=100000),第二行为n个整数。

输出

每组数据占一行,每行输出排序后的n个整数,以空格分开。

样例输入

5
1 3 2 4 5
6
2 5 1 3 3 2

样例输出

1 2 3 4 5
1 2 2 3 3 5

完整代码:

    #include<stdio.h>
    #define maxn 100001//注意这里题目要求的n的大小
    void quicksort(int a[],int first,int end)
    {
        int i=first,j=end,key=a[first];
        while(i<j)
        {
            while(i<j&&a[j]>=key)
            j--;
            a[i]=a[j];
            while(i<j&&a[i]<=key)
            i++;
            a[j]=a[i];
        }
        a[i]=key;
        if(first<i-1)
        quicksort(a,first,i-1);
        if(end>i+1)
        quicksort(a,i+1,end);
    }
    int main()
    {
        void quicksort(int a[],int first,int end);
        int n,a[maxn],i,j,k;
        while(~scanf("%d",&n)){
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        quicksort(a,0,n-1);
        for(i=0;i<n;i++)
        {if(i==n-1)
        printf("%d",a[i]);
        else
        printf("%d ",a[i]);
        }
        printf("\n");
        
        }
        return 0;


    }

这里因为define maxn的时候没有达到题目要求的那么大,刚开始直接习惯的写#define maxn 1001了,runtime error了好几次。。。。

算法笔记#1:快速排序

欢迎私信,评论区一起交流!

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/27518.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信