面试必问:排序算法,废话不多说,直接上代码[node.js]

摘要：百度渣渣搜出来的都是版本很少见简单版本我正好自己搞了一版分享给你们冒泡排序交换和每次最大元素就像气泡一样浮到数组的最后依次比较相邻的两个元素使较大的那个向后移如果条件改成则变为不稳定的排序算法从小到大排序选择排

百度渣渣搜出来的都是c,c++,java版本,很少见简单js版本,我正好自己搞了一版,分享给你们

//1.冒泡排序
var exchange = function (a, i, j)        // 交换A[i]和A[j]
{
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

var sort = function (a) {
  var n = a.length;
  for (var j = 0; j < n - 1; j++)            // 每次最大元素就像气泡一样"浮"到数组的最后
  {
    for (var i = 0; i < n - 1 - j; i++)    // 依次比较相邻的两个元素,使较大的那个向后移
    {
      if (a[i] > a[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
      {
        exchange(a, i, i + 1);
      }
    }
  }

  return a;
}
var a = [6, 5, 3, 1, 8, 7, 2, 4];    // 从小到大排序
// console.log(sort(a))


//------------2.选择排序------------
var exchange = function (a, i, j)        // 交换A[i]和A[j]
{
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

var selectSort = function (a) {
  var n = a.length;
  var i, j, min;
  for (i = 0; i <= n - 2; i++)                // 已排序序列的末尾
  {
    min = i;
    for (j = i + 1; j <= n - 1; j++) {  // 未排序序列
      if (a[j] < a[min])// 依次找出未排序序列中的最小值,存放到已排序序列的末尾
      {
        min = j;
      }
    }
    if (min != i) {
      exchange(a, min, i);    // 该操作很有可能把稳定性打乱,所以选择排序是不稳定的排序算法
    }
  }
  return a;
}
var a = [6, 5, 3, 1, 8, 7, 2, 4];    // 从小到大排序
console.log(selectSort(a))


//-----------3.插入排序------------

var insertSort = function (a) {
  var n = a.length;
  var i, j, get;
  for (i = 1; i < n; i++)             // 类似抓扑克牌排序
  {
    get = a[i];                     // 右手抓到一张扑克牌
    j = i - 1;                      // 拿在左手上的牌总是排序好的
    while (j >= 0 && a[j] > get)    // 将抓到的牌与手牌从右向左进行比较
    {
      a[j + 1] = a[j];            // 如果该手牌比抓到的牌大,就将其右移
      j--;
    }
    a[j + 1] = get;// 直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)
  }
  return a;
}
var a = [6, 5, 3, 1, 8, 7, 2, 4];    // 从小到大排序
console.log(insertSort(a))


//-----------4.shell排序------------

var shellSort = function (a) {
  var n = a.length;
  var i, j, get;
  var h = 0;
  while (h <= n)                          // 生成初始增量
  {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (i = h; i < n; i++) {
      j = i - h;
      get = a[i];
      while ((j >= 0) && (a[j] > get)) {
        a[j + h] = a[j];
        j = j - h;
      }
      a[j + h] = get;
    }
    h = (h - 1) / 3;                    // 递减增量
  }
  return a;
}
var a = [6, 5, 3, 1, 8, 7, 2, 4];    // 从小到大排序
console.log(shellSort(a))


//-----------5.快速排序----------------
var exchange = function (a, i, j)        // 交换A[i]和A[j]
{
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

var partition = function (a, left, right)  // 划分函数
{
  var pivot = a[right];                    // 选择最后一个元素作为基准
  var tail = left - 1;                     // tail为小于基准的子数组最后一个元素的索引
  for (var i = left; i < right; i++)       // 遍历基准以外的其他元素
  {
    if (a[i] <= pivot)                   // 把小于等于基准的元素放到前一个子数组中
    {
      tail++;
      exchange(a, tail, i);
    }
  }
  exchange(a, tail + 1, right);            // 最后把基准放到前一个子数组的后边,剩下的子数组既是大于基准的子数组
  // 该操作很有可能把后面元素的稳定性打乱,所以快速排序是不稳定的排序算法
  return tail + 1;                         // 返回基准的索引
}

var quicksort = function (a, left, right) {
  var pivot_index;                        // 基准的索引
  if (left < right) {
    pivot_index = partition(a, left, right);
    quicksort(a, left, pivot_index - 1);
    quicksort(a, pivot_index + 1, right);
  }
  return a;
}
var a = [6, 5, 3, 1, 8, 7, 2, 4];    // 从小到大排序
console.log(quicksort(a, 0, a.length - 1))