Как функционирует алгоритм quicksort?

У меня есть этот класс, который осуществляет метод распоряжения quicksort, но у меня не остается ясным. Как дело в том, что он упорядочивает стоимость?

public class QuickSortClass {
    public static void quickSort(int[] vector, int izquierda, int derecha) {
        int pivote = vector[izquierda];
        int i = izquierda;
        int j = derecha;
        int auxIntercambio;
        while (i < j) {
            while (vector[i] <= pivote && i < j) {
                i++;
            }
            while (vector[j] > pivote) {
                j--;
            }
            if (i < j) {
                auxIntercambio = vector[i];
                vector[i] = vector[j];
                vector[j] = auxIntercambio;
            }
        }
        vector[izquierda] = vector[j];
        vector[j] = pivote;
        if (izquierda < j - 1) {
            quickSort(vector, izquierda, j - 1);
        }
        if (j + 1 < derecha) {
            quickSort(vector, j + 1, derecha);
        }
    }

    public static void main(String[] args) {
        int[] numeros = new int[40];
        Random rnd = new Random();
        System.out.println("Vector desordenado");
        for (int i = 0; i < numeros.length; i++) {
            numeros[i] = rnd.nextInt(50);
            System.out.print(numeros[i] + " ");
        }   
        QuickSortClass.quickSort(numeros, 0, numeros.length - 1);
        System.out.println("\nVector Ordenado");
        for (int n : numeros) {
            System.out.print(n + " ");
        }

    }
}
6
задан 15.04.2016, 17:15
3 ответа

Алгоритм quicksort часть очень простой концепции. Понимая, что у тебя есть договоренность A:

  1. Ты помещаешь в элементе A [i] где 0 <i <длина A. Этот элемент будет шарниром
  2. Размещать все элементы A [j]> В [i] в верхних будках или "в правую сторону" A [i], в то время как все элементы A [k] <В [i] они размещаются в нижних будках или "в левую сторону" A [i]. Равные элементы могут быть в Вашу правую сторону или левую сторону. Очень вероятно, что шарнир изменяет место, чтобы удовлетворять эти условия, а именно, стоимость i будьте изменены.
  3. После реализованные изменения, имеется A1, что является подмножеством A с A [0] до A [i-1] и A2, что является подмножеством A [i+1] до A [длина A - 1]. Применять этот процесс для A1 и A2.

Это объясняется очень хорошо в оживлении Wikipedia.

introducir la descripción de la imagen aquí
Из-за en:User:RolandH, CC BY-SA 3.0, https://commons.wikimedia.org / ватт / index.php? curid=1965827

Давайте видеть, как код, что ты снабжаешь в твоем вопросе, соответствует осуществлению алгоритма:

public static void quickSort(int[] vector, int izquierda, int derecha) {
    //1. Elegir el pivote
    int pivote = vector[izquierda];
    //2. Los elementos > al pivote van a su derecha, los < a su izquierda
    //esta parte de la implementación es el corazón del ordenamiento
    //se utilizan variables auxiliares:
    //- i para controlar los elementos a la izquierda del pivote
    //- j para controlar los elementos a la derecha del pivote
    int i = izquierda;
    int j = derecha;
    //esta variable debería tener un alcance menor pero se respeta la implementación
    int auxIntercambio;
    //mientras que deban evaluarse los elementos en el arreglo
    //para ubicar al nuevo pivote
    while (i < j) {
        //mientras que el elemento vector[i] sea menor o igual al pivote
        //se aumenta el valor de i
        //cuando este loop se detenga, el elemento en vector[i]
        //es mayor a pivote y deberá ir a su derecha
        while (vector[i] <= pivote && i < j) {
            i++;
        }
        //mientras que el elemento vector[j] sea mayor al pivote
        //se desminuye el valor de j
        //cuando este loop se detenga, el elemento en vector[j]
        //es menor o igual a pivote y deberá ir a su izquierda
        while (vector[j] > pivote) {
            j--;
        }
        //siempre y cuando i sea menor a j, se hace un cambio de los elementos
        //puesto que el elemento en vector[i] debe ir a la derecha
        //y vector[j] a la izquierda
        if (i < j) {
            //nota: auxIntercambio podría estar declarada aquí ya que NO tiene otro alcance
            auxIntercambio = vector[i];
            vector[i] = vector[j];
            vector[j] = auxIntercambio;
        }
    }
    //Por los ciclos anteriores, j llegó a una posición donde su elemento (i.e. vector[j]) 
    //es menor o igual al pivote, actualizamos entonces la posición del pivote, mandando vector[j] 
    //a la ubicación del pivote y viceversa (el pivote a la posicion vector[j])
    vector[izquierda] = vector[j];
    vector[j] = pivote;
    //3. Para A1 y A2, aplicar el mismo proceso.
    if (izquierda < j - 1) {
        //quicksort aplicado a A1
        quickSort(vector, izquierda, j - 1);
    }
    if (j + 1 < derecha) {
        //quicksort aplicado a A2
        quickSort(vector, j + 1, derecha);
    }
}
13
ответ дан 24.11.2019, 14:35

