十大经典排序算法(JavaScript)
这段时间琢磨了一下算法题，虽然算法课程在两年前就学了，但是期末才八十多分的我，，，真的啥也没学进去
本来也学得没多好，所以就从最基础的开始学吧！ 这十大算法都是之前老师在课堂上讲过的，但是，即使之前听的贼认真，很久也没有用也该忘了，况且我听得还不怎么认真呢
的界面是真的好丑，这个字体真的丑，还不能切换字体大小，，，（不知道我几乎每篇博客都要吐槽它，会不会给我拉黑了）
这就是个自己学习的博客（因为我话多），如果有代码可以优化的还请大家多多指出来，孩子感激不尽呀！！！
首先是总体框架图这十大算法可按照是否为比较算法分为两类：比较类和非比较类比较类排序（非线性时间比较类排序）：通过比较来决定元素间的相对次序 -> 非比较类排序（先行世纪那非比较类排序）：不通过比较来决定元素间的相对次序。
时间复杂度，空间复杂度都写在了图里面（还是改成了电子版吧，之前自己写的太丑了）
1.冒泡排序（Bubble Sort）
冒泡排序的思想很简单。重复走访要排序的元素，一次比较两个元素，顺序错误则调换顺序。一直重复，直到所有的走访中顺序均按照指定（从大到小，从小到大）排序则排序完成。
1.1算法描述（从小到大排列）
比较相邻元素。如果前一个元素大于后一个元素，则交换顺序。每一对相邻元素都做同样的工作，直至排序完成。
1.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>sort
</title
>
</head
>
<body
>
<p id
="bubblesort"></p
>
</body
>
<script
>
function bubblesort(arr
){
var len
= arr
.length
;
for (var i
= len
- 1; i
> 0; i
++){
for (var j
= 1; j
<= i
; j
++){
if (arr
[j
-1] > arr
[j
]){
var temp
= arr
[j
];
arr
[j
] = arr
[j
-1];
arr
[j
-1] = temp
;
}
}
}
return arr
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("bubblesort").innerHTML
= bubblesort(arr
);
</script
>
</html
>
2.选择排序（Selection Sort）
选择排序的思想也很简单。首先找到最大（最小）元素放在起始位置，然后在剩余元素中继续寻找最大（最小）元素放在已排序的元素后。以此类推，直至所有元素排序完毕。
2.1算法描述（从小到大）
初始状态时，有序为空，无序为arr第一趟排序过后，有序中有一个最小元素，无序中为出去最小元素后的arr序列n-1趟结束，数组有序
2.2算法实现
这两个都是从小到大排序的，但是第二个是先找出最大元素
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="selectsort1"></p
>
<p id
="selectsort2"></p
>
</body
>
<script
>
function selectsort1(arr
){
var len
= arr
.length
;
var minindex
;
for (var i
= 0; i
< len
; i
++){
minindex
= i
;
for (var j
= i
+1; j
< len
; j
++){
if (arr
[j
] < arr
[minindex
]){
minindex
= j
;
}
}
var temp
= arr
[i
];
arr
[i
] = arr
[minindex
];
arr
[minindex
] = temp
;
}
return arr
;
}
function selectsort2(arr
){
var len
= arr
.length
;
var maxindex
;
for (var i
= len
-1; i
>=0; i
--){
maxindex
= i
;
for (var j
= i
-1; j
>= 0; j
--){
if (arr
[j
] >arr
[maxindex
]){
maxindex
= j
;
}
}
var temp
= arr
[i
];
arr
[i
] = arr
[maxindex
];
arr
[maxindex
] = temp
;
}
return arr
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("selectsort1").innerHTML
= selectsort1(arr
);
document
.getElementById("selectsort2").innerHTML
= selectsort2(arr
);
</script
>
</html
>
3.插入排序（Insertion Sort）
插入排序的思想也很简单直观。通过构建有序序列，对未排序的数据，在已排序的序列中从后向前扫描，找到相应位置进行插入。
3.1算法描述（从小到大）
从第一个元素开始，该元素被认为是已经排序抽取下一个元素，在已经排序的序列中从后向前扫描，直到出现一个小于它的元素，将其插入该元素后面
3.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="insertsort"></p
>
</body
>
<script
>
function insertsort(arr
){
var len
= arr
.length
;
var preindex
,current
;
for (var i
= 1; i
< len
; i
++){
preindex
= i
-1;
current
= arr
[i
];
while(preindex
>= 0 && arr
[preindex
] > current
){
var temp
;
temp
= arr
[preindex
+1];
arr
[preindex
+1] = arr
[preindex
];
arr
[preindex
] = temp
;
preindex
--;
}
}
return arr
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("insertsort").innerHTML
= insertsort(arr
);
</script
>
</html
>
4.希尔排序（Shell Sort）
第一个突破O(n*n)的排序算法，是简单插入排序的升级版。但它是优先比较距离较远的元素。也称为缩小增量排序。
4.1算法描述
将需要排序的序列进行分组，分组计算为(length/2)取整数值，每进行一轮分组就会减少一半或者更多。从下标为0的元素开始，下一个元素为下标加上分组的组数，在序列长度内均为该组的元素。组内进行排序，从小到大，直至分组数为1结束。
4.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="shellsort"></p
>
</body
>
<script
>
function shellsort(arr
){
var len
= arr
.length
;
var temp
;
for (var gap
= Math
.floor(len
/ 2); gap
> 0; gap
= Math
.floor(gap
/ 2)){
for (var i
= 0; i
< gap
; i
++){
for (var j
= 0; j
< len
/ gap
; j
++){
for ( var z
= 0; z
< len
; z
+= gap
){
if (arr
[z
] > arr
[z
+gap
]){
temp
= arr
[z
];
arr
[z
] = arr
[z
+gap
];
arr
[z
+gap
] = temp
;
}
}
}
}
}
return arr
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("shellsort").innerHTML
= shellsort(arr
);
</script
>
</html
>
5.归并排序（Merge Sort）
归并排序建立在归并操作上。采用分治法的思想。将已有的有序子序列进行合并，得到完全有序的序列；先使子序列有序然后实现整体有序。 两个有序表合并为一个称为二路归并，n个称为n路归并。
5.1算法描述
将长度为n的序列分为两个长度为n/2的序列，为单数则右边比左边多一个；对这两个子序列分别进行归并和排序；将排序号的两个子序列合并。
5.2 代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="mergesort"></p
>
</body
>
<script
>
function mergesort(arr
){
var len
= arr
.length
;
if (len
< 2){
return arr
;
}
var middle
= Math
.floor(len
/ 2);
var left
= arr
.slice(0,middle
);
var right
= arr
.slice(middle
);
return merge(mergesort(left
),mergesort(right
));
}
function merge(left
,right
){
var res
= [];
while (left
.length
> 0 && right
.length
> 0){
if (left
[0] <= right
[0]){
res
.push(left
.shift());
}else{
res
.push(right
.shift());
}
}
while (left
.length
)
res
.push(left
.shift());
while (right
.length
)
res
.push(right
.shift());
return res
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("mergesort").innerHTML
= mergesort(arr
);
</script
>
</html
>
6.快速排序（Quick Sort）
通过一趟排序，将序列分为两部分，一部分比关键字小，另一部分比关键字大，将关键字排到两部分之间，进行第二轮排序。
6.1算法描述
从数列中挑出一个元素作为基准（pivot），一般为第一个；将所有比基准元素小的元素排在前面，大的排在后面；将基准元素放在中间位置；递归将第一个元素选为基准元素。
6.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="quicksort"></p
>
</body
>
<script
>
function quicksort(arr
,left
,right
){
var left
= typeof left
!= 'number' ? 0 : left
;
var right
= typeof right
!= 'number' ? arr
.length
- 1 : right
;
if (left
>= right
){
return;
}
var start
= left
;
var end
= right
;
var flag
= left
;
while (left
< right
){
while (left
< right
&& arr
[right
] >= arr
[flag
]) {
right
--;
}
if (arr
[right
] < arr
[flag
]) {
var temp
= arr
[right
];
arr
[right
] = arr
[flag
];
arr
[flag
] = temp
;
flag
= right
;
}
while (left
< right
&& arr
[left
] <= arr
[flag
]) {
left
++;
}
if(arr
[left
] > arr
[flag
]) {
var temp
= arr
[left
];
arr
[left
] = arr
[flag
];
arr
[flag
] = temp
;
flag
= left
;
}
}
quicksort(arr
, start
, left
- 1);
quicksort(arr
, left
+ 1, end
);
return arr
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("quicksort").innerHTML
= quicksort(arr
);
</script
>
</html
>
7.堆排序（Heap Sort）
利用堆设计的一种排序算法。子节点的键值总是大于（小于）它的父节点。
7.1算法描述
将初始无序列表构建成大根堆，即父节点总是大于它的子节点；将堆顶元素与最后的元素进行交换；对交换后的堆进行调整成为新的大根堆；再进行上一步操作；直到所有的元素排序完毕。
7.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="heapsort"></p
>
</body
>
<script
>
var leng
;
function heapsort(arr
){
var leng
= arr
.length
;
for (var i
= Math
.floor(leng
/ 2); i
>= 0; i
--){
heapify(arr
,i
);
}
return arr
;
}
function heapify(arr
,i
){
var left
= 2 * i
+ 1;
var right
= 2 * i
+ 2;
var largest
= i
;
if (left
< leng
&& arr
[left
] > arr
[largest
]){
largest
= left
;
}
if (right
< leng
&& arr
[right
] > arr
[largest
]){
largest
= right
;
}
if(largest
!= i
){
var temp
= arr
[i
];
arr
[i
] = arr
[largest
];
arr
[largest
] = temp
;
heapify(arr
,largest
);
}
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("heapsort").innerHTML
= heapsort(arr
);
</script
>
</html
>
8.计数排序（Counting Sort）
输入的数据值转化为键存储在额外开辟的数据空间中。作为一种线性实践复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
8.1算法描述
找出待排序的数组中的最大元素和最小元素，建立区间为最小元素到最大元素之间的额外空间；统计数组中每个值为i的元素出现的次数，存入额外空间；反向填充数组，将每个元素i放在新数组中，每放一个计数就减去1。
8.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="countsort"></p
>
</body
>
<script
>
function countsort(arr
){
var len
= arr
.length
;
var min
= arr
[0], max
= arr
[0];
for (var i
= 1; i
< len
; i
++){
if (arr
[i
] < min
){
min
= arr
[i
];
}
if (arr
[i
] > max
){
max
= arr
[i
];
}
}
var bucketlen
= max
- min
+ 1;
var bucket
= [];
var count
= new Array(bucketlen
);
for (var i
= 0; i
< bucketlen
; i
++){
count
[i
] = 0;
}
var index
= 0;
for (var i
= 0; i
< len
; i
++){
count
[arr
[i
] - min
]++;
}
for (var i
= 0; i
< bucketlen
; i
++){
while (count
[i
]--){
bucket
[index
] = i
+ min
;
index
++;
}
}
return bucket
;
}
var arr
= [1,8,9,2,2,2,3,1,1,1,5,6,8,9,5];
document
.getElementById("countsort").innerHTML
= countsort(arr
);
</script
>
</html
>
9.桶排序（Bucket Sort）
桶排序是计数排序的升级版。利用了函数映射的关系，高效的关键就在于映射函数的确定。 假设输入数据服从均匀分布，将数据分到有限数量的桶中，每个桶内在进行排序（可能会使用到别的排序方法，或者使用递归）。
9.1算法描述
设置定量的数组作为空桶；便利输入数据，把数据通过区间比较（比如23，放在代号为2的桶，52放在代号为5的桶）；对每个不是空桶的桶进行排序；将排好序的非空桶的数据拼合。
9.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="bucketsort"></p
>
</body
>
<script
>
function bucketsort(arr
,bucsize
){
if (arr
.length
=== 0){
return arr
;
}
var min
= arr
[0];
var max
= arr
[0];
for (var i
= 1; i
< arr
.length
; i
++){
if (arr
[i
] < min
){
min
= arr
[i
];
}else if (arr
[i
] > max
){
max
= arr
[i
];
}
}
var default_buck_size
= 5;
bucsize
= bucsize
|| default_buck_size
;
var buccount
= Math
.floor((max
- min
) / bucsize
) + 1;
var buckets
= new Array(buccount
);
for (var i
= 0; i
< buckets
.length
; i
++){
buckets
[i
] = [];
}
for (var i
= 0; i
< arr
.length
; i
++){
buckets
[Math
.floor((arr
[i
] - min
) / bucsize
)].push(arr
[i
]);
}
arr
.length
= 0;
for (var i
= 0; i
< buckets
.length
; i
++){
insertsort(buckets
[i
]);
for (var j
= 0; j
< buckets
[i
].length
; j
++){
arr
.push(buckets
[i
][j
]);
}
}
return arr
;
}
var arr
= [1,8,9,2,2,2,3,1,1,1,5,6,8,9,5];
document
.getElementById("bucketsort").innerHTML
= bucketsort(arr
);
</script
>
</html
>
10.基数排序（Radix Sort）
基数排序按照低位优先排序，然后收集；然后高位排序，然后再收集；依此类推，直至最高位排序完毕。
10.1算法描述
取得数组中的最大数值，确定最大位数；从最低位开始取每个位组成radix数组；对radix进行基数排序。
10.2代码实现
<html
>
<meta charset
="utf-8">
<head
>
<title
>Sort
</title
>
</head
>
<body
>
<p id
="radixsort"></p
>
</body
>
<script
>
function radixsort(arr
){
var mod
= 10;
var dev
= 1;
var max
= arr
[0];
var maxdigit
= 0;
for (var i
= 1; i
< arr
.length
; i
++){
if (arr
[i
] > max
){
max
= arr
[i
];
}
}
while (max
){
max
= parseInt(max
/ 10);
maxdigit
++;
}
var count
= [];
for (var i
= 0; i
< maxdigit
; i
++, dev
*= 10, mod
*= 10){
for (var j
= 0; j
< arr
.length
; j
++){
var bucket
= parseInt((arr
[j
] % mod
) / dev
);
if (count
[bucket
] == null){
count
[bucket
] = [];
}
count
[bucket
].push(arr
[j
]);
}
var pos
= 0;
for (var j
= 0; j
< count
.length
; j
++){
var value
= null;
if (count
[j
] != null){
while((value
= count
[j
].shift()) != null){
arr
[pos
++] = value
;
}
}
}
}
return arr
;
}
var arr
= [20,2,5,9,62,52,33,7,41,22,8];
document
.getElementById("radixsort").innerHTML
= radixsort(arr
);
</script
>
</html
>
如果发现哪里有错误还请多多指正，路漫漫其修远兮，我们一起加油呀！
文章参考：https://www.cnblogs.com/onepixel/articles/7674659.html
