Data Structure ----- Quick Sort

​
​​
​​

活动地址：CSDN21天学习挑战赛

一、快速排序

1.1 概念

快速排序Is modified by the bubble sort,Although it is modified by the bubble sort,But in what sort thought there is no inevitable connection,Only belong to the same交换排序;
Quick sort sorting thought is a basic value through partition,And then will be ordered a big split into small order,Then an ordered sequence points until a;

1.2 查找过程

• Quick sort the sort of thinking the first thing to do is take a benchmark to compare,We here every sort of the first element as a comparing benchmark;
• 由下图我们可以看到,In the first round of the sort we take 9 作为基准值,Then use all remaining elements compared with the,如果比 9 要小,Will the elements placed in 9 的左方,如果比 9 要大,Will the elements placed in 9 的右边;
• All round sorted,The basic value we use has reached its final location,So this value is no longer need to participate in order;
• According to the previous round of selected benchmark,We are in the left sort again,The right sort also similarly again;
• According to the above rules constantly partition,Until the entire sequence in order after the order is over;

1.3 代码演示

1.3.1

• Will need to sort the sequence in the array;
• 建立一个方法,将数组传入、The starting coordinates incoming、Coordinates incoming;

1.3.2

• Basic value will pass an auxiliary space;
• Copy the starting coordinates and end coordinates a used to traverse the;

1.3.3

• According to the basic value of the first order;
• From the right point point traverse forward,Until a basic value is less than to find the elements,And the value assigned to the left of the anchor point;（Because the leftmost element is as the basic value of,Have copies within the secondary variables,所以可以直接替换掉）
• Right after the traverse from the anchor point of the left again traverse back,Until a basic value is greater than to find the elements,And the element assignment to the anchor point on the right;
• Until the left positioning coordinates, eventually not less than the right positioning coordinates,一次循环结束,Then the position of the benchmark values into the two coordinate intersection;（ Jump out of the loop of the final condition is left positioning coordinates is equal to the right location coordinates ）

1.3.4

• Join two recursive around to sorting interval to the same way;

1.3.5

• When the initial positioning coordinates, not less than the finish location coordinates,Is unable to sort,直接返回;

1.4 代码测试

1. At the end of each round sorting add an output traversal sequence;
2. Through the sequence of each round we can see the entire sorting process;
3. 结论：代码可用无误;

1.5 代码分享

public class test {

public static void main(String[] args) {

int[] arr = {
 15 ,20 , 14 , 21 ,12 , 9 , 16 , 18 , 10 };
celerity(arr,0,arr.length-1);
System.out.println("Eventually produce orderly sequence to：");
for ( int e: arr ) {

System.out.print( e + " ");
}
}
private static void celerity(int[] arr,int left,int right) {

if ( left >= right )
return;
int temp = arr[left];
int i = left,j = right;
while ( i < j ){

while ( temp <= arr[j] && j > i )
j--;
arr[i] = arr[j];
while ( temp >= arr[i] && j > i )
i++;
arr[j] = arr[i];
}
arr[i] = temp;
celerity(arr,left,i-1);
celerity(arr,i+1,right);
}
}