import java.util.Arrays;
class QuickSort {
public static void quickSort(int[] array, int low, int high) {
if (array.length == 0)
return;//завершить выполнение если длина массива равна 0
if (low >= high)
return;//завершить выполнение если уже нечего делить
// выбрать опорный элемент
int middle = low + (high - low) / 2;
int opora = array[middle];
// разделить на подмассивы, который больше и меньше опорного элемента
int i = low, j = high;
while (i <= j) {
while (array[i] < opora) {
i++;
}
while (array[j] > opora) {
j--;
}
if (i <= j) {//меняем местами
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
// вызов рекурсии для сортировки левой и правой части
if (low < j)
quickSort(array, low, j);
if (high > i)
quickSort(array, i, high);
}
public static void main
(String[] args
) { int[] x = { 8, 0, 4, 7, 3, 7, 10, 12, -3 };
int low = 0;
int high = x.length - 1;
quickSort(x, low, high);
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CgpjbGFzcyBRdWlja1NvcnQgewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBxdWlja1NvcnQoaW50W10gYXJyYXksIGludCBsb3csIGludCBoaWdoKSB7CiAgICAgICAgaWYgKGFycmF5Lmxlbmd0aCA9PSAwKQogICAgICAgICAgICByZXR1cm47Ly/Qt9Cw0LLQtdGA0YjQuNGC0Ywg0LLRi9C/0L7Qu9C90LXQvdC40LUg0LXRgdC70Lgg0LTQu9C40L3QsCDQvNCw0YHRgdC40LLQsCDRgNCw0LLQvdCwIDAKIAogICAgICAgIGlmIChsb3cgPj0gaGlnaCkKICAgICAgICAgICAgcmV0dXJuOy8v0LfQsNCy0LXRgNGI0LjRgtGMINCy0YvQv9C+0LvQvdC10L3QuNC1INC10YHQu9C4INGD0LbQtSDQvdC10YfQtdCz0L4g0LTQtdC70LjRgtGMCiAKICAgICAgICAvLyDQstGL0LHRgNCw0YLRjCDQvtC/0L7RgNC90YvQuSDRjdC70LXQvNC10L3RggogICAgICAgIGludCBtaWRkbGUgPSBsb3cgKyAoaGlnaCAtIGxvdykgLyAyOwogICAgICAgIGludCBvcG9yYSA9IGFycmF5W21pZGRsZV07CiAKICAgICAgICAvLyDRgNCw0LfQtNC10LvQuNGC0Ywg0L3QsCDQv9C+0LTQvNCw0YHRgdC40LLRiywg0LrQvtGC0L7RgNGL0Lkg0LHQvtC70YzRiNC1INC4INC80LXQvdGM0YjQtSDQvtC/0L7RgNC90L7Qs9C+INGN0LvQtdC80LXQvdGC0LAKICAgICAgICBpbnQgaSA9IGxvdywgaiA9IGhpZ2g7CiAgICAgICAgd2hpbGUgKGkgPD0gaikgewogICAgICAgICAgICB3aGlsZSAoYXJyYXlbaV0gPCBvcG9yYSkgewogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICB9CiAKICAgICAgICAgICAgd2hpbGUgKGFycmF5W2pdID4gb3BvcmEpIHsKICAgICAgICAgICAgICAgIGotLTsKICAgICAgICAgICAgfQogCiAgICAgICAgICAgIGlmIChpIDw9IGopIHsvL9C80LXQvdGP0LXQvCDQvNC10YHRgtCw0LzQuAogICAgICAgICAgICAgICAgaW50IHRlbXAgPSBhcnJheVtpXTsKICAgICAgICAgICAgICAgIGFycmF5W2ldID0gYXJyYXlbal07CiAgICAgICAgICAgICAgICBhcnJheVtqXSA9IHRlbXA7CiAgICAgICAgICAgICAgICBpKys7CiAgICAgICAgICAgICAgICBqLS07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAKICAgICAgICAvLyDQstGL0LfQvtCyINGA0LXQutGD0YDRgdC40Lgg0LTQu9GPINGB0L7RgNGC0LjRgNC+0LLQutC4INC70LXQstC+0Lkg0Lgg0L/RgNCw0LLQvtC5INGH0LDRgdGC0LgKICAgICAgICBpZiAobG93IDwgaikKICAgICAgICAgICAgcXVpY2tTb3J0KGFycmF5LCBsb3csIGopOwogCiAgICAgICAgaWYgKGhpZ2ggPiBpKQogICAgICAgICAgICBxdWlja1NvcnQoYXJyYXksIGksIGhpZ2gpOwogICAgfQogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludFtdIHggPSB7IDgsIDAsIDQsIDcsIDMsIDcsIDEwLCAxMiwgLTMgfTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oItCR0YvQu9C+Iik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKEFycmF5cy50b1N0cmluZyh4KSk7CiAKICAgICAgICBpbnQgbG93ID0gMDsKICAgICAgICBpbnQgaGlnaCA9IHgubGVuZ3RoIC0gMTsKIAogICAgICAgIHF1aWNrU29ydCh4LCBsb3csIGhpZ2gpOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigi0KHRgtCw0LvQviIpOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihBcnJheXMudG9TdHJpbmcoeCkpOwogICAgfQp9
Было
[8, 0, 4, 7, 3, 7, 10, 12, -3]
Стало
[-3, 0, 3, 4, 7, 7, 8, 10, 12]