Quick sorting is to find an element (originally you can find one) as the reference (pivot), and then partition the array so that the value of the element on the left of the reference is not greater than the reference value, and the value of the element on the right of the reference is not less than the reference value. , the elements used as the benchmark are adjusted to the correct position after sorting. Recursively quick sort, adjust the other n-1 elements to the correct position after sorting. Finally, each element is in the correct position after sorting and the sorting is completed. Therefore, the core algorithm of the quick sorting algorithm is partitioning operation, that is, how to adjust the position of the benchmark and adjust the final position of the return benchmark in order to divide and conquer recursion.
The algorithm for quick sorting is:
1) Set two variables i and j, when the sorting starts: i=0, j=N-1;
2) Use the first array element as the key data and assign it to the key, that is, key=A[0];
3) Start from j to search forward, that is, start from behind to search forward (j--), find the first value A[j] smaller than key, and swap A[j] and A[i];
4) Start from i to search backward, that is, start from front to backward (i++), find the first A[i] larger than the key, and swap A[i] and A[j];
5) Repeat steps 3 and 4 until i=j; (In steps 3, 4, no value that meets the conditions is found, that is, when A[j] in 3 is not less than key, and A[i] in 4 is not greater than key Change the values of j and i so that j=j-1, i=i+1 until it is found. Find the value that meets the conditions and when exchanging, the position of the j pointer remains unchanged. In addition, the i==j The process must be exactly when i+ or j- is completed, and the loop ends at this time).
Let me give you an example, this may not be easy to understand. Assume that the sequence to be sorted is
The code copy is as follows:
package com.zc.manythread;
import java.util.Random;
/**
* Quick sort
* @author Administrator
*
*/
public class QSort {
int [] date;
public QSort(int[] date) {
this.date=date;
}
/**
* Exchange function
* @param a
* @param i
* @param j
*/
private void swap(int a[],int i,int j) {
int T;
T=a[i];
a[i]=a[j];
a[j]=T;
}
/***************************
* Sort function
* @param a
* @param lo0
* @param hi0
* @return
*/
int[] QuickSort(int a[],int lo0,int hi0){//The method of division and treatment is to divide the array into A[lo0..q-1] and A[q+1..hi0]
int lo=lo0;
int hi=hi0;
int mid;
if (hi0>lo0) {
mid=a[(hi0+lo0)/2];
while(lo<=hi){
while((lo<hi0)&&(a[lo]<mid)) ++lo;
while((hi>lo0)&&(a[hi]>mid)) --hi;
if (lo<=hi) {
swap(a,lo,hi);
++lo;
--hi;
}
}
if (lo0<hi) {
QuickSort(a, lo0, hi);
}
if (lo<hi0) {
QuickSort(a, lo, hi0);
}
}
return a;
}
/******************
*
* Create duplicate array data
**********************/
private static int[] createDate(int count) {
int[] data=new int[count];
for (int i = 0; i < data.length; i++) {
data[i]=(int)(Math.random()*count);
}
return data;
}
/**
* No duplicate array data
* @param count
* @return
*/
private static int[] createDate1(int count) {
int[] data=new int[count];
Random rand = new Random();
boolean[] bool = new boolean[100];
int num = 0;
for (int i = 0; i < count; i++) {
do {
// If the generated number is the same, continue to loop
num = rand.nextInt(100);
} while (bool[num]);
bool[num] = true;
data[i]=num;
}
return data;
}
/************Main function*********************/
public static void main(String[] args) {
final int count=10;
int[] data=createDate1(count);
for (int n:data) {
System.out.print(n+"/t");
}
QSort data1=new QSort(data);
System.out.println();
int[] a=data1.QuickSort(data,0, count-1);
for (int n:a) {
System.out.print(n+"/t");
}
}
}
The results are as follows:
The above is all the content described in this article. I hope you can like it.