递归排序：快速排序语法

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

简单来说，Hoare 快速排序的工作原理是：

有一组数据
选择一些中间元素
逻辑上将数组分为3类：
- 中间元素左侧的所有内容 - 我们将其称为下半部分
- 中间元素
- 中间元素右侧的所有内容 - 我们将其称为上半部分
记住中间元素的值
从下段的最左边开始寻找大于中间元素的值，或者换句话说，它试图找到不应该在下段的东西，因为它太大了
当它找到一个时，它会从上部分的右侧开始寻找“对于上部分来说太小”的元素
如果找到满足这些条件的值，它们将被交换
这种情况反复发生，直到对下部来说太大的所有东西都转移到上部，对上部来说太小的东西都转移到下部
结果是一个“部分排序”的数组；中间元素左边的东西都比它小，中间元素右边的东西都比它大
算法重新开始，这次只将下半部分视为整个数组，然后对上半部分进行相同处理
通过取整体，然后将其减半，然后四分之一，然后......你到达一个点，你只需确保对一堆对或单个元素进行排序，然后就完成了

您的算法混合使用了 Hoare 和 Lomuto 分区策略，但更像是 Lomuto。根据数据容器的工作方式，有多种分区策略（选择如何将数组划分为多个部分）（Hoare 的策略需要可以随机访问或从每一端访问的容器，如双链表，Lomuto 只需要一个在一个方向上可读的数据容器）但是快速排序的基本算法是这样的概念，你将所有东西分成两堆“想要更小的值”和“想要更大的值”，在两堆之间反复交换东西直到“更小”和“更大” ”真的是真的，然后先对较小的一堆，然后对较大的一堆再做一遍这个过程。如果你继续前进并划分工作，那么你就会达到一切都井井有条的地步。

如果您仍在为此苦苦挣扎，不妨考虑一下：如果您将其视为对大量仅使用字符 A 和 Z 的单词进行排序，然后按字母顺序排序，您可能有一种将所有内容都放在一起的策略成堆：2 堆以 A 开头的那些和以 Z 开头的那些。然后你做 4 堆，那些以 AA、AZ、ZA 和 ZZ 开头的。然后你移动到 8 堆三个字母 AAA、AAZ、AZA、AZZ、ZAA、ZAZ、ZZA 和 ZZZ（如果你现在睡着了，这可能是合适的）。这也是一种“分而治之”的策略；你会达到这样一个点，你把一堆堆分开了，每堆只包含一个东西，然后如果你按顺序堆起来（如果你在放置它们时很小心，它们就会排列整齐) 然后它们被排序

哦，你的代码有一个错误，你在 if 后添加了一个分号，这会创建一个空语句（使 if 无用），而且你似乎也没有使用临时数组随身携带。就像这个算法希望混合两种不同的排序策略但未完成

递归排序：快速排序语法

Recursive Sorting: quick sort syntax

java

syntax

syntax-error

quicksort