【算法篇】排序与链表

排序

排序算法是计算机中比较常用的算法,这边整理了如下几种排序算法:

  • 冒泡排序
  • 插入排序
  • 选择排序
  • 归并排序
  • 快排
  • 堆排序

以下两个函数是排序中会用到的通用函数

1
2
3
4
5
6
7
8
9
function checkArray(array){
if(!array || array.length <= 2) return false;
return true;
}
function swap(array, left, right){
let rightValue = array[right];
array[right] = array[left];
array[left] = rightValue;
}

冒泡排序

冒泡排序的原理如下,从第一个元素开始,把当前元素和下一个索引元素进行比较。如果当前元素大,那么就交换位置,重复操作直到比较到最后一个元素,那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作,但是此时最后一个元素已经是最大数了,所以不需要再比较最后一个元素,只需要比较到 length - 1 的位置。

https://user-gold-cdn.xitu.io/2018/4/12/162b895b452b306c?w=670&h=508&f=gif&s=282307

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubble(arr) {
let continue = checkArray(arr);
if(!continue) {
return;
}
for(let i = arr.length - 1; i > 0; i--){
// 从0到length - 1遍历
for(let j = 0; j < i; j++){
if(arr[j] > arr[j + 1]){
swap(arr, j, j+1);
}
}
}
}

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + …… + 1 ,去掉常数项以后得出时间复杂度是O(n * n)

插入排序

插入排序的原理如下。第一个元素默认是已排序元素,取出下一个元素和当前元素比较,如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数,所以下次取出操作从第三个元素开始,向前对比,重复之前的操作。

https://user-gold-cdn.xitu.io/2018/4/12/162b895c7e59dcd1?w=670&h=508&f=gif&s=609549

1
2
3
4
5
6
7
8
9
10
11
12
function insertion(arr) {
let continue = checkArray(arr);
if(!continue) {
return;
}
for(let i = 1; i < arr.length; i++){
for(let j = i - 1; j >=0 && arr[j] > arr[j + 1]; j--){
swap(arr, j, j + 1);
}
}
return arr;
}

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + …… + 1 ,去掉常数项以后得出时间复杂度是O(n * n)

选择排序

选择排序的原理如下。遍历数组,设置最小值的索引为0,如果取出的值比当前最小值小,就替换最小值索引,遍历完成后,将第一个元素和最小值索引上的值交换。如上操作后,第一个元素就是数组中的最小值,下次遍历就可以从索引1开始重复上述操作。

