# 递归排序：快速排序语法 go评论17阅读模式

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

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

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 • 本文由 发表于 2020年8月2日 12:20:35
• 转载请务必保留本文链接：https://go.coder-hub.com/63212350.html
• java
• quicksort
• syntax
• syntax-error