1. 是什么
- 排序：把某个乱序的数组变成升序或者降序的数组。
js 中的排序：数组的 sort 方法。 - 搜索：找出数组中某个元素的下标。
js 中的搜索：数组的 indexOf 方法。
2. 排序
时间复杂度为O(n2)的排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序（希尔排序比较特殊，它的性能略优于O(n2)，但又比不 上O(nlogn)，姑且把它归入本类）
时间复杂度为O(nlogn)的排序算法
- 快速排序
- 归并排序
- 堆排序
时间复杂度为线性的排序算法
- 计数排序
- 桶排序
- 基数排序
2.1. 冒泡排序
时间复杂度因为嵌套了两个 for 循环，所以时间复杂度是 O(n^2)
思路：
- 比较所有相邻元素，如果第一个比第二个大，则交换它们。
- 一轮下来，可以保证最后一个数是最大的。
- 执行 n-1 轮，就可以完成排序。
Array.prototype.bubbleSort = function() {
// 需要执行 n-1轮，所以是 this.length - 1
for (let i = 0; i < this.length - 1; i++) {
// 每次比较的数量是当前的 length - 1 - 轮数
for (let j = 0; j < this.length - 1 - i; j++) {
if (this[j] > this[j+1]) {
const temp = this[j]
this[j] = this[j+1]
this[j+1] = temp
}
}
}
}
const array = [3,5,6,2,1];
array.bubbleSort();
console.log(array)
2.1.1 优化1
对于上面这种情况，经过第6轮后，整个数列已经是有序的了。可是我们的代码还会继续执行第7轮排序，如果能判断出已经有序，并作出标记，那么剩下的几轮排序就不必要执行了
Array.prototype.bubbleSort = function() {
// 需要执行 n-1轮，所以是 this.length - 1
for (let i = 0; i < this.length - 1; i++) {
+ let isSorted = true
for (let j = 0; j < this.length - 1 - i; j++) {
if (this[j] > this[j+1]) {
const temp = this[j]
this[j] = this[j+1]
this[j+1] = temp
+ isSorted = false
}
}
+ if (isSorted) break;
}
}
2.1.1 优化2
以一个新的数组为例。
这个数组的特点是前半部分的元素（3、4、2、1）无序，后半部 分的元素（5、6、7、8）按升序排列，并且后半部分元素中的最小值也大于前半部分元素的最大值。
其实右面的许多元素已经是有序的了，可是每一轮还是白白地比较了许多次。
这个问题的关键点在于对数列有序区的界定。
我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。
Array.prototype.bubbleSort = function() {
//记录最后一次交换的位置
+ let lastExchangeIndex = 0;
//无序数列的边界，每次比较只需要比到这里为止
+ let sortBorder = this.length - 1;
for (let i = 0; i < this.length - 1; i++) {
let isSorted = true
for (let j = 0; j < sortBorder; j++) {
if (this[j] > this[j+1]) {
const temp = this[j]
this[j] = this[j+1]
this[j+1] = temp
isSorted = false
+ lastExchangeIndex = j
}
}
+ sortBorder = lastExchangeIndex;
if (isSorted) break;
}
}
2.1.3 鸡尾酒排序
冒泡排序算法每一轮都是从左到右来比较元素，进行单向的位置交换的。而鸡尾酒排序的元素比较和交换过程是双向的。
比如一个无序数组[2,3,4,5,6,7,8,1]，我们对其进行从小到大的排序，冒泡排序如下
元素2、3、4、5、6、7、8已经是有序 的了，只有元素1的位置不对，却还要进行7轮排序
使用鸡尾酒排序
第1轮（和冒泡排序一样，8和1交换）
第2轮
此时开始不一样了，我们反过来从右往左比较并进行交换。
第3轮（虽然实际上已经有序，但是流程并没有结束）
在鸡尾酒排序的第3轮，需要重新从左向右比较并进行交换。
1和2比较，位置不变；2和3比较，位置不变；3和4比较，位置不 变……6和7比较，位置不变。
没有元素位置进行交换，证明已经有序，排序结束。
思路：排序过程就像钟摆一样，第1轮从左 到右，第2轮从右到左，第3轮再从左到右……
Array.prototype.coocktailSort = function() {
// 轮数小于当前数组长度 / 2(比如8个是3轮)
for (let i = 0; i < this.length / 2; i++) {
let isSorted = true;
for (let j = i; j < this.length - i - 1; j++) {
if (this[j] > this[j+1]) {
let temp = this[j];
this[j] = this[j+1];
this[j+1] = temp;
isSorted = false;
}
}
if (isSorted) break;
isSorted = true;
for (let j = this.length - i - 1; j > 1; j--) {
if (this[j] < this[j-1]) {
let temp = this[j];
this[j] = this[j-1];
this[j-1] = temp;
isSorted = false;
}
}
if (isSorted) break;
}
}
优点和缺点：优点是能够在特定条件 下，减少排序的回合数；而缺点也很明显，就是代码量几乎增加了1倍。
适用场景：大部分元素已经有序的情况
2.2. 选择排序的思路
- 找到数组中的最小值，选中它将其放置在第一位。
- 接着找到第二小的值，选中它并将其放置在第二位。
- 依次类推，执行 n -1 轮。
Array.prototype.selectionSort = function() {
// 执行 n - 1 轮
for (let i = 0; i < this.length - 1; i++) {
// 每一轮的最小值 index 默认为当前这一轮的初始值
let minIndex = i;
for (let j = i; j < this.length; j++) {
if (this[j] < this[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
const temp = this[minIndex]
this[minIndex] = this[i]
this[i] = temp
}
}
}
const array = [3,5,6,2,1];
array.selectionSort();
console.log(array)
时间复杂度：因为也有两个嵌套循环，所以也是 O(n^2)
2.3. 插入排序
思路
- 从数组里取出第二（轮数+1）个数，从靠近它的前一个数开始依次往前跟它对比
- 比它大就往它后面排，找到第一个小于或等于它的数就把取出的这个数插入到比它小的这个数的后面
- 以此类推进行到最后一个数
Array.prototype.insertionSort = function() {
for (let i = 1; i < this.length; i++) {
let temp = this[i];
let j = i;
while(j > 0) {
if (this[j - 1] > temp) {
// 如果前面的值大于比较项，前面的值往后排也就是把前面的值赋给当前项
this[j] = this[j -1]
} else {
// 否则直接把当前位置作为插入的位置
break;
}
j--
}
this[j] = temp;
}
}
const array = [3,5,6,2,1];
array.insertionSort();
console.log(array)
时间复杂度：两个嵌套循环所以也是 O(n^2)
2.4. 归并排序
思路：
- 分：把数组劈成两半，再递归对子数组进行”分“操作，直到分成一个个单独的数。
- 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组。
合并两个有序数组
Array.prototype.mergeSort = function() {
const rec = (arr) => {
if (arr.length === 1) { return arr};
const mid = Math.floor(arr.length /2);
const left = arr.slice(0, mid);
const right = arr.slice(mid, arr.length);
const orderLeft = rec(left);
const orderRight = rec(right);
const res = [];
while(orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
} else if (orderLeft.length) {
res.push(orderLeft.shift())
} else if (orderRight.length) {
res.push(orderRight.shift())
}
}
return res;
}
// 改变原数组
rec(this).forEach((n, i) => {
this[i] = n;
})
}
const array = [5,4,3,2,1];
array.mergeSort();
时间复杂度
- 分的时间复杂度是 O(logN)
- 合的时间复杂度是 O(n)
- 分和合是嵌套关系所以是 O(n * logN)
2.5. 快速排序
Array.prototype.quickSort = function() {
const rec = (arr) => {
if (arr.length <= 1) return arr;
const left = [];
const right = [];
const mid = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < mid) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...rec(left), mid, ...rec(right)]
}
const res = rec(this);
res.forEach((n, i) => {this[i] = n})
}
const array = [3,5,6,2,1];
array.quickSort();
时间复杂度：
最差情况每次都将第一个元素作为基准值，有几个元素调用栈的高度就会是几，所以调用栈的高度是 O(n)，每层需要的时间为 O(n) 所以就是 O(n) * O(n) = O(n^2)
平均情况调用栈的高度是 O(log n) 每层的时间是 O(n) 所以是 O(n) * O(log n) = O(n log n)
- 递归的时间复杂度是 O(logN)
- 分区操作的时间复杂度是 O(n)
- 因为是嵌套的所以总的时间复杂度是： O(n * lo)
3. 搜索
3.1. 顺序搜索
Array.prototype.sequentialSearch = function(item) {
for (let i = 0; i < this.length; i++) {
if (this[i] === item) {
return i;
}
}
retutn -1;
}
const arr = [1,2,3,4,5]
arr.sequentialSearch(3)
时间复杂度 O(n)
3.2. 二分搜索
思路
Array.prototype.binarySearch = function(item) {
let low = 0;
let high = this.length - 1;
while(low <= high) {
const mid = Math.floor((high-low)/2);
const element = this[mid];
if (element < item) {
low = mid + 1;
} else if (element > item) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
const arr = [1,2,3,4,5]
arr.binarySearch(3)
时间复杂度 O(logN)
4. 合并两个有序链表 leetCode 21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
解题思路
解题步骤
var mergeTwoLists = function(list1, list2) {
const res = new ListNode(0);
let p = res;
let p1 = list1
let p2 = list2
while(p1 && p2) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next
}
if (p1) {
p.next = p1;
}
if (p2) {
p.next = p2;
}
return res.next
};
5. 猜数字大小 leetCode 374
var guessNumber = function(n) {
let min = 1;
let high = n;
while(min <= high) {
let mid = Math.floor((min+high) /2)
const newValue = guess(mid)
if (newValue === 0) {
return mid
} else if (newValue === -1) {
high = mid - 1
} else {
min = mid + 1
}
}
};
网友评论