/* 手撕排序 + 算法总结 */
//比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
//非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
// 1.冒泡排序
//时间复杂度O(n^2) 最好情况O(n)，空间O(1) 稳定
//它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
//走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
var num = [1,2,4,3,5,6,8,7,9]
var bubbleSort = function(num){
var temp=0;
var i=num.length;
while(i--){
for(let j=0;j<i-1;j++){
if(num[j]>num[j+1]){
temp = num[j+1];
num[j+1]=num[j];
num[j]=temp;
}
}
}
return num;
}
var a=bubbleSort(num);
console.log(a);
// 2.选择排序
//时间复杂度O(n^2) 最好情况O(n^2)，空间O(1) 不稳定
//首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
//然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
var selectionSort = function(num){
for(let i=0;i<num.length;i++){
let temp=0;
for(let j=i+1;j<num.length;j++){
if(num[i]>num[j]){
temp=num[j];
num[j]=num[i];
num[i]=temp;
}
}
}
return num;
}
var b=selectionSort(num);
console.log(b);
// 3.插入排序
//时间复杂度O(n^2) 最好情况O(n)，空间O(1) 稳定
//通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
var insertionSort = function(num){
var temp=0;
for(let i=0;i<num.length;i++){
for(let j=i;j>0;j--){
temp = num[j];
if(num[j]<num[j-1]) num[j] = num[j-1];
else{
num[j]=temp;
break;
}
}
}
return num;
}
var c=insertionSort(num);
console.log(c)
// 4.归并排序
//该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
//将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
var d=mergeSort(num);
console.log(d);
// 5.快速排序
//通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，
//则可分别对这两部分记录继续进行排序，以达到整个序列有序。
//steps
//从数列中挑出一个元素，称为 “基准”（pivot）；
//重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
//递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
var quickSort = function(nums){
var len = nums.length;
if(len<2) return nums;
var pivot = nums[Math.floor(len/2)];
var left = 0,right = nums.length-1;
var temp = 0;
while(left!=right){
if(nums[left]<pivot) left++;
if(nums[right]>pivot) right--;
temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
}
quickSort(nums.slice(0,left));
quickSort(nums.slice(right,len));
return nums;
}
var e=quickSort(num);
console.log(e);
查看9道真题和解析