Стратегия этого алгоритма "дели и ты завоюешь", вместо того, чтобы стараться упорядочивать единственный большой список, он отделяет ее несколько раз в более маленьких частично аккуратных списках до тех пор, пока у тебя нет списки единственного элемента, который уже находится в правильном положении. Это яснее с примером:

Имея неряшливый начальный вектор

[5, 1, 3, 9, 6, 10, 2, 8, 4, 7]

Он разделяется на две части, беря элемент произвольного способа (обычно элемент способа)

[5, 1, 3, 9, 6] [10, 2, 8, 4, 7]

Сейчас используя отборную стоимость (шарнир) "6", мы двигаем каждое меньшее или равное что-нибудь в этом роде в левой стороне и чем-нибудь в этом роде, превосходящем правую сторону

[5, 1, 3, 4, 2, 6] [10, 9, 8, 7]

Этот процесс повторяется из-за каждого субсписка

[5, 1, 3][4, 2, 6] | [10, 9][8, 7]

[2, 1, 3][4, 5, 6] | [8, 7, 9] [10]

[2, 1][3] | [4, 5][6] | [8, 7][9] | [10]

[1][2] | [3] | [4][5] | [6] | [7][8] | [9] | [10]

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

2
ответ дан 24.11.2019, 14:35

Ну, чтобы видеть, мы будем предполагать, что у нас есть следующий array целых чисел:

int[] numeros = { 20, 35, 10, 15, 25, 30 }; // Desordenado.

Алгоритм quicksort начинает тем, что 'вмещается' как главная стоимость показывая в параметре, мы будем предполагать, что это первый, 20.

Реализуй поиски левой стороны в правую сторону и найди 35, как верхний узел и реализуй поиски правой стороны в левую сторону и найди 15 как меньший узел.

Он обменивается ими и продолжает поиски с новыми изменениями:

int[] numeros = { 20, 15, 10, 35, 25, 30 }

Исходя из этой точки, array остается разделенным на 2 subarrays, из которых они пройдут по тому же процессу до тех пор, пока он не будет регулирующим несовершеннолетнего в больший.

Результат:

int[] numeros = { 10, 15, 20, 25, 30, 35 } // Ordenado

Рекомендуемое, позвонив, в нее оно функционирует состоит в том, чтобы давать промежуточную стоимость, медиану.

Для большей информации, поскольку они оставили тебя в каком-то комментарии:

Ссылка в Wikipedia: Quicksort

Ссылка в Algolist: Quicksort

Ссылка в PuntoComEsUnLenguage: Quicksort (где я основывался, чтобы отвечать тебе)

1
ответ дан 24.11.2019, 14:35
  • 1
    Я не понимаю c и # 243; mo это отвечает на вопрос: c и # 243; mo дело в том, что c и # 243; я говорю, что он упорядочивает стоимость –  15.04.2016, 17:48