@[toc]

已经有很多排序算法的文章了,这里主要是做一个自己的总结。 内容大部分整合自《算法第四版》,图示大部分来自菜鸟教程网。语言选择的当然是JavaScript啦~ 代码可以直接在LeetCode的912.排序数组 (opens new window)题目上运行

在此之前先定义一个交换数组中两个元素的函数

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

# 1. 冒泡排序 (简单)

# 流程

  • 比较相邻的元素。如果前者大于后者就交换
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数
  • 针对所有的元素重复以上的步骤,除了最后一个
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

# 图示

在这里插入图片描述

# 代码

参考代码1

/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
      }
    }
  }
  return nums;
};

参考代码2 优化冒泡排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let flag = true;
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
		swap(nums, j, j + 1);
        flag = false;
      }
    }
    if(flag) {
      return;
    }
  }
  return nums;
};

# 复杂度分析

时间复杂度:$O(N^2)$,这里 $N$是数组的长度; 空间复杂度:$O(1)$,使用到常数个临时变量。

# 2. 选择排序(简单)

一种最简单的排序算法:首先找到数组中最小的元素,将它和数组中的第一个元素交换位置,然后在剩下的元素中找到最小的,与第二个元素交换位置,直到整个数组排序。(不断选择剩余数组中最小的元素)

# 流程

  1. 首先在未排序序列中找到最小元素,存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾
  3. 重复第二步,直到所有元素均排序完毕

# 图示

在这里插入图片描述

# 代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let min = i;
    // 已排序区间 [0, i) ,未排序区间 [i+1 , len)
    // 遍历 i+1 之后的元素找到最小元素的索引
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[min]) {
        min = j;
      }
    }
    swap(nums, i, min);
  }
  return nums;
};

# 复杂度分析

  • 对于长度为N的数组,选择排序需要大约$N^2/2$次比较和$N$次交换。
  • 有两个特点:①运行时间和输入无关 ②数据移动是最少的,交换次数和数组的大小是线性关系

时间复杂度:$O(N^2)$,这里 $N$ 是数组的长度; 空间复杂度:$O(1)$,使用到常数个临时变量。

# 3. 插入排序(重点)

# 流程

每次将一个数字插入一个有序的数组里,成为一个长度更长的有序数组,有限次操作以后,数组整体有序

# 图示

在这里插入图片描述

# 代码

参考代码1(交换元素)(算法第四版的思路)

/**
 * 插入排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
  // 已排序区间 [0, i) ,未排序区间 [i , len)

  // 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
  for (let i = 1; i < nums.length; i++) {
    // 从右往左遍历
    for (let j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
      // 只要nums[j]比前一个元素nums[j-1]小,就交换这两个元素
      swap(nums, j, j - 1);
    }
  }
  return nums;
};

参考代码2(移动元素)

/**
 * 插入排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    // 已排序区间 [0, i) ,未排序区间 [i , len)
    // 将 nums[i] 插入到区间 [0, i) 使之成为有序数组

    // 先暂存这个元素,然后之前元素逐个后移,留出空位
    let temp = nums[i];
	let j = i;
    while(j > 0 && temp < nums[j - 1]) {
      // 只要nums[j]比前一个元素nums[j-1]小,将nums[j-1]移动到nums[j]
      nums[j] = nums[j - 1];
      j--;
    }
    
    // 找到位置j,将i的值放在j上
    nums[j] = temp;
  }
  return nums;
};

# 复杂度分析

插入排序对部分有序的数组和“短数组”很有效

时间复杂度:$O(N^2)$,这里 $N$ 是数组的长度; 空间复杂度:$O(1)$,使用到常数个临时变量。

# 4. 希尔排序(了解)

对插入排序的改进!插入排序效率低的原因是它只会交换相邻的元素 希尔排序的思想是使数组中任意间隔为h的元素都是有序的,即带间隔地使用插入排序

# 流程

设置增量序列是一个超参数,需要经验。下面的代码给出了两种定义方式

# 图示

在这里插入图片描述

# 代码

设置增量序列是一个超参数,需要经验。下面的代码给出了两种定义方式

参考代码1(交换元素)

var shellSortArray = function (nums) {
  const N = nums.length;
  // 使用 Knuth 增量序列
  let h = 1;
  while (h < N / 3) {
    h = 3 * h + 1; // 动态定义间隔序列
  }

  while (h >= 1) {
    for (let i = h; i < N; i++) {
      for (let j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
        swap(nums, j, j - h);
      }
    }
    h = Math.floor(h / 3)
  }
};

参考代码2(移动元素)

var shellSortArray2 = function (nums) {
  const N = nums.length;
  for (let gap = N / 2; gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < N; i++) {
      let temp = nums[i];
      let j = i;
      while(j >= gap && nums[j - gap] > temp){
        nums[j] = nums[j - gap];
        j -= gap;
      }
      nums[j] = temp;
    }
  }
  return nums;
};

# 复杂度分析

在输入随机排序数组的情况下,我们在数学上还不知道希尔排序所需要的平均比较次数

# 5. 归并排序(重点)

将两个有序的数组归并成一个更大的有序数组

# 流程

分治算法、递归调用

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  4. 重复步骤 3 直到某一指针达到序列尾;

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

# 图示

在这里插入图片描述 在这里插入图片描述

# 代码

使用JavaScript中数组的队列方法,使得归并排序实现起来异常简单,不用涉及过多的指针问题

/**
 * 归并排序算法
 * @param {*} arr 数组
 * @returns 有序数组
 */
