排序

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');


function sort(arr) {
  let temp;
// 优化点，如果某次冒泡并没有交换，那后面都不需要交换了
  let flag = false;
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = true;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }

    }
    if (flag) {
      flag = false;
    } else {
      break;
    }
  }
}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');


function sort(arr) {
  let temp;
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    temp = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
console.log(arr);

function sort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let insert = i - 1;
    let temp = arr[i];
    while (insert >= 0 && temp < arr[insert]) {
      arr[insert + 1] = arr[insert];
      insert--;
    }
    arr[insert + 1] = temp;
  }
}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');

function sort(arr) {
  let len = arr.length;
  let temp;
  do {
    len = Math.floor(len / 2);
    for (let i = len; i < arr.length; i++) {
      for (let j = i - len; j >= 0; j -= len) {
        if (arr[j + len] < arr[j]) {
          temp = arr[j];
          arr[j] = arr[j + len];
          arr[j + len] = temp;
        }
      }
    }
  } while (len > 1);
}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');


function sort(arr) {
  let gap = Math.floor(arr.length / 2);
  while (gap >= 1) {
    for (let i = gap; i < arr.length; i++) {
      let j = i - gap;
      let temp = arr[i];
      while (j >= 0 && temp < arr[j]) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = temp;
      // let j = i;
      // let temp = arr[j];
      // if (arr[j] < arr[j - gap]) {
      //   while (j - gap >= 0 && temp < arr[j - gap]) {
      //     arr[j] = arr[j - gap];
      //     j -= gap;
      //   }
      //   arr[j] = temp
      // }


    }
    gap = Math.floor(gap / 2);
  }
}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');



function sort(arr, left, right) {
  let l = left;
  let r = right;
  const middle = arr[Math.floor((left + right) / 2)];
  let temp;
  while (l < r) {
    while (arr[l] < middle) {
      l++;
    }
    while (arr[r] > middle) {
      r--;
    }
    if (l == r) {
      r -= 1;
      l += 1;
      break;
    }
    temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
    //  减少一次没必要的比较
     if(arr[l]==middle){
      r--;
    }else if(arr[r]==middle){
      l++;
    }else{
      l++;
      r--;
    }
  }
  if (left < r) {
    sort(arr, left, r)
  }
  if (right > l) {
    sort(arr, l, right)
  }

}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');




function sortOrigin(arr, left, mid, right) {
    let i = left;
    let j = mid + 1;
    let temp = [];
    let t = 0;

    while (i <= mid && j <=  right) {

        if (arr[i] < arr[j]) {
            temp[t] = arr[i];
            i++;

        } else {
            temp[t] = arr[j];
            j++;
        }
        t++;
    }
    while (i < mid) {
        temp[t] = arr[i];
        i++;
        t++;
    }
    while (j < right) {
        temp[t] = arr[j];
        j++;
        t++;
    }
    t = 0;
    while (left <= right) {
        arr[left] = temp[t];
        t++;
        left++;
    }


}

function sort(arr, left, right) {
    if (left < right) {
        let mid = Math.floor((left + right) / 2);
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        sortOrigin(arr, left, mid, right)
    }

}

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');

function sort(arr) {
  var max = 0;
  for (let i = 0; i < arr.length; i++) {
    max = Math.max(max, arr[i]);
  }
  var maxLength = (max + '').length;
  let bet = [];
  for (let i = 0; i < 10; i++) {
    bet[i] = [];
  }
  let betLength = new Array(10).fill(0);

  for (let i = 0, step = 1; i < maxLength; i++, step *= 10) {
    for (let j = 0; j < arr.length; j++) {
      let num = Math.floor(arr[j] / step) % 10;
      bet[num][betLength[num]] = arr[j];
      betLength[num]++;
    }
    let t = 0;
    for (let k = 0; k < 10; k++) {
      if (betLength[k]) {
        for (let d = 0; d < betLength[k]; d++) {
          arr[t] = bet[k][d];
          t++;
        }
        betLength[k] = 0;
      }
    }
  }

}

sort(arr);

let arr = [];
for (let i = 0; i < 80000; i++) {
  arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');

function start(arr) {
  var i = Math.floor(arr.length / 2) - 1
  for (var j = i; j >= 0; j--) {
    sort(arr, j, arr.length)
  }
  var temp;
  for (var j = arr.length - 1; j > 0; j--) {
    temp = arr[j];
    arr[j] = arr[0];
    arr[0] = temp;
    sort(arr, 0, j)
  }
}

function sort(arr, i, len) {
  let temp = arr[i];
  for (let j = i * 2 + 1; j < len; j = j * 2 + 1) {
    if (j + 1 < len && arr[j] < arr[j + 1]) {
      j++;
    }
    if (temp < arr[j]) {
      arr[i] = arr[j]
      i = j
    } else {
      break;
    }
  }
  arr[i] = temp;

}
start(arr)