js实现排序算法——插入，选择，冒泡，快排

偏执的太偏执、 2022-06-13 10:13 138阅读 0赞

这两天在学习js时，有幸阅读到了阮一峰大神的——快速排序（Quicksort）的Javascript实现。于是我想总结下简单的排序算法并通过js实现。

注明参考出处——http://www.ruanyifeng.com/blog/2011/04/quicksort\_in\_javascript.html。

# 一.插入排序 #

> 所谓插入排序，实际上工作原理就是将一个数据插入到已经排好序的有序数据中。
> 
> 如图：
> 
> ![Center][]  
> 
> 
> 具体操作如图，我遍历数组，每次比较都先对已经遍历到的数字进行排序，然后将新遍历到的数字插入已经排好序的数里。
> 
> 插入排序代码：
> 
>     var sz = [2,5,3,1,4];
>     
>     
>     //插入排序
>     console.log(
>     	function(){
>     		var sz_copy = [];
>     		for(i=0;i<sz.length;i++){
>     			if(i==0){//为什么在里面进行判断，在外面防止sz为空数组
>     				sz_copy.push(sz[i]);
>     			}else{
>     				var j=0;
>     				for(j=0;j<i;j++){
>     					if(sz[i]<sz_copy[j]){//因为前面已经从小到大排好序，当我现在这个数小于我比较的数，那么我就找到位置了,然后将数插入位置便好
>     						break;
>     					}
>     				}
>     				
>     				sz_copy.splice(j,0,sz[i]);
>     				console.log(sz_copy);
>     			}
>     		}
>     		return sz_copy;
>     	}()
>     );
> 
>   
> 
> 
> # 二.选择排序 #
> 
> 选择排序说白了就是每次去寻找数组中最大/最小的数字，当找到就将其与最后/最前的数字交换位置，然后将它移出无序数组。
> 
> 如图：
> 
> ![Center 1][]
> 
>   
> 
> 
> 代码如下：
> 
>     var sz = [5,2,3,1,4];
>     
>     
>     //选择排序
>     console.log(
>     	function(){
>     		var min_num;
>     		var min_p;
>     		for(var i=0;i<sz.length;i++){
>     			min_num = sz[i];
>     			min_p = i;
>     			for(var j=sz.length-1;j>=i;j--){
>     				if(min_num>sz[j]){//进行遍历其他无序数，发现比现在最小数还小的，记住位置。
>     					min_num = sz[j];
>     					min_p = j;
>     				}
>     			}
>     			//这是最小数，交换位置
>     			var zhong = sz[i];
>     			sz[i] = sz[min_p];
>     			sz[min_p] = zhong;
>     		}
>     		return sz;
>     	}()
>     );
> 
>   
> 
> 
> # 三.冒泡排序 #
> 
> 我其实一直觉得冒泡排序和选择排序还是有一定的相似度的，都是对数组进行多次遍历，寻找最大/最小值排除。但他们之间也是有差异的，最大的差异就是冒泡排序每一次排序过程，通过相邻元素的交换，将当前没有排好序中的最大（小）移到数组的最上（下）面。像鱼吐泡泡，泡泡向上走，遇到大泡泡就让大泡泡先上去。
> 
> 如图：
> 
> ![Center 2][]  
> 
> 
> 冒泡排序代码：
> 
>     var sz = [2,5,3,1,4];
>     
>     
>     //冒泡排序
>     console.log(
>     	function(){
>     		for(var i=0;i<sz.length-1;i++){
>     			for(var j=0;j<sz.length-i-1;j++){
>     				if(sz[j]>sz[j+1]){//让相邻数进行判断，若下面的数大于上面的数，冒泡
>     					var zhong = sz[j];
>     					sz[j] = sz[j+1];
>     					sz[j+1] = zhong;
>     				}
>     			}
>     		}
>     		return sz;
>     	}()
>     );
> 
>   
> 
> 
> # 四.快速排序 #
> 
> 这是我参照阮一峰大神写的快速排序代码，具体讲解大家可以去看下他的讲解： [点击打开链接][Link 1]
> 
> 这是我的代码：
> 
>     var arr = [85, 24, 63, 45, 47, 17, 31, 96, 50];
>     
>     console.log(function a(arr){
>     	
>     	if(arr.length<=1){
>     		return arr;
>     	}
>     
>     	//分左右
>     	var zhong_num = Math.floor(arr.length/2);//获得最接近且小于参数的值
>     	var zhong_s = arr.splice(zhong_num,1)[0];//数组去除中间值并取得它
>     	var left = [];
>     	var right = [];
>     	
>     	//装填
>     	for(var i in arr){
>     		if(arr[i]<zhong_s){
>     			left.push(arr[i]);
>     		}else{
>     			right.push(arr[i]);
>     		}
>     	}
>     	
>     	//组合
>     	return a(left).concat([zhong_s],a(right));
>     }(arr));

[Center]: /images/20220613/efe16fc19eb34d459d5e4be5ca472bde.png
[Center 1]: /images/20220613/c399c03466524f00a5d585ca9d333a97.png
[Center 2]: /images/20220613/0e6785ac9ff7416fa14c6c9812677f8d.png
[Link 1]: http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html