今天来学习一下数据结构课程中非常重要的排序算法。
我们学习一下一些常见的排序算法，如冒泡排序、选择排序、快速排序等。
1、冒泡排序实现思路：
对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
如果左边的队员大, 则两队员交换位置
向右移动一个位置, 比较下面两个队员
当走到最右端时, 最大的队员一定被放在了最右边
按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.
依次类推, 就可以将数据排序完成
我们用数组来存放每一项数据，每次又从左端开始称为新的一趟，排序的趟数为数组长度减一；第一趟比较的次数也是数组长度减一，每增加一趟比较次数就会对应减一。
知道了这些我们通过代码实现：
//排序数组
var arr=[5,4,2,14,7,3,9]
//趟数
for (let i = 0; i < arr.length-1; i++) {
//每一趟的比较次数
for (let j = 0; j < arr.length-1-i; j++) {
if (arr[j]>arr[j+1]) {
let temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp
}
}
}
console.log(arr);//[2, 3, 4, 5, 7, 9, 14]
2、选择排序
选择排序改进了冒泡排序, 将交换的次数由O(N²)减少到O(N), 但是比较的次数依然是O(N²)
实现思路：
选定第一个索引位置，然后和后面元素依次比较
如果后面的队员, 小于第一个索引位置的队员, 则交换位置
经过一轮的比较后, 可以确定第一个位置是最小的
然后使用同样的方法把剩下的元素逐个比较即可
可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后
排序的趟数也是数组的长度-1，每一趟将找到对应的最小值依次从前往后排。
代码实现：
var arr=[5,4,2,14,7,3,9]
//趟数
for (let i = 0; i < arr.length-1; i++) {
//最小值
let min=i
//判断每次的最小值
for (let j = i+1; j < arr.length; j++) {
if (arr[min]>arr[j]) {
min=j
}
}
//将初始设定的最小值与找到的最小值交互
let temp=arr[min]
arr[min]=arr[i]
arr[i]=temp
}
console.log(arr);
3、插叙排序
插入排序是简单排序中效率最好的一种.
插入排序也是学习其他高级排序的基础, 比如希尔排序/快速排序, 所以也非常重要.
插叙排序的实现的核心是局部排序
局部排序：比如在一个队列中的人, 我们选择其中一个作为标记的队员. 这个被标记的队员左边的所有队员已经是局部有序的.
这意味着, 有一部门人是按顺序排列好的. 有一部分还没有顺序.
实现思路：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后, 重复上面的步骤.
实现代码：
var arr = [5, 4, 2, 14, 7, 3, 9]
//循环判断每一个元素
for (let i = 1; i < arr.length; i++) {
//从下标1开始，因为最开始数组第一个元素即下标取0的元素默认以及排好序了
let j = i
//设置一个变量标记一下每次插入的那个元素
let mark = arr[i]
// console.log(mark);
while (j > 0 && arr[j - 1] > mark) {
//直到找到合适的位置才会跳出循环
arr[j] = arr[j - 1]
j-- //向前找
}
//把我们要插入的那个元素插入到我们找到的位置
arr[j] = mark
}
console.log(arr);
高级排序
快速排序
快速排序几乎可以说是目前所有排序算法中, 最快的一种排序算法.
当然, 没有任何一种算法是在任意情况下都是最优的, 比如希尔排序确实在某些情况下可能好于快速排序. 但是大多数情况下, 快速排序还是比较好的选择.
快速排序是什么?
快速排序其实是我们学习过的最慢的冒泡排序的升级版.
我们知道冒泡排序需要经过很多次交换, 才能在一次循环中, 将最大值放在正确的位置.
而快速排序可以在一次循环中(其实是递归调用)找出某个元素的正确位置, 并且该元素之后不需要任何移动.
快速排序的思想:
快速排序最重要的思想是分而治之.
比如我们下面有这样一顿数字需要排序:
第一步: 从其中选出了65. (其实可以是选出任意的数字, 我们以65举个栗子)
第二步: 我们通过算法: 将所有小于65的数字放在65的左边, 将所有大于65的数字放在65的右边.
第三步: 递归的处理左边的数据.(比如你选择31来处理左侧), 递归的处理右边的数据.(比如选择75来处理右侧, 当然选择81可能更合适)
最终: 排序完成
和冒泡排序不同的是什么呢?
我们选择的65可以一次性将它放在最正确的位置, 之后不需要任何移动.
需要从开始位置两个两个比较, 如果第一个就是最大值, 它需要一直向后移动, 直到走到最后.
也就是即使已经找到了最大值, 也需要不断继续移动最大值. 而快速排序对数字的定位是一次性的.
代码实现：
var arr = [5, 4, 2, 14, 7, 3, 9]
function quicksort(arr){
//如果数组只只有一个或者为空就不用排序
if (arr.length<=1) {
return arr
} else {
// 找出数组中间的那个数，如果是偶数位时取前一位
let middle=Math.floor(arr.length/2)
//将这一位移除
let newarr = arr.splice(middle,1)
// console.log(newarr);
let arrleft=[]//用于接收小于middle位值得数
let arrright=[]//用于接收大于middle位值得数
arr.forEach(el => {
if (el
归并排序
基本思想与过程：先递归的分解数列，再合并数列（分治思想的典型应用）
（1）将一个数组拆成A、B两个小组，两个小组继续拆，直到每个小组只有一个元素为止。
（2）按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。
（3）对左右两个小数列重复第二步，直至各区间只有1个数。
代码实现：
var arr = [5, 4, 2, 14, 7, 3, 9]
//拆分
function divide(arr){
//如果数组长度小于1就不要拆分了，因为一个数据默认就是有序得
if (arr.length<=1) {
return arr
} else {
let middle=Math.floor(arr.length/2)
let arrleft=arr.slice(0,middle)
// console.log(arrleft);
let arrright=arr.slice(middle)
// console.log(arrright);
//合并并递归
return hebing(divide(arrleft),divide(arrright))
}
}
//合并
function hebing(arrleft,arrright){
let arr=[]
while (arrleft.length>0 && arrright.length>0) {
if (arrleft[0]
