0

根据我拥有的材料，我正在学习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;
}
4

3 回答 3

1

没有枢轴是partitionElement。似乎这段代码总是选择序列中的第一个元素作为枢轴。该函数将在所有情况下运行，包括最坏的情况，但它会表现不佳（具有平方复杂度）。

不同的人提出了不同的选择枢轴的解决方案，但我个人喜欢这个：从考虑的区间中选择 3 个随机元素，计算它们的平均值并将其用作枢轴。

于 2013-06-20T08:33:00.173 回答
1

这个方法 partition() 有问题，例如对于 {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

于 2013-06-20T10:07:10.623 回答
1

快速排序视频

该视频以及维基百科文章应该可以解决问题。维基百科在解释排序算法方面非常棒。关于您的问题，indexPartition是rightIndex，它是 的索引partitionElement，枢轴。

于 2013-06-20T09:08:42.060 回答