Алгоритм Quick Sort является одним из самых быстрых алгоритмов сортировки. Его среднее время выполнения - O(n log n). Quick Sort реализуется с помощью рекурсии. В этой статье представлен демонстрационный пример алгоритма быстрой сортировки на Java. Суть алгоритма заключается в следующем. Берется некоторый элемент массива (желательно рандомом, чтобы алгоритм выполнялся приблизительно одинаковые промежутки времени для любых наборов данных).

 

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

А вот собственно и реализация на Java:

import java.util.Random;

           

public class QuickSortExample {

    public static int ARRAY_LENGTH = 30;

    private static int[] array = new int[ARRAY_LENGTH];

    private static Random generator = new Random();

           

    public static void initArray() {

        for (int i=0; i

            array[i] = generator.nextInt(100);

        }

    }

           

    public static void printArray() {

        for (int i=0; i

            System.out.print(array[i] + “, ”);

        }

        System.out.println(array[ARRAY_LENGTH-1]);

    }

           

    public static void quickSort() {

        int startIndex = 0;

        int endIndex = ARRAY_LENGTH - 1;

        doSort(startIndex, endIndex);

    }

           

    private static void doSort(int start, int end) {

        if (start >= end)

            return;

        int i = start, j = end;

        int cur = i - (i - j) / 2;

        while (i < j) {

            while (i < cur && (array[i] <= array[cur])) {

                i++;

            }

            while (j > cur && (array[cur] <= array[j])) {

                j–;

            }

            if (i < j) {

                int temp = array[i];

                array[i] = array[j];

                array[j] = temp;

                if (i == cur)

                    cur = j;

                else if (j == cur)

                    cur = i;

            }

        }

        doSort(start, cur);

        doSort(cur+1, end);

    }

           

    public static void main(String[] args) {

        initArray();

        printArray();

        quickSort();

        printArray();

    }

}

Данная программа работает правильно, но наверняка ее можно немного оптимизировать.