C＃QuickSort递归程序不排序

我想了解一个快速排序示例。我随机生成9个数字并放入列表中。程序选择一个随机数据透视表。根据数据透视表，列表中的其他值将被放置在左侧列表或右侧列表中。然后我再次使用左侧列表和右侧调用该方法。这是我感到困惑的地方。它不完全排序9个数字。我究竟做错了什么？C＃QuickSort递归程序不排序

这是我更新的代码。现在，如果数据透视表号码与列表中的另一个数字相同，则它在返回时例如不包括在排序列表中。无序487878146，整理14678 的一段代码，我认为是造成问题的是（如果（j ==枢）继续;）

public static List<int> QuickSort(List<int> arr) 
    { 
     Random random = new Random(); 
     int i, pivot; 

     List<int> leftList = new List<int>(); 
     List<int> rightList = new List<int>(); 

     if (arr.Count > 1) 
     { 
      //pivot = random.Next(arr[0],arr[arr.Count - 1]); 
      pivot = arr[random.Next(0, arr.Count - 1)]; 
       foreach(int j in arr) 
       { 
        if (j == pivot) continue; 
        if (j <= pivot) 
         leftList.Add(j); 
        else 
         rightList.Add(j); 
       } 

      List<int> sortedLeft = QuickSort(leftList); 
      List<int> sortedRight = QuickSort(rightList); 

      List<int> tempList = new List<int>(); 
      tempList.AddRange(sortedLeft); 
      tempList.Add(pivot); 
      tempList.AddRange(sortedRight); 

      //for (i = 1; i <= leftList.Count; i++) 
      // tempList.Add(leftList[i - 1]); 
      //tempList.Add(pivot); 
      //for (i = 1; i <= rightList.Count; i++) 
      // tempList.Add(rightList[i - 1]); 


      return tempList; 
     } 
     return arr; 
    }

来源

2012-10-08 Colin Roe

你不应该创建多个'随机'对象。创建一个并重用它。虽然在这里它可能与您的实际问题无关。 –

请首先自己调试你的代码...今天早些时候也有解决同一个问题的比较 - http://stackoverflow.com/questions/12785824/what-am-i-inging-wrong-in-this-c -sharp-quicksort-algorithm –

这看起来并不像quicksort。这看起来像mergesort，但没有合并，并没有完全将每个片段精确地减半。 – Servy

你快速排序返回排序列表，所以你需要，而不是将它们合并的无序输入：

List<int> sortedLeft = QuickSort(leftList); 
List<int> sortedRight QuickSort(rightList); 

List<int> tempList = new List<int>(); 
tempList.AddRange(sortedLeft); 
tempList.Add(pivot); 
tempList.AddRange(sortedRight);

来源

2012-10-08 18:08:29 Lee

除了李的回答，你应该因为你使用的是并不一定是数组中，然后在列表中插入随机数修改支点的选择。你可以尝试像这样的事情：

pivot = arr[random.Next(0,arr.Length - 1)];

来源

2012-10-08 18:30:14

谢谢，我更新了我的代码。现在，如果数据透视表号码与列表中的另一个数字相同，则它在返回时不包括在排序列表中，例如，未分类487878146，排序14678我认为导致问题的代码段（如果（j == pivot）继续;） –

是的，但是您可以在任何您想要的列表中包含j元素。例如，而不是继续，放入一个leftList。 –

我试过并得到了一个StackOverflow异常。我所做的是计算j元素等于主元的次数。然后，当我合并列表时，我会根据计数向列表添加数据透视表，n次。有用。 –

C＃QuickSort递归程序不排序

回答

相关问题