1. 冒泡排序
function maopao(arr){
var len = arr.length
for(var i = 0; i < len -1; i++){
var flag = true
// 最后几位是有序的
for(var j = 0; j < len - 1 - i; j++){
if(arr[j] > arr[j+1]){
var temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
flag = false
}
}
if(flag){
return null;
}
}
}
冒泡为稳定排序：辅助空间: O(1)
平均复杂度：n^2， 最好：n，最坏：n^2
2. 直接插入排序
function insertSort(arr){
var len = arr.length
for(var i = 0; i < len; i++){
for(var j = 0; j < i; j++){
if(arr[i] <= arr[j]){
// 将后面的元素插入前面(后面要删除，前面要插入)
var temp = arr.splice(i, 1)[0]
arr.splice(j, 0, temp) // 因为i在j后面，所以这里直接在j的后面插入即可，不必+1多此一举
break ; // 记得跳出本次循环
}
}
}
}
直接插入为稳定算法，辅助空间为O(1)
平均时间复杂度：n^2，最好: n, 最坏：n^2，不适合基本有序时
希尔排序（直接插入的基础上增加步进）
function shellSort(arr) {
var len = arr.length, temp;
var gap = Math.floor(len/2) // 定义间隔序列
for (gap; gap> 0; gap = Math.floor(gap/2)) {
for (var i = gap; i < len; i++) {
// 这里进行直接插入排序
for(var j = 0; j < i; j+=gap){
if(arr[j] > arr[i]){
var num = arr.splice(i, 1)[0]
arr.splice(j, 0, num)
break;
}
}
// temp = arr[i];
// for (var j = i-gap; j >= 0 && arr[j]> temp; j-=gap) {
// arr[j+gap] = arr[j];
// }
// arr[j+gap] = temp;
}
}
return arr;
}
3. 快速排序
function quickSort(arr, start, end){
// var start = start || 0
// var end = end || arr.length -1
// start，end 一定要传
if(start < end){
var mid = sort(arr, start, end)
// 对枢纽左右递归进行快排
quickSort(arr, start, mid-1)
quickSort(arr, mid+1, end)
}
}
function sort(arr, start, end){
// console.log(start, end)
var point = arr[end]
while(start < end){
while(arr[start] <= point && start < end){
start++
}
arr[end] = arr[start]
while(arr[end] >= point && start < end){
end--
}
arr[start] = arr[end]
}
arr[start] = point
return start
}
// 百度实现方案
const quickSort = (array) => {
const sort = (arr, left = 0, right = arr.length - 1) => {
if (left >= right) {//如果左边的索引大于等于右边的索引说明整理完毕
return
}
let i = left
let j = right
const baseVal = arr[j] // 取无序数组最后一个数为基准值
while (i < j) {//把所有比基准值小的数放在左边大的数放在右边
while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
i++
}
arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
j--
}
arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
}
arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
sort(arr, left, j-1) // 将左边的无序数组重复上面的操作
sort(arr, j+1, right) // 将右边的无序数组重复上面的操作
}
const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
sort(newArr)
return newArr
}
快排为不稳定排序，辅助空间：log2n ~ n
平均时间复杂度：nlog2n，最好: nlog2n, 最坏：n^2
5. 堆排序
https://blog.csdn.net/longpersevere/article/details/78400892
function buildMaxHeap(arr){
var len = arr.length;
for(var i = Math.floor(len/2)-1; i>=0; i--){
maxHeapify(arr, i, len)
}
}
function maxHeapify(arr, i, heapSize){
var left = 2*i + 1;
var right = 2*i + 2;
var largest = i;
if(left < heapSize && arr[left] > arr[largest]){
largest = left
}
if(right < heapSize && arr[right] > arr[largest]){
largest = right
}
// 说明有交换
if(largest != i){
swap(arr, i, largest) // 最大值作为堆顶
maxHeapify(arr, largest, heapSize)
//交换后，原值arr[i]（往下降了）（索引保存为largest），
//作为根时，子节点可能比它大，因此要继续调整
}
}
function swap(arr, i, j){
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
function heapSort(arr){
buildMaxHeap(arr);
var len = arr.length;
for(var i = arr.length - 1; i > 0; i--){
swap(arr, 0, i);
len --;
maxHeapify(arr, 0, len)
}
return arr;
}
var len;
function buildMaxHeap(arr) { //建堆
len = arr.length;
// [n/2-1]表示的是最后一个有子节点 (本来是n/2（堆从1数起），但是这里arr索引是从0开始，所以-1)
for (var i = Math.floor(len/2)-1; i>=0; i--) {
maxHeapify(arr, i);
}
//对每一个节点（非叶节点），做堆调整
}
function maxHeapify(arr, i) { //堆调整
var left = 2*i+1,
right = 2*i+2,
largest = i; //i为该子树的根节点
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) { //即上面的if中有一个生效了
swap(arr, i, largest); //交换最大的为父节点
maxHeapify(arr, largest); //交换后，原值arr[i]（往下降了）（索引保存为largest），
//作为根时，子节点可能比它大，因此要继续调整
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
maxHeapify(arr, 0);
}
return arr;
}
4. 归并排序（二路归并）
function mergeSort(items){
if(items.length == 1){
return items;
}
var middle = Math.floor(items.length/2),
left = items.slice(0, middle),
right = items.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]){
/*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
希尔排序
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
for (gap; gap> 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j]> temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
