在学习了极客时间的数据结构之后，根据排序的原理，我用JS重新实现了一遍，配图来自极客时间的配图，因为我实在找不出比他写的更好的了。
学习方法：
讲排序之前，先说一下学习方法，那就是debug模式，在JS中，直接在循环里添加debugger，打开F12，F5刷新一下，就可以看到数组的变化情况了，对学习非常有帮助，我就是这样学的，在Java中，则是Eclipse进入Debug模式，我还是喜欢JS，因为更直观。
学习方法
冒泡排序
原理：
冒泡排序是最简单的，只需要通过两次遍历，两两交换，就可以实现排序。
冒泡排序
代码：
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
//冒泡排序
function arrSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {//遍历，这里，arr.length-1，是因为最后一次不用循环了。
for (let j = 0; j < arr.length - i ; j++) {//双重遍历，遍历i之后的数，例如有8个元素，i在第一项，那么遍历后面7项。
if(arr[j] < arr[j-1]){//如果右边，小于左边，那么交换位置。
let temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
return arr;
}
console.log(arrSort(arr));
空间复杂度：因为只涉及到交换，只需要常量级的临时空间，所以空间复杂度为O(1)
时间复杂度：最好O(n)，最坏O(n²)，平均O(n²)
使用场景：数据量小于1000
稳定性：稳定
插入排序
原理：
1、从第二个元素开始，遍历它之前的元素。
2、如果他之前的元素，大于他，那么交换。并继续往前遍历之前比它大的元素。
插入排序原理图
代码实现：
//插入排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(array) {
for(let i = 1; i < array.length; i++) {//遍历一波数组,从数组第二项开始遍历
let key = array[i];//这里必须要定义，因为循环结束，会用到。
let j = i - 1;//定义j为i-1,在第一次遍历，是从数组第一项开始
while(j >= 0 && array[j] > key) {//如果j的值大于i的值，也就是左边的大于右边的，j>=0，防止j--变负数。
array[j + 1] = array[j];//例如第二项和第三项248和31，那么变成，248，248
j--;//如果248>31执行成功了，变成了248,248,那么依次判断左边，是否有小于 的。
}
array[j + 1] = key;//把第一项赋值成最小的那个。
}
return array;
}
console.log(arrSort(arr));
空间复杂度：因为不需要额外的存储空间，所以空间复杂度为O(1)
时间复杂度：最好O(n)，最坏O(n²)，平均O(n²)
使用场景：数据量小于1000
稳定性：稳定
选择排序
原理：跟冒泡排序差不多，也是两两交换，不过这两两交换，是第一位和第五位交换，而不是第四位和第五位。
选择排序
代码：
//选择排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(arr){
for(let i = 0; i < arr.length - 1; i++){//遍历数组
let min = arr[i];//防止arr[i]发生变化
for(let j = i + 1; j < arr.length - 1; j++){//双重遍历，查找最小的数进行交换，跟冒泡不一样的地方在于，选择排序，假如第4位更小，则是1，4位交换，不是3，4位交换
if(min > arr[j]){
let temp = min;
min = arr[j];
arr[j] = temp;
}
}
arr[i] = min;
}
return arr;
}
console.log(arrSort(arr));
空间复杂度：空间复杂度为O(1)
时间复杂度：最好O(n²)，最坏O(n²)，平均O(n²)
使用场景：数据量小于1000
稳定性：不稳定，因为会碰到重复的数。
归并排序
原理：归并排序使用了非常好的分治思想，把一个数组，分成两部分，排序之后，较小的那个值取出来放在第一个位置，再合并。
归并排序
代码：
//分治排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function merge(left, right) {
let result = [];
while(left.length > 0 && right.length > 0) {//如果两边数组都有值
if(left[0] < right[0]) {//左边小于右边
result.push(left.shift());//给result数组添加值，并在left删掉值
}
else {
result.push(right.shift());//给result数组添加值，并在right删掉值
}
}
/* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
return [...result,...left,...right];//这里用es6的语法，只是一个简写，百度一眼就会。...left...right是因为万一长度不相等，会少数，所以会加这两个。
}
function mergeSort(arr){
if(arr.length==1){//如果数组长度为1则返回数组
return arr
};
let mid=Math.floor(arr.length/2);//分成两部分
let left_arr=arr.slice(0,mid);//数组分成两份后，塞进去。假如说数组有8个元素，分成两部分，左边(0,4)
let right_arr=arr.slice(mid);//右边(4到后面所有)
return merge(mergeSort(left_arr),mergeSort(right_arr));//递归
}
console.log(mergeSort(arr));
空间复杂度：因为不是原地排序，需要其他的空间，所以空间复杂度为O(n)
时间复杂度：最好O(nlogn)，最坏O(nlogn)，平均O(nlogn)
使用场景：数据量大于1000
稳定性：稳定。
快速排序
原理：和归并排序一样，也是利用了分治思想，但是快排是选择一个中间数，然后比它小的放左边，比它大的放右边。
快速排序
代码：
//快速排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(arr){
if (arr.length <= 1){
return arr
};
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex,1)[0];//取出中间的数字，比如第一次就取出9
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if(arr[i] < pivot) {//第一次运算，如果小于9就进入左数组，大于就进入右数组
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return arrSort(left).concat([pivot],arrSort(right));//递归，再把左数组分成两半进行排序，右数组同理。
}
console.log(arrSort(arr));
空间复杂度：最好O(logn) 最差O(n)
时间复杂度：最好O(nlogn)，最坏O(n2) ，平均O(nlogn)
使用场景：数据量大于1000
稳定性：不稳定。
我们用快排比归并用的多，原因就在于归并他不是原地排序，空间复杂度比较高。
希尔排序
原理：
希尔排序是根据增量（中间隔一段距离），实现跳跃式的移动，使得排序的效率提高。在最后一轮中，增量必须等于1，另外，由于是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
举一个小小的例子：
一个数组有8个元素，8%2==4，第一轮中间隔4个，4%2==2，第二轮中间隔2个……
第一轮，第一项和第五项，第二项和第六项，第三项和第七项，第四项和第八项。
第二轮，第一项和第三项，第二项和第四项，第三项和第五项，第四项和第六项，第五项和第七项……
希尔排序，PPT工程师登场
//希尔排序
let arr = [145, 248, 31, 45, 9, 11, 145, 300];
function arrSort(arr){
let gap =Math.floor(arr.length/2);
while(gap>=1){
for(let i = gap;i<arr.length;i++){
let j,temp=arr[i];
for(j=i-gap;j>=0&&temp<arr[j];j=j-gap){
arr[j+gap]=arr[j];
}
arr[j+gap]=temp;
}
gap=Math.floor(gap/2);
}
return arr;
}
console.log(arrSort(arr));
空间复杂度：O(1)
时间复杂度：最好O(nlog²n)，最坏O(nlog²n)，平均O(nlogn)
使用场景：数据量大于1000
稳定性：不稳定。
此外，还有桶排序，计数排序，堆排序，基数排序等，作者还在研究当中。
网友评论