function mergeSort(arr) {
  // 采用自顶向下的递归方法
  const N = arr.length;
  if (N < 2) {
    // 递归出口,数组只有一个元素,直接返回这个数组
    return arr;
  }
  // x >> 1 是位运算中的右移运算,表示右移一位,等同于 x 除以 2 再取整,即 x >> 1 === Math.floor(x / 2)
  // N >> 1 和 Math.floor(N / 2) 等价
  let middle = N >> 1;
  // 拆分为两个子数组
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  // 递归调用mergeSort
  return merge(mergeSort(left), mergeSort(right));
}


/**
 * 对两个有序数组进行合并操作
 * @param {*} left left数组
 * @param {*} right right数组
 * @returns 一个有序数组temp
 */
function merge(left, right) {
  // 临时数组存储归并后的数据
  const temp = [];
  // 两个数组都还没有遍历结束
  while (left.length && right.length) {
    // 注意: 判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
    if (left[0] <= right[0]) {
      // left[0]小,删除left数组中第一项left[0],并将它放入temp数组中
      temp.push(left.shift());
    } else {
      // 删除right数组中第一项,并将它放入temp数组中
      temp.push(right.shift());
    }
  }
  // left数组还有元素,right数组遍历完了
  while (left.length) {
    // 将left数组剩下的元素都放入temp数组中
    temp.push(left.shift());
  }
  // right数组还有元素,left数组遍历完了
  while (right.length) {
    temp.push(right.shift());
  }
  // 返回排序好的数组
  return temp;
}

我们不使用JavaScript中Array自带的一些方法,使用指针的方式按照《算法(第四版)》重写一遍

/**
 * 排序数组
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const N = nums.length;
  let temp = new Array();
  mergeSort(nums, 0, N - 1, temp);
  return nums;
};

/**
 * 归并排序  采用自顶向下的递归方法
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @param {number[]} temp
 * @returns
 */
var mergeSort = function (nums, left, right, temp) {
  // 如果指针重叠了就返回
  if (left >= right) {
    return;
  }

  // let mid = Math.floor(left + (right - left) / 2);
  let mid = (left + right) >> 1;
  // 递归调用mergeSort
  mergeSort(nums, left, mid, temp);
  mergeSort(nums, mid + 1, right, temp);
  // 归并两个有序数组
  merge(nums, left, mid, right, temp);
};

/**
 * 归并两个有序数组
 * @param {number[]} nums
 * @param {number} left
 * @param {number} mid
 * @param {number} right
 * @param {number[]} temp
 */
var merge = function (nums, left, mid, right, temp) {
  // 将nums复制到temp中去
  for (let k = left; k <= right; k++) {
    temp[k] = nums[k];
  }

  // 给两个数组分别定义一个指针
  let i = left;
  let j = mid + 1;

  // 将temp中的元素按规则写回nums
  for (let k = left; k <= right; k++) {
    if (i > mid) {
      // 左半边取尽,取右半边元素
      nums[k] = temp[j];
      j++;
    } else if (j > right) {
      // 右半边取尽,取左半边元素,左指针右移
      nums[k] = temp[i];
      i++;
    } else if (temp[i] <= temp[j]) {
      // 谁小就取谁 ,左边小
      nums[k] = temp[i];
      i++;
    } else {
      // 右边小
      nums[k] = temp[j];
      j++;
    }
  }
};

