JavaScript排序算法

2021-05-12

3分钟阅读时长

冒泡排序

基础

思路：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

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

备注：
每次都从第一个元素开始比较，所以i和j都是从0开始的。是每次都会在数组最后多一个已经排好了序的元素。

优化

优化方向：

每次循环最大的元素都会被放到最后，因此下一次循环可以不再比较这些元素。
当某次循环中没有任何元素进行互换时，说明排序已经完成，不必再进行接下来的循环。

function optimizedBubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        let swapped = false;
        for (var j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

插入排序

将第一个待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

function insertionSort(arr){
    if(arr.length==1){
        return arr;
    }else{
        for(var i=1;i<arr.length;i++){
            for(var j=0;j<i;j++){
                if(arr[j]>=arr[i]){
                    var temp=arr[i];
                    arr.splice(i,1);
                    arr.splice(j,0,temp);
                }
            }
        }   
        return arr;
    }
}

选择排序

在未排序序列中找到最小（大）元素，与未排序序列的第一个元素进行互换。即，放到了已排序序列的末端。
再从剩余未排序元素中继续寻找最小（大）元素，与未排序序列的第一个元素进行互换。
重复第二步，直到所有元素均排序完毕。

function selectionSort(arr){
    for(var i=0;i<arr.length-1;i++){
        // 记录未排序序列的第一个元素位置
        let currentIndex=i;
        let min=arr[currentIndex];
        let minIndex=currentIndex;
        // 从未排序序列中找到最小元素并记录其位置
        for(var j=i+1;j<arr.length;j++){
            if(arr[j]<min){
                minIndex=j;
                min=arr[j];
            }
        }
        // 交换未排序序列的第一个元素和最小元素
        let temp=arr[minIndex];
        arr[minIndex]=arr[currentIndex];
        arr[currentIndex]=temp;
    }
}

快速排序

随机选取数组中的一个数作为基数pivot（可以简单地选择最后一个元素）
将比pivot大的元素全部移到pivot左边，比pivot大的元素全部移到pivot的右边。以选取最后一个元素为pivot为例。
- 使用下标i记录分界线：在i之前（包括i）的元素的值都小于pivot，在i之后的元素是大于等于pivot元素和未分类元素
- 使用j记录当前检查的未分类元素：在j之前的元素都已被分类
- 即，i之前（包括i）是比pivot小的元素，在i和j（不包括j）之间是比pivot大的元素，在j之后（包括j）是未分类的元素
- 当j的元素小于pivot时，这个元素应该被放到比pivot小的元素序列的末尾。因此，将j处元素与i+1处元素进行互换，并且i++。此时的i又指向了比pivot小的元素序列的末尾
- 当j的元素大于等于pivot时，这个元素本来就应该在i的右边，所以不需要进行更多操作。此时j++，继续将下一个元素分类
- 当j==r，即j已经扫描到了pivot所在位置时，pivot之前的元素都已经被分类，大小界限之分是在i和i+1之间。此时，将pivot值与i+1处值进行交换，使得pivot值的左边的值都比它小，右边的值都比它大。本次分类结束。
再对原pivot左边的序列和右边的序列都进行分类操作。
当需要被分类的序列的长度小于等于1时，分类操作结束。

这是分治的思想。

function quickSort(arr, l, r) {
    if (l >= r) {
        return;
    } else {
        p = partition(arr, l, r);
        // 当原pivot没有被换到第一个或第二个元素处
        // 否则没有左边需要被排序
        if (p > 1) {
            quickSort(arr, l, p - 1);
        }
        // 当原pivot没有被换到倒数第一个或倒数第二个元素处
        // 否则没有右边需要被排序
        if (p < arr.length - 2) {
            quickSort(arr, p + 1, r);

        }
    }
}

function partition(arr, l, r) {
    // 选择最后一个元素作为本次的pivot
    let pivot = arr[r];
    let i = l - 1;
    for (var j = l; j < r; j++) {
        if (arr[j] < pivot) {
            i++;
            let temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    let temp = pivot;
    arr[r] = arr[i + 1];
    arr[i + 1] = temp;
    return i + 1;
}

下一页 JavaScript数组操作方法

本页内容