经典排序算法之快速排序（二分法排序）

妖狐艹你老母 2022-08-28 11:55 168阅读 0赞

### 前言 ###

> 前面两篇文章我们已经分析了经典排序算法中的冒泡排序和插入排序的思路，以及冒泡排序的优化方案。接下来我们将继续学习一个新的排序算法 - 快速排序（二分法排序）。

### 思路分析 ###

> 所谓的快速排序其实就是利用二分法加递归的原理，每次取出数组中的中间位置的值作为参照，然后再借助两个额外的数组。遍历原数组中的每个元素跟中间值（参照值）进行比较，把小于中间值的元素放在一个新数组中，相反把大于中间值的元素放在另一个新的数组中。这样一来其中一个新数组中的所有元素肯定都是小于中间值的，而另外一个新数组中的元素也必然都是大于中间值的。以此类推在把两个新的数组以同样的方式（可以采用递归）进行拆解，直到数组中只剩下一个元素为止，最后再把所有的小数组加所有的中间数再加上所有的大数组拼接在一起，就能得到我们想要的结果了。  
> 下面用一个实际例子来具体分析一下： 数组nums：\[12,1,8,10,21,25,4,30,6\]
> 
>  *  计算当前数组中的中间元素，mid：21， midIndex：4
>  *  遍历数组nums将大于21的元素放在新数组right中，小于21的则放在新数组left中，得到left:\[12,1,8,10,4,6\]，right：\[25,30\]
>  *  按照上面的方法继续将新数组left和right进行二分法拆解
>     
>      *  left数组中间值：10，left1：\[1,8,4,6\] ，right1：\[12\]（当数组中只剩一个元素时不再进行拆分）
>      *  right数组中间值：30，left2：\[25\]，right2： \[\]
>  *  现在只有left1中的元素个数还是大于1的，所以要继续拆分
>     
>      *  left1数组中间值：4，left3：\[1\]（不再拆分），right3：\[8,6\]
>  *  right3继续拆分：中间值：6，left4：\[\]，right4：\[8\]
>  *  到此已经全部拆分完毕，最后再将所有的left，mid和right合并在一起就是我们想要的结果了
>  *  下面我们用一张图片来更直观的展示一下拼接过程：  
>     ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA56yR56iL5bqP54y0_size_20_color_FFFFFF_t_70_g_se_x_16]

### 快排代码 ###

var midSort = function midSort(nums){ 
    	if(nums.length <=1) return nums;
    	let mid = Math.floor(nums.length/2),
    		midNum = nums.splice(mid,1)[0];
    	let left = [], right = [];
    	nums.forEach(item =>{ 
    		item < midNum ? left.push(item): right.push(item)
    	})
    	return midSort(left).concat(midNum,midSort(right));//利用递归对left和right数组继续拆分
    }

### 总结 ###

> 本文我们学习了经典排序算法中的快排法，该算法相对于冒泡和插入排序效率要高一些，但依然不算是最优算法。  
> 欢迎喜欢的老铁点赞，评论，加关注哦。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA56yR56iL5bqP54y0_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/75b09dd6ffee410b9cf3b0092c100442.png