常用的快速排序

137 阅读 0 评论 91 点赞

我是靠谱客的博主受伤音响，最近开发中收集的这篇文章主要介绍常用的快速排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快速排序

之前的冒泡排序，解决了之前简化的桶排序的浪费空间的问题，但是在执行效率上牺牲了不少。假如我们的计算机每秒钟可以运行十亿次那么对一亿个数进行排序，桶排序就只需要0.1秒，而冒泡排序需要一千万秒，达到115天之久，这时间就有点吓人。那么有没有既不浪费内存空间又可以快速排序的算法呢？那就是快速排序了，光听名字就知道很快了。

假设我们现在要对 6 1 2 7 9 3 4 5 10 8这10个数进行排序。首先要在这个序列中找出一个基准数。为了方便就让第一个数6来做基准数，接下来就是将序列数中比基准数大的数放到6的右边，比基准数小的数放在6的左边。类似下面这样排序

3 1 2 5 4 6 9 7 10 8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置设为k。现在需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边数都大于等于6。

方法其实很简单：分别从上面序列的两端开始遍历，先从左往右编译到一个比6小的数，再从右往左遍历一个比6大的数，然后交换它们。以以上序列6 1 2 7 9 3 4 5 10 8为例，右边第一个比6小的是5，左边第一个比6大的是7，然后交换位置，变成以下：

6 1 2 5 9 3 4 7 10 8

第一次交换结束，然后继续遍历移动，然后遍历到了4和9，然后再次交换变成如下：

6 1 2 5 4 3 9 7 10 8

此时，左右两边的变量都走到了3，遍历结束，将基准数6和3进行交换，交换之后的序列如下：

3 1 2 5 4 6 9 7 10 8

到此，第一轮遍历真正结束。此时以基准数6为分界点，左边的数都小于等于6，右边的数都大于等于6。

现在基准数6已经归位，它正好处于序列的第6位。此时我们已经讲原来的序列，将6划分为两个序列，左边的序列为3 1 2 4 5，右边的序列为9 7 10 8。解下来就是需要分别处理这两个序列，因为6的左边和右边都还没有归位，都是乱序的。归位方法与刚刚的方法一样。

快速排序之所以比较快，是因为相比冒泡排序，每次的交换都是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，大于等于基准数的全部放到基准点的右边。这样，每次在交换的时候就不会想冒泡排序一样只能在相邻的两个数之间进行交换，交换的距离就大了很多。因此，总的比较的次数和交换次数就变少了，速度自然就提高了。当然在最坏的情况下仍然是相邻的两个数进行交换。因此快速排序的最差时间复杂度和冒泡排序是一样的。其实快速排序是基于一种叫做二分的思想。

#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);
    
    return;
}

int main()
{
    int i, j;
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    quicksort(0, n - 1);
    
    for (i = 1; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("n");
    
    return 0;
}