# 复杂度分析

时间复杂度:$O(N \log N)$,这里 $N$ 是数组的长度; 空间复杂度:$O(N)$,辅助数组与输入数组规模相当。

# 优化

设置短数组长度阈值,使归并到短数组的时候用插入排序法

上面介绍的是一种自顶向下的递归方法,另外还有自底向上的递归方法,在这里就不做过多介绍,具体可以参考算法第四版的内容

# 6. 快速排序(重点)

# 流程

  1. 从数组中选择一个值作为主元(pivot),也就是数组中间的那个值。
  2. 创建两个指针(引用),左边一个指向数组第一个值,右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值,接着,移动右指针直到找到一个比主元小的值,然后交换它们,重复这个过程,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。这一步叫作划分(partition)操作。
  3. 算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组)重复之前的两个步骤,直至数组已完全排序。

# 图示

在这里插入图片描述

# 代码

双指针法

/** 
 * @param {number[]} nums
 * @return {number[]}
 */

var sortArray = function (nums) {
  const N = nums.length;
  quickSort(nums, 0, N - 1);
  return nums;
};

function quickSort(nums, left, right) {
  if (right <= left) {
    return;
  }
  let pIndex = partition(nums, left, right);
  quickSort(nums, left, pIndex - 1);
  quickSort(nums, pIndex + 1, right);
}

function partition(nums, left, right) {

  let pivot = nums[left];
  // 为两个数组分别定义一个指针
  let i = left + 1;
  let j = right;

  while (true) {
    while (i <= right && nums[i] <= pivot) {
      i++;
    }
    while (j > left && nums[j] > pivot) {
      j--;
    }
    if (i >= j) {
      break;
    }
    swap(nums, i, j);
    i++;
    j--;
  }
  swap(nums, left, j);
  return j;
}

# 复杂度分析

时间复杂度:$O(N \log N)$,这里 $N$ 是数组的长度; 空间复杂度:$O(\log N)$,这里占用的空间主要来自递归函数的栈空间。

# 7. 堆排序(重点)

# 概念

先来看看什么是堆

当一棵二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序。 根结点是堆有序的二叉树中的最大结点 一棵大小为N的完全二叉树的高度为[lgN]

大顶堆:逻辑上是完全二叉树,对于树中任意节点,其关键字的值都不小于其孩子节点的关键字的值。

在堆上的一些操作

父节点位置为i,其左孩子节点位置为2i+1,右孩子节点位置为2i+2 最后一个非叶节点编号为 [n/2] - 1 (向下取整) 在一个堆中,位置k的结点的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1 从a[k]向上一层就令k等于k/2,向下一层则令k等于2k或2k+1

书上看的一个比较有意思的描述

我们把堆想象成一个严密的黑社会组织,每个子结点都表示一个下属(父结点则表示它的直接上级),那么这些操作就可以得到很有趣的解释。swim()【上浮】表示一个很有能力的新人加入组织并被逐级提升(将能力不够的上级踩在脚下),直到他遇到了一个更强的领导。sink()【下沉】则类似于整个社团的领导退休并被外来者取代之后,如果他的下属比他更厉害,他们的角色就会交换,这种交换会持续下去直到他的能力比其下属都强为止。

function swim(k){
  while(k > 1 && nums[Math.floor(k/2)] < nums[k]){
    swap(nums, Math.floor(k/2), k);
    k = Math.floor(k/2);
  }
}
function sink(k){
  while(2*k <= N) {
    let j = 2 * k;
    if(j < N && nums[j] < nums[j+1]){
      j++;
    }
    if(nums[k] >= nums[j]){
      break;
    }
    swap(nums, k, j);
    k = j;
  }
}