https://user-gold-cdn.xitu.io/2018/4/13/162bc8ea14567e2e?w=670&h=508&f=gif&s=965636

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selection(arr) {
let continue = checkArray(arr);
if(!continue) {
return;
}
for(let i = 0; i < arr.length; i++){
let minIndex = i;
for(let j = i + 1; j < arr.length; j++){
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
retrn arr;
}

时间复杂度O(n * n)。

归并排序

递归的将数组两两分开直到最多包含两个元素,然后将数组排序合并,最终合并为排序好的数组。假设我有一组数组[3,1,2,8,9,7,6],中间数索引是3,先排序数组[3,1,2,8]。在这个左边数组上,继续拆分直到变成数组包含两个元素(如果数组长度是奇数的话,会有一个拆分数组只包含一个元素)。然后排序数组[3,1]和[2,8],然后再排序数组 [1,3,2,8],这样左边数组就排序完成,然后按照以上思路排序右边数组,最后将数组[1,2,3,8]和[6,7,9]排序。

https://user-gold-cdn.xitu.io/2018/4/13/162be13c7e30bd86?w=896&h=1008&f=gif&s=937952

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function sort(arr) {
let continue = checkArray(arr);
if(!continue) {
return;
}
mergeSort(arr, 0, arr.length - 1);
return arr;
}

function mergeSort(arr, left, right) {
// 左右索引相同说明已经只有一个数
if(left === right) return;
// 等同于 left + (right - left) / 2
// 相比 (left + right) / 2 更加安全,不会溢出
// 使用位运算,因为快
let mid = parseInt(left + (right - left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

let help = [];
let i = 0;
let p1 = left;
let p2 = mid + 1;
while(p1 <= mid && p2 <= right){
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid){
help[i++] = arr[p1++];
}
while(p2 <= right) {
help[i++] = arr[p2++];
}
for(let i = 0; i < help.length; i++){
arr[left + i] = help[i];
}
return arr;
}

时间复杂度O(N * logN)。

快排

随机选取一个数组中的值作为基准值,从左至右取值与基准值对比大小。比基准值小的放数组左边,大的放右边,对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分,继续递归以上操作。

https://user-gold-cdn.xitu.io/2018/4/16/162cd23e69ca9ea3?w=824&h=506&f=gif&s=867744

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function sort(arr){
let continue = checkArray(arr);
if(!continue) {
return;
}
quickSort(arr, 0, arr.length - 1);
return arr;
}

function quickSort(arr, left, right){
if(left < right){
swap(arr, , right);
let indexs = part(arr, parseInt(Math.random() * (right - left + 1)) + left, right);
quickSort(arr, left, indexs[0]);
quickSort(arr, indexs[1] + 1, right);
}
}

function part(arr, left, right){
let less = left - 1;
let more = right;
while(left < more) {
if(arr[left] < arr[right]){
++less;
++left;
}else if(arr[left] > arr[right]){
swap(arr, --more, left);
}else {
left ++;
}
}
swap(arr, right, more);
return [less, more];
}

该算法的复杂度和归并排序是相同的,但是额外空间复杂度比归并排序少,只需O(logN),并且相比归并排序来说,所需的常数时间也更少。

堆排序

堆排序利用了二叉堆的特性来做,二叉堆通常用数组表示,并且二叉堆是一颗完全二叉树(所有叶子节点都是从左往右顺序排序,并且其他层的节点都是满的)。二叉堆又分为大根堆与小根堆。

  • 大根堆是某个节点的所有子节点的值都比他小
  • 小根堆是某个节点的所有子节点的值都比他大

堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例,某个节点的左边子节点索引是 i 2 + 1,右边是i 2 + 2 ,父节点是 (i - 1) / 2。

  1. 首先遍历数组,判断该节点的父节点是否比他小,如果小就交换位置并继续判断,直到他的父节点比他大。
  2. 重新以上操作1,直到数组首位是最大值
  3. 将首位和末尾交换位置并将数组长度减一,表示数组末尾已是最大值,不需要再比较大小。
  4. 对比左右节点哪个大,然后记住大的节点的索引并且和父节点对比大小,如果子节点大就交换位置
  5. 重复 3-4 直到整个数组都是大根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function heap(arr) {
let continue = checkArray(arr);
if(!continue) {
return;
}
// 将最大值交换到首位
for(let i = 0; i < arr.length; i++){
heapInsert(arr, i);
}
let size = arr.length;
// 交换首位和末尾
swap(arr, 0, --size);
while(size > 0){
heapify(arr, 0, size);
swap(arr, 0, --size);
}
return arr;
}

function heapInsert(arr, index){
// 如果当前节点比父节点大,就交换
while(arr[index] > arr[parseInt((index - 1) / 2)]){
swap(arr, index, parseInt((index - 1) / 2));
// 将索引变成父节点
index = parseInt((index - 1) / 2);
}
}

function heapify(arr, index, size) {
let left = index * 2 + 1;
while(left < size) {
// 判断左右节点大小
let largest = left + 1 < size && arr[left] < arr[left + 1] ? left + 1 : left;
// 判断子节点和父节点大小
largest = arr[index] > arr[largest] ? largest : index;
if(largest === index) break;
swap(arr, index, largest);
index = largest;
left = index * 2 + 1;
}
}

以上实现了小根堆,如果需要实现大根堆,只需要把节点对比反一下就好。
该算法复杂度是O(logN)。

系统自带排序实现

每个语言的排序内部实现都是不同的。
对于js来说,数组长度大于10会采用快排,否则使用插入排序。选择插入排序是因为虽然时间复杂度很差,但是在数据量很小的情况下和O(n * logN) 相差无几,然后插入排序需要的时间常数很小,所以相对别的排序来说更快。

对于java来说,还会考虑内部的元素的类型。对于存储对象的数组来说,会采用稳定性好的算法。稳定性的意思就是对于相同值来说,相对顺序不能改变。


链表

反转单向链表

思路很简单,使用三个变量分别表示当前节点和当前节点的前后节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function reverseList(head){
// 判断下变量边界问题
if(!head || !head.next) return head;
// 初始设置为空,因为第一个节点反转后就是尾部,尾部节点指向 null
let pre = null;
let current = head;
let next;
// 判断当前节点是否为空
// 不为空就先获取当前节点的下一节点
// 然后把当前节点的next设为上一个节点
// 然后把current设为下一个节点,pre设为当前节点
while(current) {
next = current.next;
current.next = pre;
pre = current;
current = next;
}
return pre;
}

坚持原创技术分享,您的支持将鼓励我继续创作!