作者:yanyige | 发布时间:2017-03-14 20:25
排序算法总结
一、插入排序
插入排序很好理解，顾名思义，就是将未排好序的元素一个一个插入到已经排好的序列中。需要两重循环遍历整个数组，时间复杂度是O(n^2)。
代码如下：
function insertSort(arr) {
var length = arr.length;
for(let i = 1; i < length; i ++) {
let temp = arr[i];
let j = i - 1;
while(j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j --;
}
arr[j + 1] = temp;
}
return arr;
}
二、希尔排序
希尔排序是插入排序的变型，它把数组按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 先取一个小于n的整数d1作为第一个增量，将所有数进行分组。在各组内部进行插入排序，排序后在将第二个增量设置成d2(d1/2)。重复这个步骤直到增量d==1，即所有数字放在同一组中进行插入配需位置。
时间复杂度是O(n^1.3)
整个过程如下图所示：
<div align=center>
</div>
代码如下：
function shellSort(arr) {
let length = arr.length;
let d = length >> 1;
while(d > 0) {
for(let i = d; i < length; i ++) {
let j = i - d;
while(j >= 0 && arr[j] > arr[j + d]) {
let temp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = temp;
j = j - d;
}
}
d = d >> 1;
}
return arr;
}
三、冒泡排序
这是最长接触的一种排序方法了吧~ 双重循环遍历相邻的两个数，使结果较小的向上“冒泡”，最终的结果就是排好序的数组了。
直接上代码:
function bubbleSort(arr) {
let length = arr.length;
for(let i = 0; i < length - 1; i ++) {
for(let j = i + 1; j < length; j ++) {
if(arr[j] < arr[i]) {
let temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}
