乐趣区

冒泡排序快速排序的JavaScript实现

这篇文章会介绍几种经典的排序算法思想和它们的 javaScript 实现。
一:冒泡排序
冒泡排序的核心思想是“比较”,即通过比较相邻元素的大小,从而实现从小到大或者从大到小的排序。下面我们以一个最终为从小到大的排序来理解一下冒泡排序的实现思路:

1:从坐标为 0 的元素开始,比较相邻的两个元素,大的元素放在小的元素后面,直到数组的最后 2 个元素比较完,这算一个循环。这一轮循环之后,最大的元素会在数组的最后边,但是前面的元素依然是混乱的。

2:依然是从坐标为 0 的元素开始依次两两比较,直到数组的倒数第二个和倒数第三个这一组比较成。这一轮完成在以后,第二大的元素会在倒数第二的位置,前面的元素依然是混乱的。

从上面的 2 点,我们可以看出冒泡排序的思路是:
1: 第一趟把最大的元素挪到数组的最后一个
2: 第二趟把第二大的元素放到数组的倒数第二个
3: 以此类推。每次都是从数组的第 0 个元素开始两两比较,但是每一趟需要比较的次数依次减 1,因为在上一轮里面最大的元素已经在数组的最右边。

当我们已经想清楚了算法的思想,具体到代码实现的时候,我们就需要 2 个变量:
1: 一个变量i,表示需要循环多少趟比较,它的最大值为数组的个数减 1
2: 一个变量j,表示在每一趟里需要比较的次数。每一趟里面它都是从 0 开始,但是每一趟里面它的最大值会随着趟数的增加依次减 1

下面来看一下代码实现。下面是一个从小到大排序的实现。我们打印了每一对元素比较之后的临时数组,可以清楚地看到数组是怎样随着 i 和 j 的变化从而一步步变成有序数组的:

function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {console.log("=================");
        console.log(`i: ${i}`);
        for (let j = 0; j < len - 1 - i; j++) {console.log(`j: ${j}`);
            if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 利用 ES6 的解构特性,交换相邻两个元素
            }
            console.log(`arr: ${arr}`);
        }

    }
    return arr;
}

bubbleSort([5, 4, 3, 2, 1]);

下面是打印信息:

=================
i: 0
j: 0
arr: 4,5,3,2,1
j: 1
arr: 4,3,5,2,1
j: 2
arr: 4,3,2,5,1
j: 3
arr: 4,3,2,1,5
=================
i: 1
j: 0
arr: 3,4,2,1,5
j: 1
arr: 3,2,4,1,5
j: 2
arr: 3,2,1,4,5
=================
i: 2
j: 0
arr: 2,3,1,4,5
j: 1
arr: 2,1,3,4,5
=================
i: 3
j: 0
arr: 1,2,3,4,5    

二:快速排序

退出移动版