如何理解快速排序算法

Question

根据我所掌握的材料，我正在用java学习快速排序。最好的情况是枢轴是中间的，最坏的情况是枢轴的一侧总是空的。

对于下面的代码，是"indexPartition“枢轴？，您在下面的函数中放置了什么样的参数，以便在最坏的情况下运行？

    private void quickSortSegment(E[] list, int start, int end)
{
  if (end-start>1) 
  { 
     int indexPartition = partition(list, start, end);
     quickSortSegment(list, start, indexPartition);
     quickSortSegment(list, indexPartition+1, end);
  }
}

private int partition(E[] list, int start, int end)
{
  E temp; 
  E partitionElement = list[start];
  int leftIndex = start; 
  int rightIndex = end-1;
  while (leftIndex<rightIndex)
  {  
    while (list[leftIndex].compareTo(partitionElement) <= 0 && leftIndex<rightIndex)
    {
        leftIndex++; 
    }
    while (list[rightIndex].compareTo(partitionElement) > 0)
    {
        rightIndex--; 
    }
     if (leftIndex<rightIndex)
     {  
        temp = list[leftIndex];
        list[leftIndex] = list[rightIndex];
        list[rightIndex] = temp;
     }
  }
  list[start] = list[rightIndex];
  list[rightIndex] = partitionElement;
  return rightIndex;
}

Answer 1

不，枢轴是partitionElement。这段代码似乎总是选择序列中的第一个元素作为支点。该函数在所有情况下都会运行，包括最坏的情况，但是它的性能会很差(具有平方复杂性)。

不同的人对于选择支点提出了不同的解决方案，但我个人喜欢这个方案:从考虑的区间中选择3个随机元素，计算它们的平均值，并以此作为支点。

Answer 2

​

​

这段视频连同维基百科的文章应该会澄清一些事情。维基百科在解释排序算法方面非常棒。关于您的问题，indexPartition是rightIndex，它是partitionElement的索引，是支点。

Answer 3

这个方法分区()有什么问题，例如，对于{3,1,2}，我们将得到{1,3,2}：

public class CompareApp {
public static void main(String... args) {
    Integer[] arr = {3, 1, 2};
    quickSortSegment(arr, 0, 2);
    for (Integer i : arr) System.out.println(i);
}

private static <E extends Comparable> void quickSortSegment(E[] list, int start, int end) {
    if (end - start > 1) {
        int indexPartition = partition(list, start, end);
        quickSortSegment(list, start, indexPartition);
        quickSortSegment(list, indexPartition + 1, end);
    }
}


private static <E extends Comparable> int partition(E[] list, int start, int end) {
    E temp;
    E partitionElement = list[start];
    int leftIndex = start;
    int rightIndex = end - 1;
    while (leftIndex < rightIndex) {
        while (list[leftIndex].compareTo(partitionElement) <= 0 && leftIndex < rightIndex) {
            leftIndex++;
        }
        while (list[rightIndex].compareTo(partitionElement) > 0) {
            rightIndex--;
        }
        if (leftIndex < rightIndex) {
            temp = list[leftIndex];
            list[leftIndex] = list[rightIndex];
            list[rightIndex] = temp;
        }
    }
    list[start] = list[rightIndex];
    list[rightIndex] = partitionElement;
    return rightIndex;
}}

java system.compare.CompareApp

1 3 2