# 1. 建堆

  1. 找出完全二叉树中最后一个非叶节点 [n/2] - 1
  2. 比较这个节点和其孩子节点的大小,如果小于孩子的最大值,就交换他们的值,交换后继续比较其与当前孩子的值的情况,进行同样的处理
  3. 指针不断上移(减一)循环步骤2

# 2. 插入节点

  1. 将要插入的节点放入所有节点的最后面
  2. 找到这个节点到根节点的一条路径,如果比父节点大,就交换,直到不大于父节点的大小

# 3. 删除节点

  1. 将要删除的节点拿出来
  2. 用堆中最后一个节点替换到待删除的节点的位置
  3. 对交换后的节点进行和【建堆步骤2】类似的调整

# 流程

堆排序可以分为两个阶段。在堆的构造阶段中,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按递减顺序取出所有元素并得到排序结果。

  1. 将初始待排序关键字序列 $(R_1, R_2 .... R_n)$ 构建成大顶堆,此堆为初始的无序区;[堆的有序化(reheapifying)]
  2. 将堆顶元素 R[1] 与最后一个元素 R[n] 交换,此时得到新的无序区$(R_1, R_2 .... R_{n-1})$和新的有序区 $(R_n)$ ,且满足 $R[1, 2 ... n-1] <= R[n]$。
  3. 由于交换后新的堆顶 R[1] 可能违反堆的性质,因此需要对当前无序区 $(R_1, R_2 .... R_{n-1})$调整为新堆,然后再次将 R[1] 与无序区最后一个元素交换,得到新的无序区 $(R_1, R_2 .... R_{n-2})$和新的有序区$(R_{n-1}, R_n)$。不断重复此过程,直到有序区的元素个数为 $n - 1$,则整个排序过程完成。

# 图示

在这里插入图片描述 在这里插入图片描述

# 代码

/**
 * 堆排序
 * @param {*} nums
 * @returns
 */
function sortArray(nums) {
  const N = nums.length;
  // 建堆 找到第一个非叶子节点,向上遍历
  for (let i = Math.floor(N / 2 - 1); i >= 0; i--) {
    // 对 i位置节点 调整堆
    heapify(nums, i, N);
  }
  // 排序过程 每一次循环都找出当前最大值(根节点),数组长度减一
  for (let i = N - 1; i > 0; i--) {
    // 根节点与最后一个节点交换位置(将此时最大元素移动到数组末尾)
    swap(nums, 0, i);
    // 对 此时的根节点 调整堆 最后的元素不用参与调整
    heapify(nums, 0, i);
  }
  return nums;
}

/**
 * 对节点i进行 调整堆
 * 满足:i节点以下的子堆是一个大顶堆
 * 调整范围 [i, length)
 * @param {*} nums
 * @param {*} i
 * @param {*} length
 */
function heapify(nums, i, length) {
  // 将i节点的值保存,这个过程就是给temp找到一个合适的位置
  let temp = nums[i]
  // j指向i的左孩子节点
  let j = 2 * i + 1;
  // 循环遍历[i, length)
  while (j < length) {
    if (j + 1 < length && nums[j] < nums[j + 1]) {
      // 父节点有右孩子 并且 左孩子小于右孩子 将j指向右孩子
      j++;
    }
    // 此时 j 指向 i 的孩子节点中较大的那个节点
    if (temp < nums[j]) {
      // 如果 父节点小于 j节点
      // 交换i,j的元素
      swap(nums, i, j);
      // 将i和j都下移一位
      i = j;
      j = 2 * i + 1; 
    } else {
      // 父节点 大于 孩子节点中最大的元素,就退出循环
      break;
    }
  }
}

# 复杂度分析

堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是 $O(N)$,排序过程的时间复杂度是 $O(N \log N)$,所以,堆排序整体的时间复杂度是 $O(N \log N)$。

# 8. 计数排序(了解)

# 流程

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

# 图示

在这里插入图片描述

# 代码

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

# 9. 基数排序(了解)

# 图示

在这里插入图片描述

# 代码

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

# 10. 桶排序(了解)

# 代码

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

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

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

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

    return arr;
}
  • 基数排序:根据键值的每位数字来分配桶;
  • 计数排序:每个桶只存储单一键值;
  • 桶排序:每个桶存储一定范围的数值;

# 11. 总结

在这里插入图片描述 在这里插入图片描述

上次更新: 2022/4/3 18:00:41