爲什麼我的鏈表快速排序的實現比陣列慢得多？

我一直算法的問題，需要我執行快速排序算法的鏈表和數組。
我已經完成了這兩個部分，算法正在工作，但似乎我的快速排序鏈接列表實現中有一些錯誤。爲什麼我的鏈表快速排序的實現比陣列慢得多？

這是我的快速排序鏈接列表實現。

public static void SortLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    { 
     if(low != null && low !=high) 
     { 
      DataList.Node p = _PartitionLinkedList(items, low, high); 
      SortLinkedList(items, low, p); 
      SortLinkedList(items, p.Next(), null); 
     } 


    } 

    private static DataList.Node _PartitionLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    { 
     DataList.Node pivot = low; 
     DataList.Node i = low; 
     for (DataList.Node j = i.Next(); j != high; j=j.Next()) 
     { 
      if (j.Value().CompareTo(pivot.Value()) <= 0) 
      { 

       items.Swap(i.Next(),j); 
       i = i.Next(); 

      } 
     } 
     items.Swap(pivot, i); 
     return i; 
    }

這裏是快速排序的數組實現

public static void SortData(DataArray items, int low, int high) 
    { 
     if (low < high) 
     { 
      int pi = _PartitionData(items, low, high); 
      SortData(items, low, pi - 1); 
      SortData(items, pi + 1, high); 
     } 

    } 
static int _PartitionData(DataArray arr, int low, int high) 
    { 
     double pivot = arr[high]; 
     int i = (low - 1); 
     for (int j = low; j <= high - 1; j++) 
     { 
      if (arr[j].CompareTo(pivot)<=0) 
      { 
       i++; 
       arr.Swap(i,j); 
      } 
     } 
     arr.Swap(i + 1, high); 
     return i + 1; 
    }

這裏是快速排序數組和鏈表的性能。（左邊n，右邊的時間）
Picture
正如你所看到的qs鏈接列表花費了10分鐘來排序6400個元素。我不認爲它的正常..

另外我不認爲它因爲數據結構，因爲我使用相同的結構選擇排序和性能的鏈接列表和數組是相似的。

GitHub回購萬一我忘記提供一些代碼。 Repo

來源

2017-03-07 InvGhostt

鏈接列表實現可能會比較慢，因爲...什麼是大O符號中的數組和隨機鏈表的隨機元素訪問時間？「並且鏈接列表和數組的表現都相似」 - 這應該是一個令人擔憂的跡象，因爲它們不可以。無論如何 - 分析你的代碼。分析器是告訴你爲什麼有些緩慢。 – zerkms

所以你認爲它的正常，鏈表實現是如此之慢。對於鏈表，它需要超過10分鐘，對於數組，甚至不到一秒。 – InvGhostt

「所以你認爲鏈表的實現速度慢得多。」 ---回答你需要分析你的代碼。就Big-O而言，實現鏈表和基於數組的例子的複雜性是什麼？然後，再次 - 探查器。 – zerkms

對於6400個元素，10分鐘是很長的時間。它通常需要2或3個可怕的錯誤，而不僅僅是一個。

不幸的是，我只看到一個可怕的錯誤：您的第二個遞歸調用SortLinkedList(items, p.Next(), null);一直到列表的末尾。你的意思是停止在high。

這可能佔了10分鐘，但似乎有點不太可能。

即使在修復了上述錯誤之後，它仍然看起來像您的排序不正確 - 請務必測試輸出！

來源

2017-03-08 03:01:16

我會看看你的鏈表，特別是交換方法。除非我們看到鏈表的實現，否則我認爲問題區域在那裏。

你有使用鏈接列表的原因嗎？他們有o（n）搜索，這使得quicksort n^2lg（n）排序。

執行此操作的另一種方法是將鏈接列表中的所有項添加到列表中，對列表進行排序並重新創建鏈接列表。 List.Sort（）使用快速排序。

public static void SortLinkedList(DataList items) 
{ 
    list<object> actualList = new list<object>(); 

    for (DataList.Node j = i.Next(); j != null; j=j.Next()) 
    { 
     list.add(j.Value()); 
    } 

    actualList.Sort(); 

    items.Clear(); 
    for (int i = 0; i < actualList.Count;i++) 
    { 
     items.Add(actualList[i]); 
    } 
}

來源

2017-03-07 22:19:20

我正在使用鏈接列表，因爲它的要求使用它，我不能讓你建議這個解決方法。這裏是鏈接列表的實現https://github.com/arnas/tempalg/blob/master/MyDataList.cs – InvGhostt

對鏈接列表的快速排序通常與對數組的快速排序略有不同。使用第一個節點的數據值作爲樞軸值。然後代碼創建3個列表，其中一個用於值<數據透視表，一個用於值==數據透視表，一個用於值>數據透視表。然後它執行遞歸調用<數據透視表和>數據透視表。當遞歸調用返回時，這3個列表現在已經排序，所以代碼只需要連接3個列表。

爲了加快鏈表的連接，跟蹤指向最後一個節點的指針。爲了簡化這一點，使用循環列表，並使用指向最後一個節點的指針作爲訪問列表的主要方式。這使附加（加入）列表更簡單（不掃描）。一旦進入一個函數，使用last-> next命令來得到一個指向列表的第一個節點的指針。

最糟糕的兩種數據模式已經是排序數據或已經是反向排序的數據。如果使用帶有指向最後一個節點方法的循環列表，則可以使用最後和第一個節點的平均值作爲2的中值，這可能有所幫助（注意節點==樞軸的列表最終可能爲空）。

最壞情況的時間複雜度是O（n^2）。最差情況下的堆棧使用是O（n）。可以通過在列表<數據透視表和列表>數據透視表中的較小者上使用遞歸來減少堆疊使用。返回後，現在排序的較小列表將與列表==數據庫連接並保存在第四個列表中。然後，排序過程將迭代剩餘的未排序列表，然後合併（或可能加入）與已保存的列表。

使用任何方法（包括bottom up merge sort）排序鏈接列表比將鏈接列表移動到數組，排序數組，然後從排序數組創建鏈接列表要慢。然而，我描述的快速排序方法將比使用帶有鏈表的陣列導向算法快得多。

來源

2017-03-08 05:51:39 rcgldr

爲什麼我的鏈表快速排序的實現比陣列慢得多？

回答

相關問題