Быстрая сортировка по массиву - PullRequest
Новая
       4

Быстрая сортировка по массиву

0 голосов
/ 01 ноября 2019

У меня есть массив A = | 0,535 | 0,960 | 0,750 | 0,750 | 0,151 | 0,001 | 0,981 | 0,327 | 0,111 |

Я принял ось 0,535

Я поменял местами A [1] = 0,960 с A [8] = 0,111, чтобы получить

A = | 0,535 | 0,111 | 0,750 |0,750 | 0,151 | 0,001 | 0,981 | 0,327 | 0,960 |

Затем я поменялся местами A [2] = 0,750 с A [7] = 0,327, чтобы получить

A = | 0,535 | 0,111 | 0,327 | 0,750 | 0,151 | 0,001| 0,981 | 0,750 | 0,960 |

Теперь я не понимаю, что делать дальше (0,75 по сравнению с 0,75), поскольку значения 0,151 меньше, чем пивот, а 0,981 больше, чем пивот. Может ли кто-нибудь, пожалуйста, вести меня?

1 Ответ

0 голосов
/ 05 ноября 2019

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

    function qsort(x, lo, hi) {
      var i, p;
      if (lo >= hi) {
          return;
      }
      p = lo;
      for (i = lo + 1; i <= hi; i++) {
        if (x[i] < x[lo]) {
            swap(x, ++p, i);

         }
      }
    swap(x, lo, p);
    qsort(x, lo, p - 1);
    qsort(x, p + 1, hi);
    }

Как вы сказали, вы получаете 0,535 в качестве пивота на первом шаге, он пройдет через ваши элементы из второго элемента (из пивота), и если он будет меньше, чем выбранный пивот,он изменит позицию этого элемента со вторым элементом, если он найдет второй элемент меньше, он изменит его с позицией третьего элемента и так далее. В конце он изменит позицию оси с помощью позиции = общее количество элементов, которое было больше, чем. Таким образом, после выбора 0,535 массив будет выглядеть так:

[0,111, 0,151, 0,001, 0,327, 0,535, 0,75, 0,981, 0,75, 0,96].

И после этого пивот будет 0,111 итогда массив будет иметь вид:

[0,001, 0,111, 0,151, 0,327, 0,535, 0,75, 0,981, 0,75, 0,96].

снова pivot = 0,151 и массив:

[0,001, 0,111, 0,151, 0,327, 0,535, 0,75, 0,981, 0,75, 0,96]

, снова поворот = 0,75 и массив:

[0,001, 0,111, 0,151, 0,327, 0,535,0,75, 0,981, 0,75, 0,96]

снова пивот = 0,981 и массив:

[0,001, 0,111, 0,151, 0,327, 0,535, 0,75, 0,96, 0,75, 0,981]

снова pivot = 0,96 и массив:

[0,001, 0,111, 0,151, 0,327, 0,535, 0,75, 0,75, 0,96, 0,981]

...