这个在C＃中使用QuickSort算法有什么问题？
可悲的是，我也遇到了Quicksort的问题。 我和其他学生讨论了这个问题并尝试了标准的故障排除方法。 但我找不到我做错了什么……
static int partition(int[] A) { int pivot, i, j; i = 0; j = A.Length; pivot = A[i]; do { do { i++; } while (A[i] < pivot || i pivot); swap(ref A[i], ref A[j]); } while (i < j); if (i <= j) { swap(ref A[i], ref A[j]); swap(ref A[0], ref A[j]); } return j; } static void swap(ref int a, ref int b) { int aCopy = a; a = b; b = aCopy; } static int[] QuickSort(int[] A) { int s; int left = 0; int right = A.Length; int[] B, C; if (A.Length == 0 || A.Length == 1) return A; else { s = partition(A); B = new int[s]; C = new int[right - s]; for (int i = left; i < s; i++) { B[i - left] = A[i]; } for (int i = s; i < right; i++) { C[i - s] = A[i]; } QuickSort(B); QuickSort(C); return A; } } 调试器经常给我一个带有j变量的’IndexOutOfRangeException’。 我试过调整
while (A[i] < pivot || i < j);
部分。 但是这没有做任何事情（好吧，它导致了一次StackOverflowException）。
好吧，有太多的错误，比如你要交换已经交换的元素等等。 这是您的解决方案，您可以毫无错误地执行此操作，其中还包括之前的答案和评论中所述的内容。 好编码！
static int partition(int[] A) { int pivot, i, j; i = 0; j = A.Length-1; pivot = A[0]; while (i < j) { while (A[i] < pivot && i < j) { i++; } while (A[j] > pivot && j > i) { j--; } swap(ref A[i], ref A[j]); } return j; } static void swap(ref int a, ref int b) { int aCopy = a; a = b; b = aCopy; } static int[] QuickSort(int[] A) { int s; int left = 0; int right = A.Length; int[] B, C; if (A.Length == 0 || A.Length == 1) return A; else { s = partition(A); B = new int[s]; C = new int[right - s - 1]; for (int i = left; i < s; i++) { B[i - left] = A[i]; } for (int i = s + 1; i < right; i++) { C[i - s - 1] = A[i]; } B = QuickSort(B); C = QuickSort(C); for(int i = 0; i < s;i++) A[i] = B[i - left]; for (int i = s + 1; i < right; i++) { A[i] = C[i - s - 1]; } return A; } }
你有j = A.Length ，但它应该是j = A.Length - 1 （基于你正在使用的循环）。
您始终将第一个项目作为一个项目包含在枢轴下而不检查值，然后您将包括所有其他值，即使它们位于枢轴之上，只是因为i < j ，因为您使用'或'运算符（ || ）条件之间。
这个：
do { i++; } while (A[i] < pivot || i < j);
应该：
while (i < j && A[i] < pivot); { i++; }
我注意到即使段长度为2或3个元素，你仍然在尝试使用Quicksort。 当您将输入数组的大小减小到少于4个元素时，我认为您需要使用替代排序技术。 请记住，快速排序要求您将输入数组拆分为“pivot”元素和2个单独的数组，其中一个数组的所有元素都小于数据透视图，另一个数组的所有元素都大于数据透视表。 要做到这一点，输入数组必须至少有3个元素。 这可能是您的问题的根源。
这是一个使用这种技术的通用快速排序……
public delegate int CompareDlg(T thisOne, T otherOne); public class QuickSort { #region private variable to sort inplace readonly private IList itms; private CompareDlg cmp; #endregion private variable to sort inplace #region properties public CompareDlg Comparer { set { cmp = value; } get { return cmp; } } #endregion properties #region ctor private QuickSort() { } // Hide parameterless constructor /// /// Constructor, requires generic List of Ts /// where T must implement CompareTo() method... /// /// List of T elements to sort public QuickSort(IList list) : this(list, null) { } /// /// Constructor, requires generic List of Ts /// where T must implement CompareTo() method, /// And Compare method to use when sorting, /// (Overrides default CompareTo() implemented by T) ... /// /// List of T elements to sort /// Method to use to compare elements public QuickSort(IList list, CompareDlg compareDelegate) : this() { if (list.Count == 0) throw new InvalidOperationException( "Empty List passed to QuickSort."); var first = default(T); if (typeof(T).IsClass) { foreach (var t in list) if (!((first = t).Equals(default(T)))) break; if (first.Equals(default(T))) throw new InvalidOperationException( "List passed to QuickSort contains all nulls."); } if (compareDelegate == null && !(first is IComparable )) throw new InvalidOperationException(string.Format( "Type {0} does not implement IComparable<{0}>. " + "Generic Type T must either implement IComparable " + "or a comparison delegate must be provided.", typeof(T))); itms = list; cmp += compareDelegate ?? CompareDefault; } #endregion ctor #region public sort method public static void Sort(IList itms) { (new QuickSort (itms)).Sort(); } public void Sort(bool asc) { Sort(0, itms.Count - 1, asc); } public static void Sort(IList itms, CompareDlg compareDelegate) { (new QuickSort (itms, compareDelegate)).Sort(); } public void Sort() { Sort(0, itms.Count - 1, true); } /// /// Executes QuickSort algorithm /// /// Index of left-hand boundary of partition to sort /// Index of right-hand boundary of partition to sort /// private void Sort(int L, int R, bool asc) { // Call iSort (insertion-sort) if (R - L < 4) iSort(L, R); //for partitions smaller than 4 elements else { int i = (L + R) / 2, j = R - 1; // Next three lines to set upper and lower bounds if (Comparer(itms[L], itms[i]) > 0 == asc) Swap(L, i); if (Comparer(itms[L], itms[R]) > 0 == asc) Swap(L, R); if (Comparer(itms[i], itms[R]) > 0 == asc) Swap(i, R); Swap(i, j); // -------------------------------------------- var p = itms[j]; // p = itms[j] is pivot element i = L; while (true) { while (Comparer(itms[++i], p) < 0 == asc) { } while (Comparer(itms[--j], p) > 0 == asc) { } if (j < i) break; Swap(i, j); } Swap(i, R - 1); Sort(L, i, asc); // Sort Left partition Sort(i + 1, R, asc); // Sort Right partition } } private static int CompareDefault(T thisOne, T otherOne) { if(!(thisOne is IComparable )) throw new InvalidCastException( "Type must implement IComparable "); return (thisOne as IComparable ).CompareTo(otherOne); } #endregion public sort method #region private Helper methods private void Swap(int L, int R) { var t = itms[L]; itms[L] = itms[R]; itms[R] = t; } private void iSort(int L, int R) { for (var i = L; i <= R; i++) { var t = itms[i]; var j = i; while ((j > L) && Comparer(itms[j - 1], t) > 0) { itms[j] = itms[j - 1]; j--; } itms[j] = t; } } #endregion private Helper methods }