记录学习排序的过程
1.冒泡排序
冒牌排序就是每次比较相邻的两个数的数值，前者如果比后者大就交换位置，一次遍历下来可以找出最大的数值，并且把它放在数组的最后。第二次遍历就找出次最大的项并且把它放到最后。如此循环...
function bubbleSort(array) {
let len = array.length
for(let i=0; i<len-1; i++) {
for(let j=0; j<len-i-1; i++) {
if(array[j] > array[j+1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]]
}
}
}
}
let arr = [56, 65, 1, 3, 5, 79, 13, 25, 63, 34, 388, 412, 65, 20, 22]
bubbleSort(arr) // [1, 3, 5, 13, 20, 22, 25, 34, 56, 63, 65, 65, 79, 388, 412]
遍历的时候也可以反向遍历
function bubbleSort(array) {
let len = array.length
for(let i=len-1; i>=0; i--) {
for(let j=0; j<i; j++) {
if(array[j] > array[j+1]) {
[array[j], array[j+1]] = [array[j+1], array[j]]
}
}
}
}
let arr = [56, 65, 1, 3, 5, 79, 13, 25, 63, 34, 388, 412, 65, 20, 22]
bubbleSort(arr) // [1, 3, 5, 13, 20, 22, 25, 34, 56, 63, 65, 65, 79, 388, 412]
冒泡排序的效率及稳定性
- 对于n项的数组，要比较(n-1)+(n-2)+...+1 = n*(n-1)/2次，所以大O法表示时间复杂度：O(n2)
- 从稳定性上来看，排序前值相同的两个元素的相对位置在排序后不改变，所以冒泡排序是稳定的。
2.选择排序
选择排序与冒泡排序有相似之处，选取一个元素与后面的元素一次比较，一次遍历之后可以找到最小的那个元素，数次遍历之后排序完成。
function selectSort(arr) {
let len = arr.length
for(let i=0; i<len-1; i++) {
for(let j=i+1; j<len; j++) {
if(arr[j] < arr[i]) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
}
}
let array = [10,2,13,5,26,799,1,33,21,51]
selectSort(array) //[1, 2, 5, 10, 13, 21, 26, 33, 51, 799]
选择排序的效率及稳定性
- 选择排序的交换次数是O(n)，但是比较次数还是O(n2)，所以时间复杂度还是O(n2)
- 稳定性来看，假设当前元素在后续项中找到最小值并与之交换，但是该最小值的前一项的值与当前值相等，此时稳定性被破坏，所以选择排序是不稳定的。例子如下：
[5(a), 7, 6, 5(b), 1, 3] --> [1, 7, 6, 5(b), 5(a), 3]
为了区分两个相同的项，在它们后面加上a，b以区分。显然，5(a)位于5(b)前面。
假设当前项为5(a)，在第一轮遍历中找到最小值1，并且与之交换。
交换后可以看到，5(a)在5(b)的后面，它们两个的相对位置发生了变换，不符合稳定性。
3.插入排序
插入排序就是在数组中取出某一元素，把该元素之前的序列视为已经排好序的序列，再拿当前的数与前面有序的数列的项比较，找到准确的位置进行赋值。
function insertSort(array) {
let len = array.length
for(let i=1; i<len; i++) {
let j, temp = array[i] //记录当前值
for(j=i-1; j>=0 && array[j]>temp; j--) { //判断当前值与之前面的数的数值关系
array[j+1] = array[j] //如果当前值小于前面的值，把前面大的值赋值给当前值
}
array[j+1] = temp //最后把当前的值放进去对应的位置
}
}
let arr = [6,12,4,1,13,22,26,20,14,33,7,9]
insertSort(arr) //[1, 4, 6, 7, 9, 12, 13, 14, 20, 22, 26, 33]
-
示例如下
示例.png
插入排序的效率及稳定性
- 第一趟最多1次比较，第二趟最多2次比较，以此类推，最后一趟是n-1次
- 1 + 2 + 3 + ... + n-1 = n*(n - 1) / 2
- 每次插入前，平均只有一般数据需要比较，所以 n*(n-1)/4，相对于其他排序，比较次数少一半，但还是O(n2)
- 插入排序是稳定的，如果A在有序的序列内，如果B与A一样，B会被放到A的后面
