1. 排序算法
在生活中,我们离不开排序。例如体育课上按身高排的队;又如考试过后按成绩排的名次。在编程中也是如此,例如当开发一个学生管理系统,需要按照学好从小到大进行排序;开发一个平台,需要把同类商品按价格从高到低排序。(当然,一般前端不负责处理业务逻辑。)由此可见,排序无处不在。排序看似简单,但是背后却隐藏了多种多样的算法与思想。
一个算法的好坏是通过 时间复杂度 与 空间复杂度 来衡量的。简单来说,时间复杂度 就是执行算法的 时间成本(算法的执行次数) ,空间复杂度 则是执行算法的 空间成本 。
1.1 复杂度
时间复杂度 与 空间复杂度 都是用 “大 O” 来表示,写作 O(*)。有一点值得注意的是,我们谈论复杂度,一般谈论的都是时间复杂度。
常见时间复杂度的 “大 O 表示法” 描述有以下几种:
时间复杂度 | 非正式术语 |
---|---|
O(1) | 常数阶 |
O(n) | 线性阶 |
O(n2) | 平方阶 |
O(log n) | 对数阶 |
O(n log n) | 线性对数阶 |
O(n3) | 立方阶 |
O(2n) | 指数阶 |
一个算法在 N 规模下所消耗的时间消耗从小到大如下:
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
2. 常见数组排序方法
2.1 冒泡排序
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
- 之所以叫冒泡排序,每一轮两两比较之后,都会冒出一个本轮最大的数,将其移动到本轮尾部。
// 需要几个轮次 6个数排序 最大需要5轮
// 外层循环控制轮次
for (var i = 1; i < arr.length; i++) {
for (var j = 0; j < arr.length - i; j++) {
// 经过这样for循环,我们能找到本轮最大的数,并排在本轮尾部
if (arr[j] > arr[j + 1]) {
// 交换位置
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr); // [1, 5, 12, 32, 40, 41]
2.2 选择排序
选择排序是一种简单直观的排序算法。首先找到数组中最小的那个元素,其次,将他和数组的第一个元素交换位置。再次,在剩下的元素中找到最小的元素,将他与数组的第二个元素交换位置。如此往复,直到将整个数组排序。
for (var i = 0; i < arr.length; i++) {
var minIndex = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if (minIndex !== i) {
// 交换位置
var temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
console.log(arr);
2.3 插入排序
对比生活中整理扑克牌的思路,将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中,为了要给插入的元素腾出空间,我们需要将其余元素在插入之前向后移动一位。
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序的算法步骤如下:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤 2~5。
var len = arr.length;
var j, temp;
for (var i = 1; i < len; i++) {
j = i - 1;
temp = arr[i];
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
文档更新时间: 2023-01-05 17:27 作者:孙老师