js 实现排序算法

╰半橙微兮° 2024-02-17 18:22 45阅读 0赞

## 一、JS实现冒泡排序 ##

*  冒泡排序应该算是排序算法中最简单的一种，它的思路也特别的简单，主要有以下四步：  
    
    
     *  1、从第一个元素开始，比较相邻的元素一对元素
     *  2、如果前面的元素比后面的元素要大，则两者进行交换，下面示例的代码中，交换使用了一个中间变量，交换变量的办法不只一种可自行去实现
     *  3、在一轮遍历之后，最大的一个元素一定会被移动到了末尾
     *  4、重复上述的步骤，我们就能逐个地将剩余元素中的最大的值慢慢向后移动，直到遍历完成，排序也就完成了！

##### 下面是冒泡排序的JS代码的实现 #####

#### 冒泡排序的时间复杂度为O(n^2) ####

## 二、JS实现快速排序 ##

*  快速排序是使得最为广泛的一种排序算法，速度也较快,下面主要介绍一下快速排序的基本思路：  
    
    
     *  1、在要排序的元素中选择一个元素作为基准，基准可以任意选择，但是为了方便理解，基准一般来说都会选择位于中间的元素
     *  2、选取了基准之后，按照给出的要排序的元素的顺序，让第个元素分别与基准进行比较，比基准大的元素放在基准的右边，比基准小的元素放在基准的左边，这样就形成了左右的两个子集。
     *  3、接下对第二步形成的两个子集序列分别递归地执行步骤一和步骤二，直到所有的子集只剩下一个元素为止。

##### 下面是JS代码对快速排序的实现 #####

//声明要排序的数组
                var array = [34,45,83,98,24,4,45,78,32];
                //定义排序函数
                var quickSort = function(array){
        
                //检查数组的元素个数，如果小于或者等于1就返回
                if(array.length <= 1){
                    return array;
                }
                // 选取中间的元素作为基准
                var pivotIndex = Math.floor(array.length/2);
    
                /*将中间的元素从数组中分离出来，
    下面删除的是从第四个位置开始 的一个元素，为24，该方法的返回值为一个数组，即下面的array.splice(pivotIndex,1)返回的是删除的24，
    以数组的形式返回，返回的是[24]所以要分离出24需要在后面加上[0],如下所示*/
                var pivot = array.splice(pivotIndex,1)[0];
                //定义两个空数组用来存放一左一右两个子集
                var left = [];
                var right = [];
                //开始遍历数组，小于基准的放入左边的子集，大于基准的放入右边的子集
                for(var i=0;i<array.length;i++){
                    if(array[i] < pivot){
                        left.push(array[i]);
                    }else{
                        right.push(array[i]);
                    }
                }
                //最后使用递归来不断地重复此过程即可以得到排序完成后的数组
    
                    return quickSort(left).concat([pivot],quickSort(right));
            }
            var result = quickSort(array);
            console.log(result);

#### 快速排序的时间复杂度为：平均情况下快速排序的时间复杂度是O(nlgn)，最坏情况是O(n^2) ####