# 排序算法

function bubbleSort(arr) {
    for(var i = 0, len = arr.length - 1; i < len; i++) {
        for(var j = i + 1, l = arr.length; j < l; j++) {
            if (arr[i] > arr[j]) {
                var item = arr[i];
                arr[i] = arr[j];
                arr[j] = item;
            }
        }
    }
    return arr;
}

const data = [3,2,5,1,7,9];

bubbleSort(data);

function insertSort(arr) {
    var inner;
    for(var i = 1, len = arr.length; i < len; i++) {
        var temp = arr[i];
        inner = i;
        while(inner > 0 && arr[inner - 1] >= temp) {
            arr[inner] = arr[inner - 1];
            inner--;
        }
        arr[inner] = temp;
    }
    return arr;
}

const data = [3,2,5,1,7,9];

insertSort(data);

function selectSort(arr) {
    for(var i = 0, len = arr.length - 1; i < len; i++) {
        var min = i;
        for(var j = i +1, l = arr.length; j < l; j++) {
            min = arr[j] < arr[min] ? j : min;
        }
        if (arr[min] < arr[i]) {
            var item = arr[i];
            arr[i] = arr[min];
            arr[min] = item;
        }
    }
    return arr;
}

const data = [3,2,5,1,7,9];

selectSort(data);

function shellSort(array) {
  // 定义间隔序列，这里写死了，可以动态定义
  const gaps = [5, 3, 1];
  for (let index = 0; index < gaps.length; index++) {
    const gap = gaps[index];

    for (let outer = gap; outer < array.length; outer++) {
      // 检查的数字
      const temp = array[outer];
      for (
        let inner = outer - gap;
        // 如果比之前的 gap 小，就交换一下，直到交换到第一个 gap 处
        inner >= 0 && array[inner] > temp;
        inner -= gap
      ) {
        swap(array, inner, inner + gap);
      }
    }
  }
  return array;
}

function swap(array, index1, index2) {
  var temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
}

function qSort(list) {
  if (list.length == 0) {
    return [];
  }
  var pivot = list[0];
  var lesser = [];
  var greater = [];
  for (var i = 1; i < list.length; i++) {
    if (list[i] < pivot) {
      lesser.push(list[i]);
    } else {
      greater.push(list[i]);
    }
  }
  return qSort(lesser).concat(pivot, qSort(greater));
}
var myArray = [2, 3, 1, 9, 6, 4, 7, 8, 5];
var arr = qSort(myArray);
console.log(arr);

// 归并排序算法
function mergeSort(array) {
  // 避免污染传入的数组
  const temp = [...array];
  splitArray(temp, 0, array.length - 1);
  return temp;
}

// 将大数组拆分成两个小数组
function splitArray(array, start, end) {
  if (start < end) {
    const mid = Math.floor((start + end) / 2);
    splitArray(array, 0, mid);
    splitArray(array, mid + 1, end);
    mergeArray(array, start, mid, end);
  }
}

// 合并两个排序好的数组
function mergeArray(array, start, mid, end) {
  var i = start;
  var j = mid + 1;
  var k = 0;
  var temp = [];
  while (i <= mid && j <= end) {
    if (array[i] <= array[j]) {
      temp[k] = array[i];
      i++;
    } else {
      temp[k] = array[j];
      j++;
    }
    k++;
  }

  while (i <= mid) {
    temp[k] = array[i];
    i++;
    k++;
  }

  while (j <= end) {
    temp[k] = array[j];
    j++;
    k++;
  }

  for (let index = 0; index < k; index++) {
    array[index + start] = temp[index];
  }
}
var arr = [2, 3, 7, 9, 8, 5, 4, 6, 1];
console.log('原始数组：', arr);
const result = mergeSort(arr);
console.log('排列后数组：', result);