JS数组排序

比眉伴天荒 2022-11-09 12:58 125阅读 0赞

## 一、冒泡排序 ##

**1、比较相邻的两个元素，如果前一个比后一个大，则交换位置。  
2、比较完第一轮的时候，最后一个元素是最大的元素。  
3、这时候最后一个元素是最大的，所以最后一个元素就不需要参与比较大小。**

## 二、快速排序 ##

**  第一次排序的时候将数据分成两个部分，一部分比另外一部分所有的数据都要小，然后递归调用，在两边都实行快速排序。**

**  第一种**

function quick(arr) {
      if(arr.legth<1) return arr
      let centerIndex = Math.floor(arr.length/2)
      let centerValue = arr.splice(centerIndex,1)[0]
      let left = []
      let right = []
      for (let i = 0; i < arr.length; i++) {
        if(arr[i]<centerValue){
          left.push(arr[i])
        }else{
          rigth.push(arr[i])
        }   
      }
      return quick(left).concat([center,quick(rigth)])
    }

> 缺点：
> 
> 1、基数用的是splice()函数取，而不是算法中常用的取下标。基数只是一个参照对象，在比对的时候，只要能从数组中取到即可，所以只需要知道它的索引即可，调用函数删除基数只会更耗时；
> 
> 2、根据基数来划分时，R专门生成两个数组来存储，从而占用了更多的存储空间（增加了空间复杂度）。

** 第二种**

1、通过下标取中间数为基数；

2、从起点往后寻找比基数大的，记录为下标 i；再从终点往前寻找比基数小的，记录为下标 j，当 i <= j时，原地交换数值；

3、重复步骤2，直到遍历所有元素，并记录遍历的最后一个下标 i，以此下标为分界线，分为左右两边，分别重复步骤1~3实现递归排序；

// 快排改进——黄佳新
        var devide_Xin = function (array, start, end) {
            if(start >= end) return array;
            var baseIndex = Math.floor((start + end) / 2), // 基数索引
                 i = start,
                 j = end;
    
            while (i <= j) {
                while (array[i] < array[baseIndex]) {
                    i++;
                }
                while (array[j] > array[baseIndex])  {
                    j--;
                }
    
                if(i <= j) {
                    var temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    i++;
                    j--;
                }
            }
            return i;
        }
    
        var quickSort_Xin = function (array, start, end) {
            if(array.length < 1) {
                return array;
            }
            var index = devide_Xin(array, start, end);
            if(start < index -1) {
                quickSort_Xin(array, start, index - 1);
            }
            if(end > index) {
                quickSort_Xin(array, index, end);
            }
    
            return array;
        }

**总结：**

> 1、用下标取基数，只有一个赋值操作，跟快；
> 
> 2、原地交换，不需要新建多余的数组容器存储被划分的数据，节省存储；