必备知识点
- JS原型
- 排序中的有序区和无序区
简单来说，有序区就是在一组数据中已经排好序的部分，无序区就是该组数据中还没排好序的部分。
- 二叉树的基本知识
封装原型方法
Function.prototype.method = function ( name, func ) {
this.prototype[ name ] = func;
return this;
}
|
算法思路及复杂度对比
| 名称 |
数据对象 |
时间复杂度 |
空间复杂度 |
描述 |
| 冒泡排序 |
数组 |
O(n²) |
O(1) |
(无序区，有序区) 通过在无序区的相邻元素的比较和替换，使较小的元素浮到最上面 |
| 选择排序 |
数组、链表 |
O(n²) |
O(1) |
(有序区，无序区) |
| 在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少 |
|
|
|
|
| 插入排序 |
数组、链表 |
O(n²) |
O(1) |
(有序区，无序区) 把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多 |
| 堆排序 |
数组 |
O(nlogn) |
O(1) |
(有序区，无序区) 在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少 |
| 归并排序 |
数组、链表 |
O(nlogn) |
|
(最大堆，有序区) 从堆顶把根卸下来放在有序区之前，再恢复堆 |
| 快速排序 |
数组 |
O(nlogn)~O(n²) |
O(logn)，O(n) |
（小数，枢纽元，大数） |
| 希尔排序 |
数组 |
O(nlog²n)~O(n²) |
O(1) |
每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后依次一定要是1 |
算法实现
1.冒泡排序
Array.method('bubbleSort', function () {
var len = this.length,
i, j, tmp;
for ( i = 0; i < len; i++ ) {
for ( j = len - 1; j > i; j-- ) {
if ( this[j] < this[j-1] ) {
tmp = this[j-1];
this[j-1] = this[j];
this[j] = tmp;
}
}
}
return this;
});
|
改进冒泡排序:如果在某次排序中没有出现交换的情况，那么说明在无序的元素现在已经是有序了，可以直接返回。
Array.method('rBubbleSort', function () {
var len = this.length,
i, j, tmp, exchange;
for ( i = 0; i < len; i++ ) {
exchange = 0;
for ( j = len - 1; j > i; j-- ) {
if ( this[j] < this[j-1] ) {
tmp = this[j-1];
this[j-1] = this[j];
this[j] = tmp;
exchange = 1;
}
}
if ( !exchange ) {
return this;
}
}
return this;
});
|
2.选择排序
Array.method('selectSort', function () {
var len = this.length,
i, j, k, tmp;
for ( i = 0; i < len; i++ ) {
k = i;
for ( j = i + 1; j < len; j++ ) {
if ( this[j] < this[k] ) {
k = j;
}
}
if ( k!=i ) {
tmp = this[k];
this[k] = this[i];
this[i] = tmp;
}
}
return this;
});
|
3.插入排序
Array.method('insertSort', function () {
var len = this.length,
i, j, k, tmp;
for ( i = 1; i < len; i++ ) {
tmp = this[i];
j = i - 1;
while ( j>=0 && tmp < this[j] ) {
this[j+1] = this[j];
j--;
}
this[j+1] = tmp;
}
return this;
});
|
4.堆排序
堆排序是一种树形选择排序方法(注意下标是从1开始的，也就是R[1...n])。
堆排序思路：
1) 初始堆：
将原始数组调整成大根堆的方法——筛选算法：
比较R[2i]、R[2i+1]和R[i]，将最大者放在R[i]的位置上(递归调用此方法到结束)
2) 堆排序：
每次将堆顶元素与数组最后面的且没有被置换的元素互换。
Array.method('createHeap', function(low, high){
var i=low, j=2*i, tmp=this[i];
while(j<=high){
if(j< high && this[j]<this[j+1]) j++;
if(tmp < this[j]){
this[i] = this[j];
i = j;
j = 2*i;
}else break;
}
this[i] = tmp;
return this;
});
Array.method('heapSort', function(){
var i, tmp, len=this.length-1;
for(i=parseInt(len/2); i>=1; i--) this.createHeap(i, len);
for(i=len; i>=2; i--){
tmp = this[1];
this[1] = this[i];
this[i] = tmp;
this.createHeap(1, i-1);
}
return this;
});
|
5.归并排序
归并排序思路：
1) 归并
从两个有序表R[low…mid]和R[mid+1…high]，每次从左边依次取出一个数进行比较，将较小者放入tmp数组中，最后将两段中剩下的部分直接复制到tmp中。
这样tmp是一个有序表，再将它复制加R中。(其中要考虑最后一个子表的长度不足length的情况)
2) 排序
自底向上的归并，第一回：length=1；第二回：length=2*length …
Array.method('createHeap', function(low, high){
var i=low, j=2*i, tmp=this[i];
while(j<=high){
if(j< high && this[j]<this[j+1]) j++;
if(tmp < this[j]){
this[i] = this[j];
i = j;
j = 2*i;
}else break;
}
this[i] = tmp;
return this;
});
Array.method('heapSort', function(){
var i, tmp, len=this.length-1;
for(i=parseInt(len/2); i>=1; i--) this.createHeap(i, len);
for(i=len; i>=2; i--){
tmp = this[1];
this[1] = this[i];
this[i] = tmp;
this.createHeap(1, i-1);
}
return this;
});
|
6.快速排序
快速排序思路：
1) 假设第一个元素为基准元素
2) 把所有比基准元素小的记录放置在前一部分，把所有比基准元素大的记录放置在后一部分，并把基准元素放在这两部分的中间(i=j的位置)
Array.method('quickSort', function(s, t){
var i=s, j=t,
tmp;
if(s < t){
tmp = this[s];
while(i!=j){
while(j>i && this[j]>tmp) j--;
R[i] = R[j];
while(i<j && this[j]<tmp) i++;
R[j] = R[i];
}
R[i] = tmp;
this.quickSort(s, i-1);
this.quickSort(i+1, t);
}
return this;
});
|
7.希尔排序
希尔排序思路:
我们在第 i 次时取gap = n/(2的i次方)，然后将数组分为gap组(从下标0开始，每相邻的gap个元素为一组)，接下来我们对每一组进行直接插入排序。
Array.method('shellSort', function(){
var len = this.length, gap = parseInt(len/2),
i, j, tmp;
while(gap > 0){
for(i=gap; i<len; i++){
tmp = this[i];
j = i - gap;
while(j>=0 && tmp < this[j]){
this[j+gap] = this[j];
j = j - gap;
}
this[j + gap] = tmp;
}
gap = parseInt(gap/2);
}
return this;
});
|
