js 实现常见排序算法

朴灿烈づ我的快乐病毒、 2023-06-08 12:00 23阅读 0赞

传送门：[算法可视化工具][Link 1]

### 文章目录 ###

*  冒泡排序
 *  选择排序
 *  插入排序
 *  合并排序
 *  快速排序
 *  原生排序

为了方便说明，默认按从小到大排序

# 冒泡排序 #

> 基本思路：  
> 1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数  
> 2.对除了最后一个之外的数重复第一步，直到只剩一个数  
> ![在这里插入图片描述][format_png]

代码如下：

# 选择排序 #

> 基本思路：  
> 1.找出最小的数，和第一个交换位置  
> 2.在剩下的数中，找出最二小的数，放在第二个  
> 3.依次类推，排出顺序  
> ![在这里插入图片描述][format_png 1]

代码如下：

# 插入排序 #

> 基本思路：  
> 1.把数组分为\[已排序\]和\[未排序\]两部分,第一个数为\[已排序\]，其余为\[未排序\]  
> 2.从\[未排序\]抽出第一个数，和\[已排序\]部分比较，插入到合适的位置  
> ![在这里插入图片描述][format_png 2]

代码如下：

# 合并排序 #

> 基本思路：  
> 1.不断将数组对半分，直到每个数组只有一个  
> 2.将分出来的部分重新合并  
> 3.合并的时候按顺序排列  
> ![在这里插入图片描述][format_png 3]

代码如下：

// 被拆分的数组重新合并
    function merge(left, right) { 
        var result = [],
            left_index = 0,
            right_index = 0;
    
        // 将两个数组合并
        // 合并的时候按从小到大的顺序
        while (left_index < left.length && right_index < right.length) { 
            if (left[left_index] < right[right_index]) { 
                result.push(left[left_index++]);
            } else { 
                result.push(right[right_index++]);
            }
        }
    
        // 和其他数组拼接
        return result.concat(left.slice(left_index)).concat(right.slice(right_index));
    }
    
    function mergeSort(myArray) { 
        // 只有一个数的时候退出递归
        if (myArray.length < 2) { 
            return myArray;
        }
    
        var middle = Math.floor(myArray.length / 2),
            left = myArray.slice(0, middle),
            right = myArray.slice(middle);
    
        // 递归
        // 不断拆分只到一个数组只有一个数
        return merge(arguments.callee(left), arguments.callee(right));
    }

# 快速排序 #

> 基本思路：  
> 1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边  
> 2.再按此方法对这两部分数据分别进行快速排序（递归进行）  
> 3.不能再分后退出递归，并重新将数组合并  
> ![在这里插入图片描述][format_png 4]

代码如下：

# 原生排序 #

myArray.sort(function(a,b){ 
    	return a-b
    })

[Link 1]: https://visualgo.net/zh/sorting?slide=1
[format_png]: /images/20230531/8fdc9993dddf4f1e8089b8bb43d33adf.png
[format_png 1]: /images/20230531/bdda7943fb5f4df0bf54867c493c5921.png
[format_png 2]: /images/20230531/888ae14e24e64557ae9219b69b1b9be3.png
[format_png 3]: /images/20230531/4902f5bccc8d4d43b74fb77427935dc4.png
[format_png 4]: /images/20230531/266a60d2851a419aa67061e026c5b2bc.png