啊哈算法之快速排序

浏览数：21 / 时间：2015年06月08日

关于效率问题

上篇讲的冒泡排序可以说是我们第一个真正的算法，他解决了桶排序的占用空间过大的问题（因为桶排序要根据排序的数的个数申请指定的内存），但是冒泡排序却牺牲了非常大的效率，假设我们要给1亿的数进行排序，因为桶排序的时间复杂度是O(M+N)，而冒泡的是O(N2)N的平方，假设计算机的速度是每秒10亿次，桶排序只需要0.1秒，而冒泡则需要1000万秒，大概115天，这是个很恐怖的数字，想想都能吓尿人。

基准数

假设我们要对6，1，2，7，9，3，4，5，10，8，这是个数进行排序，我们首先要选个基准数（不要被这个数吓到，这货就是我们拿来做参照的），我们就拿6当基准数吧。

排序原理讲解

下面我们要把比6大的数的放到6的右边，把6小的数放到左边，如何能做到呢，这就要使用上篇冒泡用到的方法，就是进行比较然后交换位置，但是这次我们从两头开始，假设有两个哨兵j和i 。i从6开始，即队首开始，j从8开始，即队尾开始，然后两个哨兵开始向中间寻找大于，小于6的数，哨兵j先出发（为什么j先出发呢，大家可以认真想想这个很重要），那么执行完第一次寻找之后：3，1，2，5，4，6，7，9，10，8，现在就实现了大于6的在右面，小于的在左边，6的位置已经确定，接着对6左右两个分别开始排序（因为6已经归位了）左面的选3为基准数，然后接着从左边的3，1，2，5，4的五个数组成的队列的两头开始寻找，第一次排序后的结果为2，1，3，5，4接着以在折半一次进行排序。这样就达到了最终的排序了，就是一直折半然后随机选择一个数当基准数，当然基准数如果靠左，这从右边开始，如果靠右就从左边开始，只有这样才能让基准数能正确的归位，这点很重要一定要理解。

关于效率

快速排序之所以快是相比冒泡排序每次交换位置的都是跳跃式的，每次排序设置一个基准数，把小于基准数的放到左边，大于基准数的放到右边，这样就不会像冒泡排序那样每次只能与相邻的数进行比较交换位置那么费事儿，比较的次数少了很多，这样也就提高了效率。因此冒泡排序最坏的就是相邻的数进行交换，这样就和冒泡排序的时间复杂度一致了就是O(N的平方），它的平均时间复杂度是O(nlogN)，其实快速排序体现的是一种“二分”思想。好了，下面上代码让大家好好理解理解

实例

#include <stdio.h>
int a[101],n;
void quickSort(int left,int right){ //快速排序
    int i,j,t,temp;
    if (left > right) { //判断参数的正确性
        return;
    }
    temp = a[left];
    i = left;
    j = right;
    while (i != j) { //判断是否相遇
        while (a[j] >= temp && i < j) { //右边的是不是小于基准数
            j--;
        }
        while (a[i] <= temp && i < j) { //左边的是不是大于基准数
            i++;
        }
        if (i < j) { //找到左边大于基准数，右边小于基准数进行交换
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i]; //相遇了，把基准数位置进行调整
    a[i] = temp;
    quickSort(left, i - 1); //递归的方法进行基准数左边的数进行调整
    quickSort(i + 1, right);//递归的方法进行基准数右边的数进行调整
}
int main(int argc, const char * argv[])
{
    int i,n;
    scanf("%d",&n); //输入数的个数
    for (i = 1; i <= n; i++) { //输入数据
        scanf("%d",&a[i]);
    }
    quickSort(1, n); //使用快速排序对输入的数进行排序
    for (i = 1; i <= n; i++) { //输出排序后的数
        printf("%d ",a[i]);
    }

}

相信大家结合注释都能看懂代码，我就不细说了

结果为：