Three methods of quick sorting

Catalog

1. hoare Law

2.  Excavation method

3. Front and back pointer method

---

1. hoare Law

Quick sort is Hoare On 1962 A binary tree structure of the exchange sort method , Let's first introduce the method he created .

Methods and steps ：

1. Select the leftmost part of the array ( Far right ) As a benchmark key

2. From the right ( From the left ) Start screening , On the right ( From the left ) Select less than key Number of numbers

3. Then from the left ( From the right ) Start selecting greater than key Number of numbers

4. Exchange the two

5. Repeat the above cycle , Until the left and right meet

There is a difficulty here ： Why do we choose the left as the benchmark? We should start from the right ？

Because starting from the right can ensure that the number of the last meeting place is less than key Of , This will satisfy the final result ： The left is smaller than key, The right side is larger than key

The code implementation is as follows ：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
//hoare edition  
int Partition2(int*a,int left,int right){
	int key=left; // From the far left  
	while(left<right){
		// Start from the right  
		while(left<right&&a[right]>=a[key]){// Find the one on the right that is less than a[key] Value  
			right--;
		}
		while(left<right&&a[left]<=a[key]){ // Find the one on the left a[key] Value  
			left++;
		}
		swap(a,left,right); // Exchange when you find it 
	} 
	swap(a,left,key);  // Finally, the reference number and the meeting point are exchanged , Return to the meeting point 
	return left; 
} 
void QuickSort(int*a,int left,int right){
	if(right<=left){ // There is only one element in the array , Or the array does not exist 
		return;
	} 
		// After a single sequence pivot Is the final location  
		int pivot=Partition3(a,left,right);
		// Using the idea of partition  
		QuickSort(a,left,pivot-1);
		QuickSort(a,pivot+1,right);
	
}

2.  Excavation method

Pit digging method is an updated version of quick sorting .

Implementation steps ：

1. Based on the leftmost number key, And keep its data .

2. It can be seen that the position of the reference number is empty , Then start from the far right and look for less than key The number of is placed in this pit .

3. When you find the right number to place the left pit , Then there is one more pit on the right , Then start from the left and find one larger than key Put the number in this pit .

4. Repeat the above steps , Until the left and right finally meet .

Code implementation ：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
int Partition(int*a,int left,int right){
	// Excavation method  
    int key=a[left];
    // Dig a hole  
    int pit=left; // Start selecting the pit position left
	while(left<right){
		while(left<right&&a[right]>=key){ // Find less than key Number of numbers 
			right--;
		}
		if(left<right){
			a[pit]=a[right];// Fill in the pit 
			pit=right; // The pit becomes right Location 
		}
		while(left<right&&a[left]<=key){ // Find greater than key Number of numbers 
			left++;
		} 
		if(left<right){  // Empathy 
			a[pit]=a[left];
			pit=left;
		}
	} 
	a[pit]=key; // The last pit is left==right The location of 
	return pit;
}

  Local variables are used pit Make the code more readable , What is the compact version ？

// Quick sort  
int Partition(int*a,int left,int right){
	// Excavation method  
    int key=a[left];
	while(left<right){
		while(left<right&&a[right]>=key){
			right--;
		}
		if(left<right){
			a[left]=a[right]
		}
		while(left<right&&a[left]<=key){
			left++;
		}
		if(left<right){
			a[right]=a[left]
		}
	} 
    a[left]=key;
	return left;
	
}

It's not here pit Variable , The code is more concise .

3. Front and back pointer method

It is the same as the excavation method and is also an updated version .

Implementation steps ：

1. Use the pointer prev Point to the first position , The pointer cur Point to the next position .

2. When cur The data referred to is not less than key when ,cur Pointer backward

3. When cur The data referred to is less than key,prev The pointer moves back and coincides with cur Pointer for data exchange , then cur Move backward .

4. Repeat the above operation , until cur Out of bounds .

The code implementation is as follows ：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
int Partition3(int*a,int left,int right){
	int key=a[left];// Benchmark number  
	int prev=left;// Point to the first  
	int cur=1+left;// Point to the next position  
	int temp=0; 
	while(cur<=right){
		// If prev Next door neighbor cur, Exchange is meaningless  
		if(a[cur]<key&&a[++prev]!=a[cur]){
			swap(a,cur,prev);
		}
		cur++; //cur Move backward 
	}
	swap(a,left,prev);// In exchange for prev and left The location of  
	return prev;// return prev 
}

Why to be cur Less than key And make sure that prev+1!=cur Just exchange ？

Because when prev Next door neighbor cur when , It indicates that there is no greater than... Between the two pointers key The data of , No need for self exchange

When prev+1!=cur when , It indicates that there is more than between the two pointers key The data of , When prev+1 Found greater than key Number of numbers , Follow cur Refers to less than key The exchange of the number of is less than key On the left , Greater than key It's on the right .

until cur Greater than right, Then it indicates that there is no less than key Number of numbers , Will prev And left swapping , complete Less than key On the left , Greater than key It's on the right .