QuickSort с значениями дубликатов

Question

Я реализовал следующий код, но, похоже, он не работает для случая, когда у моего массива есть повторяющиеся значения.

private int partition(Integer[] arr,int left, int right) 
{ 
    int i = left; 
    int j = right; 
    int pivot = arr[left]; 

    while(true) 
    { 
     while(arr[i] <pivot) i++; 
     while(arr[j] > pivot) j--; 

     if(i < j) 
     { 
      print(arr); 
      int temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
     } 
     else return j; 
    } 
} 


public void quickSort(Integer[] arr, int left,int right) 
{ 
    print(arr); 
    if(left >= right) return; 

    int index = partition(arr,left,right); 

    quickSort(arr,left,index-1); 
    quickSort(arr,index+1,right); 
} 

В этом случае я нашел несколько отличную реализацию, но я не понимаю, почему. Любая помощь будет оценена по достоинству.

private int partition(Integer[] arr, int left, int right) 
    { 
    int i = left-1; 
    int j = right+1; 
    int pivot = arr[left]; 


    while(true) 
    { 

     while(arr[++i] < pivot) ; 
     while(arr[--j] > pivot) ; 

     if(i < j) 
     { 
      print(arr); 
      int temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
     } 
     else return j; 
    } 
    } 

    public void quickSort(Integer[] arr, int left,int right) 
    { 
    print(arr); 
    if(left >= right) return; 

    int index = partition(arr,left,right); 

    quickSort(arr,left,index); 
    quickSort(arr,index+1,right); 
    } 

Answer 1

Вот ваш код:

while(arr[i] <pivot) i++; 
    while(arr[j] > pivot) j--; 

Вот что отличается в коде:

while(arr[++i] < pivot) ; 
    while(arr[--j] > pivot) ; 

Обратите внимание, что они используют оператор предварительно инкремент/декремент ++ я и - -j. Итак, первая проверка в то время будет зависеть от увеличения или уменьшения чека.

что эквивалентно наличию:

do{ i++; }while(arr[i] < pivot); 
do{ j--; }while(arr[j] > pivot); 

Пойнт, вам нужно увеличивать I и декремента J до первого сравнения.

Answer 2

1.Pick до одного элемента в качестве оси поворота

2.Move всех элементы меньше поворота налево, и всех элементов больших, чем поворот вправо

3.Apply вышеуказанных шагов на обеих частях

Следующий способ реализует быструю сортировку. Он определяет рекурсивный метод сортировки подмассивов, а также определяет способ разбиения массива на две части.

public static void quickSort(int[] data, int first, int last) 
     { 
     if (first >= last)return; 
     int pivot = partition(data, first, last); 
     quickSort(data, first, pivot - 1); // sort the left part 
     quickSort(data, pivot + 1, last); // sort the right part 
     } 

Процесс разбивки включает в себя сбор шарнира и перемещение элементов вокруг стержня. Простая процедура, как показано ниже:

1, Выделяет новый временный массив проведения разделенную результата

до 2. Выбери любой первый элемент как стержень

3.Scan массива от второго элемента, сравнить каждый элемент с шарниром, и поместить его в левый конец временного массива, если она меньше или равна оси, в противном случае положить его в правый конец.

4.Finally скопировать обратно результат из временного массива в исходном массиве

public static int partition(int[] data, int first, int last) 
{ 
int[] temp = new int[last - first + 1]; 
int pivot = data[first]; 
int i = 0, j = last - first, k; 

for (k = first + 1; k <= last; k++) 
{ 
    if (data[k] <= pivot) 
     temp[i++] = data[k]; 
    else 
     temp[j--] = data[k]; 
} 
temp[i] = data[first]; 

// Copy data back into original array 
for (k = first; k <= last; k++) 
    data[k] = temp[k - first]; 
return first + i; 
    } 

Описанный выше метод требует дополнительного хранения (линейное пространство), удерживающие промежуточный результат. Ниже приводится на месте вариант разбиения, которое не требует Addtional хранения:

1.Pick до первого элемента в массиве в качестве оси поворота

2.СКАНИРОВАНИЕ массива с обоих концов к середине

3.Всякий раз, когда два элемента нахождения на той стороне, поменять местами их

4.When сканы с обоих концов встретятся в середине, поменять стержень с этим среднего элемента

public static int partition(int[] data, int first, int last) 
{ 
int pivot = data[first]; 
int left = first, right = last; 

while (left < right) 
{ 
    // Find an element bigger than the pivot from the left 
    while (data[left] <= pivot && left < right) 
     left++; 
    // Find an element smaller than the pivot from the right 
    while (data[right] > pivot) 
     right--; 
    // Swap the two elements found 
    if (left < right) 
     swap(data, left, right); 
} 

// move the pivot element to the middle 
swap (data, first, right); 
return right; } 

1.Если поворота выбранного в каждой время является медианным элементом, тогда разделение четное, а уровень разбиения равен O (log n)

2. Если выбранная точка поворота является либо самым маленьким, либо самым большим элементом (неудача каждый раз) , то одна часть не имеет элемента, а другая часть содержит все элементы, кроме самой оси. Это будет генерировать n уровней разбиения, что по существу похоже на сортировку.

3.Если шарнир выбирается случайным образом каждый раз, то в среднем разбиение будет четным, а уровень разбиения будет близок к O (log n).

Надеет, что это может привести к правильной идее о быстрой сортировке занять некоторое время, чтобы прочитать все предоставленные комментарии в фрагментах.