Skip to content

Latest commit

 

History

History
417 lines (323 loc) · 11.7 KB

4.排序算法.md

File metadata and controls

417 lines (323 loc) · 11.7 KB

排序算法

根据时间复杂度的不同，主流排序算法可以分为3类。

1.时间复杂度为 O(n2) 的排序算法。

  • 冒泡排序

  • 选择排序

  • 插入排序

  • 希尔排序（它的性能优于 O(n2) ，但又比不上 O(nlogn)。

2.时间复杂度为 O(nlogn) 的排序算法。

  • 快速排序

  • 归并排序

  • 堆排序

3.时间复杂度为线性 的排序。

  • 计数排序

  • 桶排序

  • 基数排序

此外，还可以根据其算法的稳定性分为，稳定排序和不稳定排序。即，如果值相同的元素在排序后仍然保持着排序前的顺序，则稳定；如果值相同的元素在排序后打乱了排序前的顺序，则不稳定。

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定排序
冒泡排序 O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(1) 不稳定
插入排序 O(n2) O(n2) O(1) 稳定
希尔排序 O(nlogn) ~ O(n2) O(n2) O(1) 不稳定
快速排序 O(nlogn) O(n2) O(nlogn) 不稳定
归并排序 O(nlogn) O(nlogn) O(n) 稳定
堆排序 O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n + m) O(n + m) O(m) 稳定
桶排序 O(n + m) O(n2) O(n + m) 稳定
基数排序 O(nm) O(nm) O(n + m) 稳定

冒泡排序

冒泡排序（bubble sort），是一种基础的交换排序。

思想：将相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

冒泡排序是一种稳定排序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量 - 1）轮，所以平均时间复杂度为 O(n2)。

代码实现：

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

function output() {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i])
  }
}

const array = [5, 8, 6, 3, 9, 2, 1, 7];

sort(array)

output() // 1 2 3 5 6 7 8 9

快速排序

快速排序也属于交换排序，与冒泡排序不同的是，在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。这种思路叫做分治法。

在分治法的思想下，原属列在每一轮都被拆成两部分，每一部分在下一轮又分别被拆成两部分，直到不可再分为止。每一轮的比较和交换需要把全部元素都遍历一遍，因此快速排序的时间复杂度为 O(nlogn)。

基准元素的选择

基准元素（pivot），在分治的过程中，以基准元素为中心，把其他元素移动到它的左右两边。

最简单的确定基准元素的方式是选择数列的第1个元素。但是在特殊的情况下，会存在问题，解决的办法是随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。

元素的交换

选定好基准元素后，把其他元素中小于它的都交换到它的一边，大于它的都交换到它的另一边。具体实现有两种方法。

1.双边循环法

2.单边循环法

代码实现：

/** 
 * 排序算法
 * 快速排序
*/

function quickSort(arr, startIndex, endIndex) {
  // 递归结束的条件: startIndex >= endIndex
  if (startIndex >= endIndex) {
    return;
  }
  // 得到基准元素的位置
  // let pivotIndex = partition(arr, startIndex, endIndex);
  let pivotIndex = partition2(arr, startIndex, endIndex);
  // 根据基准元素，分成两部分进行递归排序
  quickSort(arr, startIndex, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, endIndex);
}

/**
 * 分治（双边循环）
 * arr 待交换的数组
 * startIndex 起始下标
 * endIndex 结束下标
 */
function partition(arr, startIndex, endIndex) {
  // 取第一个位置（也可以随机选择位置）的元素作为基准元素
  let pivot = arr[startIndex];
  let left = startIndex;
  let right = endIndex;

  while (left !== right) {
    // 控制right指针比较并左移
    while (left < right && arr[right] > pivot) {
      right--;
    }
    // 控制left指针比较并右移
    while (left < right && arr[left] <= pivot) {
      left++;
    }
    // 交换left和right指针所指向的元素
    if (left < right) {
      let tmp = arr[left];
      arr[left] = arr[right];
      arr[right] = tmp;
    }
  }

  // pivot和指针重合点交换
  arr[startIndex] = arr[left]; // ? 不理解
  arr[left] = pivot;

  return left;
}

/**
 * 分治（单边循环）
 * arr 待交换的数组
 * startIndex 起始下标
 * endIndex 结束下标
 */
function partition2(arr, startIndex, endIndex) {
  // 取第一个位置（也可随机选择位置）的元素作为基准元素
  let pivot = arr[startIndex];
  let mark = startIndex;

  for (let i = startIndex + 1; i <= endIndex; i++) {
    if (arr[i] < pivot) {
      mark++;
      let tmp = arr[mark];
      arr[mark] = arr[i];
      arr[i] = tmp;
    }
  }

  arr[startIndex] = arr[mark];
  arr[mark] = pivot;
  return mark;
}

function output(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i])
  }
}


const array = [4, 4, 6, 5, 3, 2, 8, 1];

quickSort(array, 0, array.length - 1);

output(array) // 1 2 3 4 4 5 6 8

堆排序

根据二叉堆的特性，最大堆堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素，这样每次删除旧的堆顶，调整得到的新的堆顶的大小都是仅次于旧的堆顶的节点，那么只要反复删除堆顶，再反复调整二叉堆，所得到的集合就会是一个有序集合。。

