递归排序:快速排序语法

huangapple go评论60阅读模式
英文:

Recursive Sorting: quick sort syntax

问题

以下是您要翻译的代码部分:

public class qucikSORT {
    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

我已为您提供代码的中文翻译。如果您有任何其他问题或需要进一步帮助,请随时告诉我。

英文:

The programs should sort a set of a number using a quick sort. Use Data Sets Starting at 10,000,000 randomly generated numbers. I've been learning about quicksort. Another, I finished merge sort. However, the quicksort is syntax. I don't know why it's syntax.

    public static void main(String[] args)throws Exception{
for(int n = 1; n&lt;=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&#39;s empty.
//fill the array with random integers
for(int i = 0; i&lt; 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(&quot;%12.8f %n&quot;, (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 &lt; 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 &lt; endIndex; i++) {
if (a[i] &lt; 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 &lt;= 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 &lt; a.length; i++)
{	// Begin for (int i = 0; i &lt; a.length; i++)
outfile.print(a[i] + &quot; &quot;);
}   // End for (int i = 0; i &lt; 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

I got syntax. It said quick.partition and quick.quickSort.

答案1

得分: 0

简而言之,Hoare的快速排序的工作原理如下:

  • 有一个数据数组
  • 选择某个中间元素
  • 逻辑上将数组分为三个部分:
    • 中间元素左边的所有内容 - 我们将其称为下部分
    • 中间元素
    • 中间元素右边的所有内容 - 我们将其称为上部分
  • 记住中间元素的值
  • 从下部分的最左边开始寻找一个大于中间元素的值,或者换句话说,它试图找到不应该在下部分的值,因为它太大了
  • 当找到一个这样的值时,从上部分的最右边开始寻找一个“对于上部分来说太小”的元素
  • 如果找到满足这些条件的值,它们会被交换
  • 这个过程重复进行,直到所有对于下部分来说太大的元素都被转移到上部分,对于上部分来说太小的元素都被转移到下部分
  • 结果是一个“部分排序”的数组;中间元素左边的所有内容都比它小,中间元素右边的所有内容都比它大
  • 算法重新开始,这次只将下部分视为整个数组,然后再对上部分执行相同的操作
  • 通过取整个数组,然后将其分成两半,然后分成四分,然后...你最终会达到一个只包含一堆成对或单个元素已排序的点,然后就完成了

你的算法在分区策略上使用了类似于Hoare和Lomuto分区策略的混合,但更像是Lomuto。根据数据容器的工作方式(Hoare的策略需要能够随机访问或从两端访问的容器,如双向链表,Lomuto只需要数据容器在一个方向上可读),有各种各样的分区策略可供选择,但快速排序的基本算法是将所有东西分成两堆,“希望更小的值”和“希望更大的值”,在堆之间反复交换东西,直到“更小”和“更大”确实成立,然后首先对较小的堆进行相同的过程,然后对较大的堆进行相同的过程。如果继续分割工作,最终会达到一切都已排序的点。

如果你仍然对此感到困惑,也许可以考虑以下方式:如果你将其视为将大量仅使用字符A和Z的单词按字母顺序排序,你可以采用以下策略:将所有东西分成两堆,以A开头的和以Z开头的。然后,你将有4堆,以AA,AZ,ZA和ZZ开头的。然后,你将转移到8堆,其中包含三个字母AAA,AAZ,AZA,AZZ,ZAA,ZAZ,ZZA和ZZZ(如果你现在已经入睡了,这可能是合适的 🤪)。 这也是一种“分而治之”的策略;你会达到一个只包含一件事物的点,然后如果你按顺序收集这些堆(如果你在放置它们时小心,它们将已经按顺序排列),它们将会被排序。

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

英文:

In simple terms, Hoare's quicksort works by:

  • having an array of data
  • picking some middle element
  • logically dividing the array into 3 categories:
    • everything to the left of the middle element - we'll call this the lower section
    • the middle element
    • everything to the right of the middle element - we'll call this the upper section
  • remembering the value at the middle element
  • starting from the very left of the lower section looking for a value that is greater than the middle element, or in other words it tries to find something that shouldn't be in the lower section because it is too big
  • when it finds one it starts from the right hand side of the upper section looking for an element that is "too small for the upper section"
  • if values are found that meet these criteria, they're swapped over
  • this happens repeatedly until everything that is too big for the lower section has been transferred into the upper section and everything too small for the upper section has been transferred into the lower section
  • the result is a "partly sorted" array; everything to the left of the middle element is smaller than it and everything to the right of the middle element is larger than it
  • the algorithm starts over, this time treating just the lower section as if it was the entire array, then it does the same with the upper section
  • by taking the whole, then halving it, then quartering it, then... you reach a point where you're just making sure that a bunch of pairs or single elements are sorted, and then that's all done

Your algorithm uses something like a mix of the Hoare and Lomuto partitioning strategies but mostly more like Lomuto. There are various strategies for partitioning (choosing how to divide the array into sections) depending on things like how the data container works (Hoare's strategy requires containers that can be randomly accessed or accessed from each end, like a double linked list, Lomuto only needs a data container to be readable in one direction) but quicksort's basic algorithm is this notion that you split everything into two piles of "want smaller values" and "want larger values", swap things repeatedly between the piles until "smaller" and "larger" really is true, then do the process again first to the smaller pile, then the larger pile. If you keep going and dividing the work then you reach a point where everything is sorted.

If you're still struggling with it, maybe consider instead: If you think of it like sorting a large amount of words that only use the characters A and Z, into alphabetical order you might have a strategy of putting everything into piles: 2 piles of those that start with A and those that start with Z. Then you make 4 piles, those that start AA, AZ, ZA and ZZ. Then you move to 8 piles of three letters AAA, AAZ, AZA, AZZ, ZAA, ZAZ, ZZA and ZZZ (which is probably appropriate if you're asleep by now 🤪). This is also a "divide and conquer strategy"; you'll reach a point where you've divided the piles so much that they each only contain one thing, then if you gather piles up in order (and if you've been careful when you laid them out they will already be in order) then they are sorted

Oh, and your code has an error in that you've added a semicolon after an if, which creates an empty statement (makes the if useless), and you also don't seem to use the temp array you carry around. It's like this algo was hoping to be a blend of two different sort strategies but is unfinished

huangapple
  • 本文由 发表于 2020年8月2日 12:20:35
  • 转载请务必保留本文链接:https://go.coder-hub.com/63212350.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定