Рекурсивная сортировка: синтаксис быстрой сортировки

Question

Программы должны отсортировать набор чисел с помощью быстрой сортировки. Используйте наборы данных, начинающиеся с 10 000 000 случайно сгенерированных чисел. Я изучал быструю сортировку. Другой: я закончил сортировку слиянием. Однако быстрая сортировка - это синтаксис. Не знаю, почему это синтаксис.

    public static void main(String[] args)throws Exception{
        for(int n = 1; n<=100; n++)
        {// begin for
            int size = 10000000; //change this num to change the size of the random array 10,000,000

            int[] a = new int[size];
            int[] temp = new int[a.length]; //temporary array, it's empty.

            //fill the array with random integers
            for(int i = 0; i< a.length; i++)
                a[i] = (int)(Math.random()*100000 + 1);

            long startTime = System.nanoTime();

            quickSort(a, temp, 0,(a.length - 1));

            long endTime = System.nanoTime();

            long duration = endTime - startTime;

            System.out.printf("%12.8f %n", (double)duration/100000000);


        }// End for
    }// end main

    public static void quickSort(int[] a, int[] temp, int startIndex, int endIndex)
    {// begin quickSort
        int pivotIndex; //the index of pivot returned by the quciksort partition

        if(startIndex < endIndex)
        {//Begin if
            pivotIndex = partition(a, temp, startIndex, endIndex);

            quickSort(a, temp, startIndex, pivotIndex -1);
            quickSort(a, temp, pivotIndex+1, endIndex);
        }//End if
    }//end quickSort

    public static int partition(int[] a, int[] temp, int startIndex, int endIndex) {
        int pivotIndex;
        int pivot;
        int midIndex = startIndex;

        pivotIndex = (startIndex + endIndex) / 2;
        pivot = a[pivotIndex];

        swap(a, temp, pivotIndex, endIndex);

        for (int i = startIndex; i < endIndex; i++) {
            if (a[i] < pivot) ;
            {
                swap(a, temp, i, midIndex);
                midIndex = midIndex + 1;
            }
        }
        swap(a, temp, midIndex, endIndex);
        return midIndex;
    }// end partition

    public  static void swap(int[]a, int[]temp, int first, int second)
    {//Begin swap
        for(int i = first; i <= second; i++){
            temp[i] = a[i];
        }
        int c;

        c = a[first];
        a[first] = a[second];
        a[second] = c;
    }//End swap

    public static void writeLines(int[] a, String fileName) throws Exception
    {  // Begin writeLines(int[] a, String fileName)

        // create a File class object with the given file name
        java.io.File out = new java.io.File(fileName);
        // Create a PrintWriter output stream and link it to the File object
        java.io.PrintWriter outfile = new java.io.PrintWriter(out);

        // write the elements of an int array, separated by spaces
        for (int i = 0; i < a.length; i++)
        {   // Begin for (int i = 0; i < a.length; i++)

            outfile.print(a[i] + " ");

        }   // End for (int i = 0; i < a.length; i++)

        // print a newline at the end of the list of integers

        outfile.println();

        outfile.close();

    } // End writeLines(int[] a, String fileName) throws Exception


}//end quickSORT

У меня есть синтаксис. Он сказал quick.partition и quick.quickSort.

Answer 1

Проще говоря, быстрая сортировка Хоара работает следующим образом:

• имея массив данных
• выбирая некоторый средний элемент
• логически разделяя массив на 3 категории:
  • все, что находится слева от среднего элемента - мы назовем это нижней частью
  • средним элементом
  • все, что находится справа от среднего элемента - мы назовите это верхним разделом
• запоминая значение в среднем элементе
• , начиная с самого левого края нижнего раздела, ища значение, которое больше среднего элемента , или, другими словами, он пытается найти что-то, чего не должно быть в нижнем разделе, потому что он слишком большой
• , когда он находит его, он начинает с правой стороны верхнего раздела в поисках элемента, который "слишком мало для верхней части"
• , если найдены значения, соответствующие этим критериям, они меняются местами на
• , это происходит неоднократно, пока все, что i s слишком большой для нижней части был перенесен в верхнюю часть, а все слишком маленькое для верхней части было перенесено в нижнюю часть
• в результате получился «частично отсортированный» массив; все, что слева от среднего элемента, меньше его, и все, что справа от среднего элемента, больше его
• алгоритм начинается заново, на этот раз обрабатывая только нижнюю часть, как если бы это был весь массив , затем он делает то же самое с верхней частью
• , беря целое, затем делите его пополам, затем четверть, затем ... вы достигаете точки, в которой просто проверяете, что группа пар или отдельные элементы сортируются, и затем все готово.

Ваш алгоритм использует что-то вроде смеси стратегий разделения Хоара и Ломуто, но в основном больше похоже на Ломуто. Существуют различные стратегии разделения (выбор способа разделения массива на разделы) в зависимости от того, как работает контейнер данных (стратегия Хоара требует наличия контейнеров, к которым можно произвольно обращаться или к которым можно получить доступ с каждого конца, например, список с двойной связью, Ломуто нужен только контейнер данных для чтения в одном направлении), но алгоритм быстрой сортировки basi c состоит в том, что вы разбиваете все на две стопки: «хотите меньшие значения» и «хотите большие значения», постоянно меняя местами между стопками, пока не станет «меньше» и "больше" действительно верно, затем повторите процесс сначала с меньшей кучей, затем с большей кучей. Если вы продолжите и разделите работу, то вы достигнете точки, где все будет рассортировано.

Если вы все еще боретесь с этим, возможно, вместо этого подумайте: если вы думаете об этом как о сортировке большого количества слов, которые используйте только символы A и Z, в алфавитном порядке у вас может быть стратегия размещения всего в стопки: 2 стопки из тех, которые начинаются с A, и тех, которые начинаются с Z. Затем вы делаете 4 стопки, те, которые начинаются с AA, AZ, ZA и ZZ. Затем вы переходите к 8 стопкам из трех букв AAA, AAZ, AZA, AZZ, ZAA, ZAZ, ZZA и ZZZ (что, вероятно, уместно, если вы уже спите ?). Это тоже стратегия «разделяй и властвуй»; вы достигнете точки, когда вы разделили стопки так, что каждая из них содержит только одну вещь, тогда, если вы собираете стопки по порядку (и если вы были осторожны, когда вы их разложили, они уже будут в порядке ), то они сортируются

О, и в вашем коде есть ошибка в том, что вы добавили точку с запятой после if, которая создает пустой оператор (делает if бесполезным), и вы также не кажетесь использовать временный массив, который вы носите с собой. Это похоже на то, что al go надеялся стать смесью двух разных стратегий сортировки, но это незаконченный