当前位置:网站首页>Quick sort
Quick sort
2022-07-06 04:36:00 【A distant youth】
The basic idea of quick sorting : Separate the records to be arranged into two independent parts by one sorting , The keywords of one part of the records are smaller than those of the other part , Then the two parts of records can be sorted separately , To get the whole sequence in order .
6.1 Algorithm description
Fast sorting uses divide and conquer to put a string (list) It's divided into two strings (sub-lists). The specific algorithm is described as follows :
- Pick a member of the sequence , be called “ The benchmark ”(pivot);
- Reorder the sequence , All elements smaller than the base value are placed in front of the base value , All elements that are larger than the base value are placed after the base value ( The same number can go to either side ). After the partition exits , The benchmark is in the middle of the sequence . This is called a partition (partition) operation ;
- recursively (recursive) Sort the substrings of elements that are less than the base value and elements that are greater than the base value .
6.2 Dynamic diagram demonstration
6.3 Code implementation
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // Partition operation
var pivot = left, // Set reference value (pivot)
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
边栏推荐
- Understanding of processes, threads, coroutines, synchronization, asynchrony, blocking, non blocking, concurrency, parallelism, and serialization
- Uva1592 Database
- 【HBZ分享】云数据库如何定位慢查询
- Visio draw fan
- CertBot 更新证书失败解决
- Hashlimit rate control
- Redis —— Redis In Action —— Redis 实战—— 实战篇一 —— 基于 Redis 的短信登录功能 —— Redis + Token 的共享 session 应用— 有代码
- How does computer nail adjust sound
- How to realize automatic playback of H5 video
- Database - MySQL storage engine (deadlock)
猜你喜欢
Lora gateway Ethernet transmission
Cross domain and jsonp details
Solve the compilation problem of "c2001: line breaks in constants"
CADD course learning (8) -- virtual screening of Compound Library
Comprehensive ability evaluation system
When debugging after pycharm remote server is connected, trying to add breakpoint to file that does not exist: /data appears_ sda/d:/segmentation
Mlapi series - 04 - network variables and network serialization [network synchronization]
Dry goods collection | Vulkan game engine video tutorial
解决“C2001:常量中有换行符“编译问题
The implementation of the maize negotiable digital warehouse receipt standard will speed up the asset digitization process of the industry
随机推荐
拉格朗日插值法
捷码赋能案例:专业培训、技术支撑,多措并举推动毕业生搭建智慧校园毕设系统
Easyrecovery reliable and toll free data recovery computer software
2/13 review Backpack + monotonic queue variant
One question per day (Mathematics)
Basic explanation of turtle module - draw curve
Understanding of processes, threads, coroutines, synchronization, asynchrony, blocking, non blocking, concurrency, parallelism, and serialization
QML和QWidget混合开发(初探)
Yyds dry goods inventory OSI & tcp/ip
【HBZ分享】云数据库如何定位慢查询
How does vs change the project type?
Recommendation system (IX) PNN model (product based neural networks)
CADD course learning (7) -- Simulation of target and small molecule interaction (flexible docking autodock)
【Try to Hack】john哈希破解工具
满足多元需求:捷码打造3大一站式开发套餐,助力高效开发
. Net interprocess communication
[Zhao Yuqiang] deploy kubernetes cluster with binary package
[Yu Yue education] reference materials of complex variable function and integral transformation of Northwestern Polytechnic University
2328. 网格图中递增路径的数目(记忆化搜索)
Visio draw fan