C语言快速排序

2020年01月07日 318点热度 3人点赞 0条评论

在阅读本文章前请确定你已经掌握递归的思想

快速排序是一种高效的排序方式,它的时间复杂度最差情况是O(n2) ,理想情况O(nlog2n),正是因为它的高效,该排序方法被认为是目前最好的一种内部排序方法,对于初学者来说理解可能有难度.

快速排序的大致步骤:

1.选取一个划分标准(一般选择最左边的值).

2.通过某种算法(暂时忽略这个算法的实现)将数组以标准值划分为两部分,左边的都小于或等于标准值,右边的都大于或等于标准值.

3.分别将标准值两边看做两个新数组,将新数组进行上述过程。

4.直到划分到元素总数小于2就返回.

举个栗子,我有一组数,想要把它们从小到大排列

5    9    2    7    3    8    6    1    4

如下图

根据这个算法我们可以简单的写一下代码,代码中忽略可以将数组分为两部分的“某种算法”.

void quickSort(int a[],int left,int right)
{
    if(left>=right)return ;//当划分的元素小于2的时候函数直接返回
    int key=a[left];
    --某种算法--//调整数组,也就是能让key的左边的所有元素小于右边

    quickSort(a,left,key-1);
    quickSort(a,key+1,right);
}

这是快速排序的一个框架

“某种算法”的步骤(从小到大):

下面是如何实现这个期待已久的“某种算法”这是快速排序的另一个难点,也是理解快速排序的关键.

首先我们肯定想到的是将数组中每一个元素与key进行比较,如果key前面的元素小于key,就将该元素删除然后插入到key后面,......诶?等等,这是一个数组,如果对数组进行删除或者插入操作将会将数组的大量元素进行移动,如果这样做,整个算法效果很可能还没有选择排序速度快,所以就有了先人留下的算法了:

算法需要定义两个变量i,j他们初始时分别在数组的左边和右边,i从左到右查找,j从右到左查找。定义一个key变量用来储存划分标准.

1.将key所在的地方(一般都是最左边的元素,即i位置)视为一个“缺位”

2.j从尾部进行查找,直到某个数小于或等于key.

3.j位置的值赋给“缺位”即i位置,并将j视作缺位。

4.i开始从左向右查找,直到某个数大于或等于key.

5.i位置的值赋给“缺位”即j位置,并将i位置视为缺位.

6.回到第1步重复执行,直到i==j;

只是这样说可能有点不好理解,下面举一个栗子,多图预警.

将第0位视为缺位

j在该位置发现key<a[j],将j所在位赋给缺位i,轮到i移动;

i发现当前位4<key正常,就往右移动

i发现当前位9>key,就将9赋给缺位j,并将i视为缺位,轮到j移动。

j发现当前位置9>key正常,就往左移动.

j发现1<key,就将j所在位赋给i,并把j视为缺位,轮到i移动

i发现1<key,正常,i向右移动.

i发现2<key正常,继续向右移动

I发现7>key,将7赋给缺位j。并把i视为缺位,轮到j移动

j发现7>key正常,向左移动

正常,继续向左移动.

继续向左移动.

j发现3<key,将3赋给缺位i,然后轮到i移动

上图i发现3<key正常,向右移动

好了,i==j他们相遇了

最后,将key赋值给i或j缺位.,这样就分好了

这个过程仔细观察我们会发现几个规律,就是缺位永远交替落在i和j位置上,这样就不用单独设置一个变量来保存缺位的位置了,只需要循环i查找,j查找,i查找,j查找。我们用这个规律在整合之前写好的快速排序的框架得到代码:

void sort(int a[], int left, int right)
{
    if(left>=right)return;//当需要排序的元素数小于2,返回
    int i=left,j=right,key=a[left];
    while(i<j)
    {
        while(i<j&&key<=a[j])j--;//j从左边查找直到key<=a[j]
        a[i]=a[j];//用j填补i的缺位,现在j为缺位
        while (i<j&&key>=a[i])i++;//i从左边查找,直到key>=a[j]
        a[j]=a[i];//用i填补j的缺位,此时i为缺位
    }
    a[i]=key;//填补最后一个缺位
    sort(a,left,i-1);//对标准元素左边的全部元素执行上述过程
    sort(a,i+1,right);//对标准元素右边的全部元素执行上述过程
}

代码写出来不过十几行,但是其中的逻辑性却很强,这也是算法的魅力所在。

这篇文章我写了两遍,第一遍是因为Ubuntu系统死机,重启之后发现上次写的文章没被网站保存,然后又重新做的图写的文章,希望对你有用.

Danny

我就如一粒石子,在随波逐流中,逐渐冲蚀了自己的棱角,变光滑,也变丑陋。

文章评论