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;
}
}
}
冒泡為穩(wěn)定排序：輔助空間: O(1)
平均復(fù)雜度：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 ; // 記得跳出本次循環(huán)
}
}
}
}
直接插入為穩(wěn)定算法破衔，輔助空間為O(1)
平均時間復(fù)雜度：n^2清女，最好: n, 最壞：n^2，不適合基本有序時
希爾排序（直接插入的基礎(chǔ)上增加步進）
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
}
// 百度實現(xiàn)方案
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] // 取無序數(shù)組最后一個數(shù)為基準(zhǔn)值
while (i < j) {//把所有比基準(zhǔn)值小的數(shù)放在左邊大的數(shù)放在右邊
while (i < j && arr[i] <= baseVal) { //找到一個比基準(zhǔn)值大的數(shù)交換
i++
}
arr[j] = arr[i] // 將較大的值放在右邊如果沒有比基準(zhǔn)值大的數(shù)就是將自己賦值給自己（i 等于 j）
while (j > i && arr[j] >= baseVal) { //找到一個比基準(zhǔn)值小的數(shù)交換
j--
}
arr[i] = arr[j] // 將較小的值放在左邊如果沒有找到比基準(zhǔn)值小的數(shù)就是將自己賦值給自己（i 等于 j）
}
arr[j] = baseVal // 將基準(zhǔn)值放至中央位置完成一次循環(huán)（這時候 j 等于 i ）
sort(arr, left, j-1) // 將左邊的無序數(shù)組重復(fù)上面的操作
sort(arr, j+1, right) // 將右邊的無序數(shù)組重復(fù)上面的操作
}
const newArr = array.concat() // 為了保證這個函數(shù)是純函數(shù)拷貝一次數(shù)組
sort(newArr)
return newArr
}
快排為不穩(wěn)定排序嫡丙，輔助空間：log2n ~ n
平均時間復(fù)雜度：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）曙博，
//作為根時，子節(jié)點可能比它大怜瞒，因此要繼續(xù)調(diào)整
}
}
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]表示的是最后一個有子節(jié)點 (本來是n/2（堆從1數(shù)起）父泳，但是這里arr索引是從0開始般哼，所以-1)
for (var i = Math.floor(len/2)-1; i>=0; i--) {
maxHeapify(arr, i);
}
//對每一個節(jié)點（非葉節(jié)點），做堆調(diào)整
}
function maxHeapify(arr, i) { //堆調(diào)整
var left = 2*i+1,
right = 2*i+2,
largest = i; //i為該子樹的根節(jié)點
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); //交換最大的為父節(jié)點
maxHeapify(arr, largest); //交換后惠窄，原值arr[i]（往下降了）（索引保存為largest）蒸眠，
//作為根時，子節(jié)點可能比它大杆融，因此要繼續(xù)調(diào)整
}
}
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()方法用于把數(shù)組的第一個元素從其中刪除楞卡，并返回第一個元素的值。*/
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) { //動態(tài)定義間隔序列
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;
}
