JavaScript之排序集锦

JavaScript 之排序集锦

---

1、快速排序

单独开辟两个存储空间 left 和 right 来存储每次递归比 target 小和大的序列,每次递归直接返回 left 、 target 、 right 拼接后的数组.
浪费大量存储空间,写法简单.

function quickSort(array) {
  if (array.length < 2) {
    return array;
  }
  const target = array[0];
  const left = [];
  const right = [];
  for (let i = 0; i < array.length; i++) {
    if (array[i] < target) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }
  return;
  quickSort(left).concat([target], quickSort(right));
}

---

2、归并排序

利用归并的思想实现的排序方法。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

• 将已有序的子序列合并，得到完全有序的序列
• 即先使每个子序列有序，再使子序列段间有序
• 若将两个有序表合并成一个有序表，称为二路归并

分割数组时直接将数组分割为两个数组，合并时直接合并数组

function merge(front, end) {
  const temp = [];
  while (front.length && end.length) {
    if (front[0] < end[0]) {
      temp.push(front.shift());
    } else {
      temp.push(end.shift());
    }
  }
  while (front.length) {
    temp.push(front.shift());
  }
  while (end.length) {
    temp.push(end.shift());
  }
  return temp;
}

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const front = array.slice(0, mid);
  const end = array.slice(mid);
  return merge(mergeSort(front), mergeSort(end));
}

---

3、选择排序

每次循环选取一个最小的数字放到前面的有序序列中.

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    [array[minIndex], array[i]] = [array[i], array[minIndex]];
  }
  return array;
}

---

4、插入排序

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。
插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

function insertSort(array) {
  for (let i = 1; i < array.length; i++) {
    let target = i;
    for (let j = i - 1; j >= 0; j--) {
      if (array[target] < array[j]) {
        [array[target], array[j]] = [array[j], array[target]];
        target = j;
      } else {
        break;
      }
    }
  }
  return array;
}

---

5、冒泡排序

• 循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。
• 这样一次循环之后最后一个数就是本数组最大的数。
• 下一次循环继续上面的操作，不循环已经排序好的数。
• 优化：当一次循环没有发生冒泡，说明已经排序完成，停止循环。

function bubbleSort(array) {
  for (let j = 0; j < array.length; j++) {
    let complete = true;
    for (let i = 0; i < array.length - j - 1; i++) {
      // 比较相邻数
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        complete = false;
      }
    }
    // 没有冒泡结束循环
    if (complete) {
      break;
    }
  }
  return array;
}

---

6、堆排序

• 创建一个大顶堆，大顶堆的堆顶一定是最大的元素。
• 交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。
• 从后往前以此和第一个元素交换并重新构建，排序完成。

// 构建大顶堆, 从第一个非叶子节点开始, 进行下沉操作.
function createHeap(array) {
  const len = array.length;
  const start = parseInt(len / 2) - 1;
  for (let i = start; i >= 0; i--) {
    adjust(array, i, len);
  }
}
// 将第target个元素进行下沉, 孩子节点有比他大的就下沉
function adjust(array, target, len) {
  for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
    // 找到孩子节点中最大的
    if (i + 1 < len && array[i + 1] > array[i]) {
      i = i + 1;
    }
    // 下沉
    if (array[i] > array[target]) {
      [array[i], array[target]] = [array[target], array[i]];
      target = i;
    } else {
      break;
    }
  }
}
function heapSort(array) {
  createHeap(array);
  // 交换第一个和最后一个元素, 然后重新调整大顶堆
  for (let i = array.length - 1; i > 0; i--) {
    [array[i], array[0]] = [array[0], array[i]];
    adjust(array, 0, i);
  }
  return array;
}

---

7、希尔排序

希尔排序的核心在于间隔序列的设定.既可以提前设定好间隔序列,也可以动态的定义间隔序列.动态定义间隔序列的算法是《算法(第4版)》 的合著者 Robret Sedgewick 提出的.

• 先将整个待排序记录序列分割成若干个子序列
• 在序列内分别进行直接插入排序,待整个序列基本有序时,在对全体记录进行一次直接插入排序

function shellSort(array) {
  let len = array.length;
  let gap = parseInt(len / 2);
  let i, j, temp, result;
  // 复制数组
  result = array.slice(0);
  while (gap > 0) {
    for (i = gap; i < len; i++) {
      temp = result[i];
      j = i - gap;
      while (j >= 0 && temp < result[j]) {
        result[j + gap] = result[j];
        j = j - gap;
      }
      result[j + gap] = temp;
    }
    gap = parseInt(gap / 2);
  }
  return result;
}

---

8、计数排序

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
• 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1

function countingSort(array, maxValue) {
  let bucket = new Array(maxValue + 1);
  let sortIndex = 0;
  let bucketLen = maxValue + 1;
  for (let i = 0; i < array.length; i++) {
    if (!bucket[array[i]]) {
      bucket[array[i]] = 0;
    }
    bucket[array[i]]++;
  }
  for (let j = 0; j < bucketLen; j++) {
    while (bucket[j] > 0) {
      array[sortIndex++] = j;
      bucket[j]--;
    }
  }
  return array;
}

---

9、桶排序

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

function bucketSort(arr, bucketSize) {
  if (arr.length === 0) {
    return arr;
  }
  let minValue = arr[0];

  let maxValue = arr[0];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i]; //输入数据的最小值
    } else if (arr[i] > maxValue) {
      maxValue = arr[i]; //输入数据的最大值
    }
  } //桶的初始化
  const DEFAULT_BUCKET_SIZE = 5; //设置桶的默认数量为5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;

  let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let buckets = new Array(bucketCount);

  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  } //利用映射函数将数据分配到各个桶中
  for (let i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }

  arr.length = 0;

  for (let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]); //对每个桶进行排序，这里使用了插入排序
    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }

  return arr;
}

---

10、基数排序

• 该算法是稳定的排序法；
• 在所有的情况下，时间复杂度均为 O(nlog(p)k)，空间复杂度为 O(n*p)
  （其中 K 为关键词位数，p 为数据字符数(即基数 radix)）；
• 若 n 很大，p 固定或很小，此方法将很有效。
• 基数排序不需要进行元素间的比较，属于分配/分布排序；
• 根据起始方向可分为 最高位优先 MSD 和 最低位优先 LSD

function radixSort(arr, n, radix) {
  if (!radix) {
    //默认为十进制
    radix = 10;
  }
  if (!n) {
    //如果未指定关键词位数将自动使用首个元素的位数作为n
    n = arr[0].toString().length;
  }
  var i,
    j,
    tmp,
    num,
    queues = [],
    q = arr.slice();
  for (i = 0; i < radix; i++) {
    queues.push([]); //生成Q[0]~Q[radix-1]
  }
  for (i = 0; i < n; i++) {
    //LSD低位起始
    while (q.length > 0) {
      tmp = q.shift();
      num = Math.floor((tmp / Math.pow(radix, i)) % radix); //获取某位数值
      //这里这个转换只能搞得动十进制= =其他就会有问题 因为不能直接用其他进制来进行运算 所以考虑使用字符串处理
      queues[num].push(tmp);
    }
    for (j = 0; j < radix; j++) {
      //重构q
      while (queues[j].length > 0) {
        q.push(queues[j].shift());
      }
    }
  }
  return q;
}