快速排序应该是应用非常广泛的一种排序算法，其效率也很高，它的优缺点如下：

优点：

1. 原地排序（只需要一个很小的辅助栈，内存消耗小）。
2. 排序一个长度为N的数组，所需的时间和[NlogN]成正比，所需耗时的增长数量级为“线性对数级别”。
3. 内循环比大多数排序算法都要短小，例如： 选择排序需要循环N-1-i（i表示外循环的变量）次，才能完成一次内循环；而快速排序的内循环次数，根据数组的有序程度而定。区间在1 ~ N / 2 - 1的范围内。

缺点：

1. 不稳定，最好情况下复杂度为O(NlogN)，最差情况，复杂度为O(N^2)。
2. 非常脆弱，编写时容易出现错误，导致实际性能只有“平方级别”。

之前一直没感觉到快排多脆弱，今天彻底感受到了。

先看一张图：

什么？！快排比归并排序要慢？我反复看了几遍代码，并没看出来哪里错了，然后我从网上复制了一段快排代码，粘贴，编译运行，神奇的事情发生了，如下图：

至此，我很是疑惑，反复对比代码，最终找到了问题所在，在快排交换数据的地方我是这样写的：

if (i < j)
    swap(&a[i], &a[j]);

其中swap函数如下：

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

别人是这样写的：

if (i < j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

咋一看，没什么区别嘛，没错，效果是一样的，但效率嘛，就不一样了，调用函数来交换数据要比直接交换数据慢，原因仔细想想也很简单。

原因

数据交换在快排中算是核心计算部分，调用函数就会导致多一层调用栈，随着递归的不断深入，效率差就一点点被放大了。

所以，快排是真的脆弱啊，稍不注意，效率就降下去了，甚至可能导致快排和冒泡排序没什么区别，时间复杂度都为O(N^2)。

最后，附上完整的代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}


/*
 * 归并排序 —— 合并
 */
void merge(int* a, int* temp, int low, int mid, int high)
{
    int i = low, j = mid + 1;
    for (int k = low; k <= high; k++)
    {
        if (i > mid)
            temp[k] = a[j++];
        else if (j > high)
            temp[k] = a[i++];
        else if (a[i] > a[j])
            temp[k] = a[j++];
        else
            temp[k] = a[i++];
    }

    for (int k = low; k <= high; k++)
        a[k] = temp[k];
}

/*
 * 归并排序 —— 分治
 */
void sort(int* a, int* temp, int low, int high)
{
    if (high <= low) return;
    int mid = low + ((high - low) >> 2);
    sort(a, temp, low, mid);
    sort(a, temp, mid + 1, high);
    merge(a, temp, low, mid, high);
}

/*
 * 归并排序
 */
void mergeSort(int* a, int n)
{
    int* temp = (int*)malloc(sizeof(int) * n);
    sort(a, temp, 0, n - 1);
}

/*
 *快速排序 —— 排序
 */
void sort(int* a, int low, int high)
{
    if (high < low) return;

    int i = low, j = high;
    int v = a[low];
    while (i != j)
    {
        while (i < j && a[j] >= v)
            j--;
        while (i < j && a[i] <= v)
            i++;

        if (i<j)
        {
            //这样写是 0.219
            //swap(&a[i], &a[j]);

            //这样写是 0.172
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    swap(&a[j], &a[low]);
    sort(a, low, j - 1);
    sort(a, j + 1, high);
}

/*
 *快速排序
 */
void quickSort(int* a, int n)
{
    sort(a, 0, n - 1);
}

int arr[1000000];
int arr2[1000000];
int main()
{
    printf("准备数据...\n");
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    {
        arr[i] = rand();
        arr2[i] = arr[i];
    }
    printf("OK \n");

    clock_t s1 = clock();
    printf("归并.....\n");
    mergeSort(arr, sizeof(arr) / sizeof(int));
    clock_t e1 = clock();

    clock_t s2 = clock();
    printf("快排.....\n");
    quickSort(arr2, sizeof(arr2) / sizeof(int));
    //quicksort(arr2, 0, sizeof(arr2) / sizeof(int) - 1);
    clock_t e2 = clock();

    printf("归并：%f\n快排： %f\n",
        (double)(e1 - s1) / CLOCKS_PER_SEC, (double)(e2 - s2) / CLOCKS_PER_SEC);

    return 0;
}