各种排序的时间复杂度
对于以上的O可能有部分人不是很了解，O表示算法的性能和复杂度。(通常来说就是占用cpu的情况）
冒泡排序
就是两层for循环，前后两个值进行比较
function popSort() {
var a = [1,5,6,7,8,10,9,3,21,6];
var n=a.length;
var tem;
for(let i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
tem=a[j];
a[j]=a[j+1];
a[j+1]=tem;
}
}
}
}
把冒泡时间负责度缩小的办法
// 改进冒泡排序
function bubbleSort1(arr) {
let i = arr.length - 1;
while (i > 0) {
let pos = 0;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
pos = j;
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i = pos;
}
console.log(arr);
}
快速排序
采取的思想为分而治的思想，以基数来进行比较
// 快速排序
const quickSort = (arr, left, right) => {
let len = arr.length,
partitionIndex;
left = typeof left != 'number' ? 0 : left;
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
};
const partition = (arr, left, right) => {
//分区操作
let pivot = left, //设定基准值（pivot）
index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
};
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
快排不需要额外的内存空间，也就是原地排序算法
因为快排每次排序的要交换的元素可能是相邻的，也可能相隔几个的元素，所以说快排是不稳定的
快排的时间复杂度，极端情况 就是数组本身是有序的所以只要O(n), 如果数组是倒叙排列O(n2)，平均下来（O(nlngn)
堆排序
堆的插入就是——每次插入都是将新数据放在数组最后，而从这个新数据的父结点到根结点必定是一个有序的数列，因此只要将这个新数据插入到这个有序数列中即可。
