JS—关于排序:冒泡、选择、归并、快排

一、冒泡排序

创新互联长期为近千家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为平度企业提供专业的成都做网站、网站设计,平度网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。

原理:相邻两元素之间两两比较,比较出大值进行赋值互换,再依次与相邻的元素比较,层层递进。#互换元素位置,相互赋值。

时间复杂度:最好O(n),最差O(n^2)

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

const bubbleSort = (arr)=>{
    for(let i = 0 ; i < arr.length - 1 ; i++){
        for(let j = 0 ; j < arr.length - 1 - i ; j++){
            if(arr[j] > arr[j + 1]){
                var temp = 0;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

解析

两个循环,当i=0的时候,里面的循环完整执行,从j=0执行到j=7,结果是将最大的数排到了最后。当i=1的时候,里面的循环再次完整执行,由于最大的数已经在最后了,没有必要去比较数组的最后两项,这也是j
二、选择排序

原理:先定义一个元素的最大值或最小值,拿每个元素与最值比较,取大值放到数组最右端,或者最小值放到数组最左端,层层比较。#互换元素下标位置,再赋值。

时间复杂度:O(n^2)

const selectionSort = (arr)=>{
    let minIndex,temp;
    for(let i = 0 ; i < arr.length ; i++){
        minIndex = i;
        for(let j = i + 1 ; j < arr.length ; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j; 
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

console.log(selectionSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]
解析
首先从原始数组中找到最小的元素,并把该元素放在数组的最前面,然后再从剩下的元素中寻找最小的元素,放在之前最小元素的后面,直到排序完毕。
minIndex始终保存着最小值的位置的索引,随着i的自增,遍历的数组长度越来越短,直到完成排序。
三、归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,
该算法采用经典的分治(divide-and-conquer)策略
(分治法将问题分(divide)成一些小的问题然后递归求解,
而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

归并排序采用的是分治的思想,首先是“分”,将一个数组反复二分为两个小数组,直到每个数组只有一个元素;其次是“治”,从最小数组开始,两两按大小顺序合并,直到并为原始数组大小,下面是图解:

“分”就是将原始数组逐次二分,直到每个数组只剩一个元素,一个元素的数组自然是有序的,所以就可以开始“治”的过程了。

时间复杂度分析:分的过程需要三步:log8 = 3,而每一步都需要遍历一次8个元素,所以8个元素共需要运行 8log8 次指令,那么对于 n 个元素,时间复杂度为 O(nlogn)。

“治”实际上是将已经有序的数组合并为更大的有序数组。那怎么做呢?就是创建一个新数组,比较left[0]和right[0] ,那个比较小就将那个的值放进新数组,然后再继续比较left[0]和right[1],或者是left[1]和right[0]。可以看出数组left,right都只需遍历一遍,所以对两个有序数组的排序的时间复杂度为O(n)。

一、递归分解

二、合并为有序数组

const mergeSort = (arr)=>{
    let len = arr.length;
    if(len < 2){
        return arr;
    }
    let mid = Math.floor(len/2);
    //拆分成两个子数组
    let left = arr.slice(0,mid);
    let right = arr.slice(mid,len);
    //递归拆分
    let mergeSortLeft = mergeSort(left);
    let mergeSortRight = mergeSort(right);
    //组合
    return merge(mergeSortLeft,mergeSortRight)
}

const merge = (left,right)=>{
    const arr1 = [];
    while(left.length && right.length){
        // 注意: 判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
        if(left[0]<=right[0]){
            //每次都要删除left或者right的第一个元素,将其加入arr1中
            arr1.push(left.shift());
        }else{
            arr1.push(right.shift());
        }
    }
    //将剩下的元素加上
    while(left.length) arr1.push(left.shift());
    while(right.length) arr1.push(right.shift());

    return arr1;
}


console.log(mergeSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

参考: https://www.cnblogs.com/lyt0207/p/.html

四、快速排序

"快速排序"的思想很简单,整个排序过程只需要三步:

(1)在数据集之中,选择一个元素作为"基准"(pivot)。

(2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。

(3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

//首先,定义一个quickSort函数,它的参数是一个数组。
const quickSort = (arr)=>{
    //然后,检查数组的元素个数,如果小于等于1,就返回。
    if(arr.length <= 1){
        return arr;
    }
    //接着,选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。
    var pivotIndex = Math.floor(arr.length / 2);
    var pivot = arr.splice(pivotIndex,1)[0];
    var left = [];
    var right = [];
    //然后,开始遍历数组,小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。
    for(let i = 0 ; i < arr.length ; i++){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    //最后,使用递归不断重复这个过程,就可以得到排序后的数组。
    return quickSort(left).concat([pivot],quickSort(right));
}

console.log(quickSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]


网站名称:JS—关于排序:冒泡、选择、归并、快排
网站地址:http://scyanting.com/article/dsojhcj.html