爲什麼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％;）。