快排很脆弱


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

优点:

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

缺点:

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

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

先看一张图:
183631.jpg

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

182312.jpg

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

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;
}

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 快排很脆弱


Just For Fun...