为什么quickSort运行速度较慢？

Question

所以我在我的大学里有这样的课，我们做各种各样的类，现在我们做递归排序，又名quickSort。哪里好，你们都知道它做什么，将数组分成两部分，依此类推，直到它以1个元素结尾，然后对它们进行排序。

所以我们讨论哪一个会更快，为什么这就是所谓的quicksort，它的结果是quickSort的复杂性是n.log2（n），而例如冒泡排序是n^2。好的，我在c＃中编写了bouth代码，并使用c＃计算器的秒表来执行bog alogirithyms，在这里我生成了-65000,65000和长度为50 000个元素的数组。

所以冒泡做了排序首次23秒第二时间29（原因它们是随机量。），即使我使阵列与第一元件50K元件N-1。也就是说，它需要对所有东西进行排序，它在27秒内完成（如此接近随机），如果我从我开始创建一个数组，它确实需要17秒对它进行排序。

所以我跑的快速排序，和良好已过5分钟，还是没有结果......如果我有ARRA运行[我] =我;或者n-i;它给了我stackoverflow例外。

qSort更快的唯一的地方是当有一个数组像100或200，他们已经排序（又名数组[i] = i）和更快的像0.1-0.2秒。布尔sort可以排序真正巨大的数组，而qSort给了我stackoverflow。

所以回到复杂度，qSort为5万个元素= 780482 而bblesort = 2 500 000 000 它清晰如明日qSort需要什么？快99.99％。但它不是？为什么我真的好奇这件事，因为我的Lector曾经说过qSort要快得多。但是在所有类型的测试之后，它似乎比bubblesort更快（稍微快一点），而且它只与没有太多元素的数组一起工作（10k随机元素qSort 17秒，而bublesort 7）。

我的电脑是每个2.6 GHz的酷睿i7 4cores，我有16 GB的内存DDR4。

我会很高兴，如果有人清除的东西，因为我的讲师似乎给我的虚假信息。

EDIT bouth代码： 的qsort ..................................

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace QuickSort 
{ 
class QuickSort 
{ 
    static public int Partition(int[] numbers, int left, int right) 
    { 
     int pivot = numbers[left]; 
     while (true) 
     { 
      while (numbers[left] < pivot) 
       left++; 

      while (numbers[right] > pivot) 
       right--; 

      if (left < right) 
      { 
       int temp = numbers[right]; 
       numbers[right] = numbers[left]; 
       numbers[left] = temp; 
      } 
      else 
      { 
       return right; 
      } 
     } 
    } 

    static public void SortQuick(int[] arr, int left, int right) 
    { 
     // For Recusrion 
     if (left < right) 
     { 
      int pivot = Partition(arr, left, right); 

      if (pivot > 1) 
       SortQuick(arr, left, pivot - 1); 

      if (pivot + 1 < right) 
       SortQuick(arr, pivot + 1, right); 
     } 
    } 

    static void Main(string[] args) 
    { 
     var watch = System.Diagnostics.Stopwatch.StartNew(); 
     Random rnd = new Random(); 

     int max = Convert.ToInt32(Console.ReadLine()); 

     int[] numbers = new int[max]; 

     for (int i = 0; i < max; i++) 
     { 

      numbers[i] = rnd.Next(-65000, 65000); 
     } 


     // the code that you want to measure comes here 






     SortQuick(numbers, 0, max - 1); 

     for (int i = 0; i < max; i++) 
      Console.WriteLine(numbers[i]); 
     watch.Stop(); 
     var elapsedMs = watch.ElapsedMilliseconds; 
     Console.WriteLine(elapsedMs); 
     Console.ReadLine(); 
    } 
} 
} 

Bublesort ................................

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace bublesort 
{ 
class Program 
{ 
    static void Main(string[] args) 
    { 
     var watch = System.Diagnostics.Stopwatch.StartNew(); 
     // the code that you want to measure comes here 

     int n = int.Parse(Console.ReadLine()); 
     int[] arr = new int[n]; 
     Random rnd = new Random(); 
     int temp = 0; 
     for (int i = 0; i < n; i++) 
     { 

      arr[i] = rnd.Next(-65000,65000); 
     } 
     for (int write = 0; write < arr.Length; write++) 
     { 
      for (int sort = 0; sort < arr.Length - 1; sort++) 
      { 
       if (arr[sort] > arr[sort + 1]) 
       { 
        temp = arr[sort + 1]; 
        arr[sort + 1] = arr[sort]; 
        arr[sort] = temp; 
       } 
      } 
     } 

     for (int i = 0; i < arr.Length; i++) 
      Console.WriteLine(arr[i]); 
     watch.Stop(); 
     var elapsedMs = watch.ElapsedMilliseconds; 
     Console.WriteLine(elapsedMs); 
    } 
} 
} 

Answer 1

如果你有你的数组中的重复，它会发生两个while循环以array [left] = array [right] = pivot结束。交换不做任何事情，既然你不增加左边和右边减少，你的快速排序将永久停留。

尝试使用长度为2和两个相等元素的数组。它会立即挂起。

另外，通过选择阵列[左]作为枢轴，则保证有序阵列最坏的情况下（二次的）行为，一旦该错误是固定的。

Answer 2

static public void Quicksort(int[] numbers, int left, int right) 
    { 
     int i = left, j = right; 
     int pivot = numbers[(left+right)/2]; 

     while (i <= j) 
     { 
      while (numbers[i] < pivot) 
      { 
       i++; 
      } 

      while (numbers[j] > pivot) 
      { 
       j--; 
      } 

      if (i <=j) 
      { 
       // Swap 
       int tmp = numbers[i]; 
       numbers[i] = numbers[j]; 
       numbers[j] = tmp; 

       i++; 
       j--; 
      } 

     } 

     // Recursive calls 
     if (left < j) 
     { 
      Quicksort(numbers, left, j); 
     } 

     if (i < right) 
     { 
      Quicksort(numbers, i, right); 
     } 
    } 

是的问题解决THX的指导做好，当我提出的枢轴的中间元件，林现在排序在间隔100种000随机元素[-65000到65000]，持续8秒。虽然布雷排序需要71秒。或者Q sort比bublesort快90％;）。