对于大桌子来说,这是一种奇怪的速度

我一直在做我的作业,比较一堆排序算法,我遇到了一个奇怪的现象.事情已经如预期的那样:insertionsort赢得了像20个整数的表格,否则快速超越了heapsort和mergesort.最多可达500,000个表格(存储在内存中).对于5,000,000英镑(仍然存储在内存中),快速排序突然变得更糟,然后是heapsort和mergesort.数字总是随机均匀分布,关闭Windows虚拟内存.任何人都知道可能是什么原因造成的？

     void quicksortit(T *tab,int s) {
                   if (s==0 || s==1) return;
                   T tmp;
                   if (s==2) {
                      if (tab[0]>tab[1]) {
                                         tmp=tab[0];
                                         tab[0]=tab[1];
                                         tab[1]=tmp;
                                         }
                      return;
                      }
                   T pivot=tab[s-1];
                   T *f1,*f2;
                   f1=f2=tab;
                   for(int i=0;ipivot)
                              f2++;
                           else {
                                tmp=*f1;
                                *f1=*f2;
                                *f2=tmp;
                                f1++; f2++;
                                }
                   quicksortit(tab,(f1-1)-tab);
                   quicksortit(f1,f2-f1);
     };

2501.. 11

当数组中有许多重复项时,您的算法开始失败.你只注意到这个值很大,因为你一直在为算法提供具有大跨度的随机值
(我假设你使用了rand():0 - RAND_MAX),而这个问题只出现在大数组中.

当您尝试对相同数字的数组进行排序(尝试排序100000个相同的数字,程序将崩溃)时,您将首先遍历整个数组,多余地交换元素.然后将数组拆分为两个,但是大数组只减少了1:

                    v
quicksortit(tab,(f1-1)-tab);

因此,您的算法变为O(n ^ 2),并且您还消耗了大量的堆栈.在这种情况下,搜索更好的支点并不会帮助您,而是选择不会出现此缺陷的quicksort()版本.

例如:

function quicksort(array)
    if length(array) > 1
        pivot := select middle, or a median of first, last and middle
        left := first index of array
        right := last index of array
        while left <= right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left <= right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

这是修改后的版本:http://rosettacode.org/wiki/Sorting_algorithms/Quicksort