我正在尝试理解一个快速排序示例。我随机生成 9 个数字并放在一个列表中。程序选择一个随机枢轴。根据透视表,列表中的其他值将放置在左侧列表或右侧列表中。然后我使用左列表和右列表再次调用该方法。这就是我感到困惑的地方。它不会完全对 9 个数字进行排序。我做错了什么?
这是我更新的代码。现在,如果一个枢轴数字与列表中的另一个数字相同,则在返回时它不会包含在排序列表中,例如未排序的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;
}
快速排序返回排序列表,因此您需要合并它们而不是未排序的输入:
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);
除了 Lee 的答案之外,您还应该修改透视选择,因为您使用的是不必在数组中的随机数,然后将其插入列表中。例如,您可以尝试这样的事情:
pivot = arr[random.Next(0,arr.Length - 1)];