堆排序算法的步骤：

1.把无序数组构建成二叉堆，需要从小到大排序，则构成最大堆；需要从大到小排序在，则构成最小堆。

2.循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

/** 
 * 排序算法
 * 堆排序
*/

/**
 * “下沉”调整
 * array 待调整的堆
 * parentIndex 要“下沉”的父节点
 * length 堆的有效大小
 */
function downAjust(array, parentIndex, length) {
  // temp保存父节点值，用于最后的赋值
  let temp = array[parentIndex];
  let childIndex = 2 * parentIndex + 1;
  while (childIndex < length) {
    // 如果有右孩子，并且右孩子大于左孩子的值，则定位到右孩子
    if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
      childIndex++;
    }
    // 如果父节点大于任何一个孩子的值，则跳出循环
    if (temp >= array[childIndex]) {
      break;
    }
    // 单向赋值
    array[parentIndex] = array[childIndex]
    parentIndex = childIndex
    childIndex = 2 * childIndex + 1
  }
  array[parentIndex] = temp
}

function output(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i])
  }
}

/**
 * 堆排序
 * @param {*} array 待调整的堆
 */
function heapSort(array) {
  // 1.把无序数组构建成最大堆
  for (let i = (array.length - 2)/2; i >= 0; i--) {
    downAjust(array, i, array.length)
  }
  output(array)
  // 2.循环删除堆顶元素，移到集合尾部，调整堆产生新的堆
  for (let i = array.length; i > 0; i--) {
    // 最后一个元素和第一个元素交换
    let temp = array[i];
    array[i] = array[0];
    array[0] = temp;
    // 下沉调整最大堆
    downAjust(array, 0, i)
  }
}

const array = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0];

heapSort(array);

output(array) // 0 1 2 3 5 6 7 8 9 10

计数排序

计数排序的工作原理如下，

1.得到数列的最大值

2.根据数列最大值确定统计数组的长度

3.遍历数组填充统计数组

4.遍历统计数组，输出结果

function countSort(array) {
  // 1.得到数列的最大值
  let max = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i]
    }
  }
  // 2.根据数列最大值确定统计数组的长度
  let countArray = new Array(max + 1);
  countArray.fill(0);
  // 3.遍历数组填充统计数组
  for (let i = 0; i < array.length; i++) {
    countArray[array[i]]++;
  }
  // 4.遍历统计数组，输出结果
  let index = 0;
  let sortedArray = new Array(array.length);
  for (let i = 0; i < countArray.length; i++) {
    for (let j = 0; j < countArray[i]; j++) {
      sortedArray[index++] = i
    }
  }
  return sortedArray;
}

function output(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i])
  }
}

const array = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10];
const sortArray = countSort(array);

output(sortArray)

局限性：

1.当数列最大值和最小值差距过大时，不适合计数排序。会造成空间的浪费，随之时间复杂度也会上升。

2.当数列元素不是整数时，也不适合。小数无法创建对应的统计数组。

桶排序

桶排序同样是一种线性时间的排序算法。它类似于计数排序所创建的计数组，需要创建若干个桶来协助排序。每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。

工作原理如下，

1.创建桶，并确定每一个桶的区间范围

创建桶的数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。

区间跨度 = （最大值 - 最小值）/ （桶的数量 - 1）

2.遍历原始数列，把元素对号入座放入各个桶中。

3.对每个桶内部的元素分别进行排序。

4.遍历所有的桶，输出所有元素。

function bucketSort(array) {
  // 得到数列的最大值和最小值，并计算出差值d
  let max = array[0];
  let min = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i]
    }
    if (array[i] < min) {
      min = array[i]
    }
  }
  let d = max - min; // 差值

  // 2.初始化桶
  let bucketNum = array.length; // 桶的个数
  let range = d / (bucketNum - 1); // 区间
  let listArray = []; // 按编号存放
  
  // 3.遍历原始数列，将每个元素放入桶中
  for (let i = 0; i < array.length; i++) {
    // 计算桶的编号
    let index = Math.floor((array[i] - min) / range);
    // 4.对每个桶内部进行排序   判断桶里面是否已经有值了，有值则进行排序
    if (listArray[index]) { 
      // 获取桶的最后一个值的下标
      let last = listArray[index].length - 1;
      // 桶最后的值要大于插入的值，所以将这个值插入到桶的前面，此时需要进行排序
      while (last >= 0 && listArray[index][last] > array[i]) {
        // 桶前面的数字放到后面去
        listArray[index][last + 1] = listArray[index][last]
        last--;
      }
      // 不用排序的直接加到桶的后面
      listArray[index][last + 1] = array[i];
    } else {
      listArray[index] = [];
      listArray[index][0] = array[i]
    }
  }

  // 5.输出全部元素
  let num = 0;
  let sortedArray = [];
  while (num < bucketNum) {
    if (listArray[num]) {
      sortedArray = sortedArray.concat(listArray[num])
    }
    num++;
  }
  return sortedArray;

}

function output(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i])
  }
}

const array = [4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09];
const sortArray = bucketSort(array);

output(sortArray) // 0.0023 2.123 3.0 4.12 4.12 6.421 8.122 10.09