Как понять алгоритм быстрой сортировки

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

Это видео вместе с wikipedia статьи следует очистить вещи. Википедия довольно удивительна для объяснения алгоритмов сортировки. Что касается вашего вопроса, indexPartition - rightIndex, который является индексом partitionElement, стержнем.

Answer 3

Что-то не так с этим методом 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; 
}} 

ява system.compare.CompareApp