当前位置:网站首页>Quick sorting (detailed illustration of single way, double way, three way)
Quick sorting (detailed illustration of single way, double way, three way)
2022-07-07 08:37:00 【S dream chasing boy】
One 、 Quick sort
Select any data of the array to be sorted as the benchmark , Traversing elements in an array . Place elements smaller than the reference value to the left of the reference value , Those greater than the reference value are placed to the right of the reference value , Put the reference value in the middle , At this time, the reference value reaches the final position . Then, the subarray on the left and the subarray on the right of the benchmark are processed in the same way , Until the interval is reduced to 1, It means that the array is ordered .
Two 、 One way sorting
Example : Given a length of 10 Array of {6,1,2,7,9,3,4,5,10,8}
The problem solving steps ;
(1) The idea of quick sorting is to put the first element of the array 6 Move to a position in the sequence M, Give Way M The elements on the left are <=6,M The right elements of are >=6; So we need to define two pointers i and j At the beginning and end of the sequence ;
(2)i Move backward in turn (i++) Move to greater than 6 The element of stops ,j Move forward (j--) Move to less than 6 The elements of , And will i,j Corresponding element exchange .
(3) according to (2) Step by step until i,j coincidence ; And because the element referred to in coincidence is 3,3<6 In exchange ; here 6 The left side of is smaller than 6,6 The right side of is larger than 6.
(4) The sequence element at this time 6 The left side of is smaller than 6, The right side is larger than 6; take 6 Repeat the left part of (1)(2)(3) Until the first element of the sequence is 1;
(5)6 The right part of is the same as the left part ;
(7) Code implementation ; from (1)~(6) It can be seen that the implementation steps have been repeated , So use recursive method .
void Quick_Sort(int *arr, int begin, int end){
if(begin > end)
return;
int tmp = arr[begin];
int i = begin;
int j = end;
while(i != j){
while(arr[j] >= tmp && j > i)
j--;
while(arr[i] <= tmp && j > i)
i++;
if(j > i){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[begin] = arr[i];
arr[i] = tmp;
Quick_Sort(arr, begin, i-1);
Quick_Sort(arr, i+1, end);
}
3、 ... and 、 Two way sorting
The quick sort algorithm mentioned before is to >v and <v Both partial elements are placed in the index value i The left part of the position pointed to , Our two-way quick sort algorithm is different , He uses two index values (i、j) Used to traverse our sequence , take <v Put the elements in the index i To the left of the position pointed to , And will be >v Put the elements in the index j To the right of the position pointed .
(1) Code implementation ;
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
private static Random random;
private QuickSort() {
}
public static <E extends Comparable<E>> void sort2ways(E[] arr) {
random = new Random();
sort2ways(arr, 0, arr.length - 1);
}
private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition2(arr, l, r);
sort2ways(arr, l, p - 1);
sort2ways(arr, p + 1, r);
}
private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r) {
// Generate [l,r] Random index between
int p = l+random.nextInt(r-l+1);
swap(arr,l,p);
// arr[l+1...i-1]<= v;arr[j+1...r]>=v
int i = l+1,j = r;
while (true){
while (i<=j && arr[i].compareTo(arr[l])<0)
i++;
while (j>=i && arr[j].compareTo(arr[l])>0)
j--;
if (i>=j)
break;
swap(arr,i,j);
i++;
j--;
}
swap(arr,l,j);
return j;
}
}
Four 、 Three way sorting
Divide the whole array into values v, Divided into less than v The area of is called smaller than area , be equal to v The area of is equal to the area and greater than v The area of is larger than the three parts of the area , In the next recursion, there is no need to deal with equal v Equal area of , Because the element equal to the area has reached the final position , For the existence of a large number equals v The three-way fast array greatly improves the efficiency .
(1) Code implementation
import java.util.*;
public class QuickSort3Ways {
// Use quick sort recursively , Yes arr[l...r] The scope of the order
private static void sort(Comparable[] arr, int l, int r){
// For small arrays , Use insert sort
if( r - l <= 15 ){
InsertionSort.sort(arr, l, r);
return;
}
// Random in arr[l...r] In the range of , Select a value as the calibration point pivot
swap( arr, l, (int)(Math.random()*(r-l+1)) + l );
Comparable v = arr[l];
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l+1; // arr[lt+1...i) == v
while( i < gt ){
if( arr[i].compareTo(v) < 0 ){
swap( arr, i, lt+1);
i ++;
lt ++;
} else if( arr[i].compareTo(v) > 0 ){
swap( arr, i, gt-1);
gt --;
} else{ // arr[i] == v
i ++;
}
}
swap( arr, l, lt );
sort(arr, l, lt-1);
sort(arr, gt, r);
}
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
边栏推荐
- MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
- MES系統,是企業生產的必要選擇
- opencv之图像分割
- Through the "last mile" of legal services for the masses, fangzheng Puhua labor and personnel law self-service consulting service platform has been frequently "praised"
- [paper reading] icml2020: can autonomous vehicles identify, recover from, and adapt to distribution shifts?
- Le système mes est un choix nécessaire pour la production de l'entreprise
- Learn how to compile basic components of rainbow from the source code
- One click deployment of highly available emqx clusters in rainbow
- 数据分片介绍
- What are the advantages of commas in conditional statements- What is the advantage of commas in a conditional statement?
猜你喜欢
随机推荐
Merge sort and non comparison sort
You should use Google related products with caution
Opencv learning notes II - basic image operations
rsync远程同步
ES6_ Arrow function
All about PDF crack, a complete solution to meet all your PDF needs
Compilation and linking of programs
[kuangbin] topic 15 digit DP
POJ - 3616 Milking Time(DP+LIS)
How to integrate app linking services in harmonyos applications
21 general principles of wiring in circuit board design_ Provided by Chengdu circuit board design
MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
Implementation method of data platform landing
【微信小程序:缓存操作】
Input and output of floating point data (C language)
Input of mathematical formula of obsidan
Laravel8 uses passport login and JWT (generate token)
IP-guard助力能源企业完善终端防泄密措施,保护机密资料安全
Go语言中,函数是一种类型
测试踩坑 - 当已有接口(或数据库表中)新增字段时,都需要注意哪些测试点?