「干货」编程语言十大经典算法，你知道几个？

预备知识：算法稳定性

一、冒泡排序

• 从头开始，比较相邻的两个数，如果第一个数比第二个数大，那么就交换它们位置。
• 从开始到最后一对比较完成，一轮结束后，最后一个元素的位置已经确定。
• 除了最后一个元素以外，前面的所有未排好序的元素重复前面两个步骤。
• 重复前面 1 ～ 3 步骤，直到都已经排好序。
  

二、选择排序

• 从第一个元素开始，遍历其后面的元素，找出其后面比它更小的元素，若有，则两者交换，保证第一个元素最小。
• 对第二个元素一样，遍历其后面的元素，找出其后面比它更小的元素，若存在，则两者交换，保证第二个元素在未排序的数中（除了第一个元素）最小。
• 依次类推，直到最后一个元素，那么数组就已经排好序了。
  

三、插入排序

• 从第一个元素开始，可以认为第一个元素已经排好顺序。
• 取出后面一个元素 n，在前面已经排好顺序的数组里从尾部往头部遍历，假设取出来的元素为 nums，如果 num>n，那么将 nums 移动到后面一个位置，直到找到已经排序的元素小于或者等于新元素的位置，将 n 放到新空出来的位置上。如果没有找到，那么 nums 就是最小的元素，放在第一个位置。
• 重复上面的步骤 2，直到所有元素都插入到正确的位置。
  

四、希尔排序

• 选择一个增量 gap，一般开始是数组的一半，将数组元素按照间隔为 gap 分为若干个小组。
• 对每一个小组进行插入排序。
• 将 gap 缩小为一半，重新分组，重复步骤 2（直到 gap 为 1 的时候基本有序，稍微调整一下即可）。
  

五、快速排序

• 从数组中挑一个元素作为基准数，一半情况下我们选择第一个 nums，保存为 standardNum，可以理解为 nums 坑位的数被拎出来了，留下空的坑位。
• 取数组的左边界索引为 i，右边界索引 j，j 从右边往左边，寻找到比 standardNum 小的数，停下来，写到 nums 的坑位，nums[j] 的坑位空出来。 i 从左边往右边找，寻找比 standardNum 大的数，停下来，写到 nums[j] 的坑位，这个时候，num 的坑位空出来（前提是 i 和 j 不相撞）。
• 上面的 i 和 j 循环步骤 2，直到 i 和 j 相撞，将基准值 standardNum 写到坑位 nums 中，这时候，standardNum 左边的数都小于等于它本身，右边的数都大于等于它本身。
• 分别对 standardNum 左边的子数组和右边的子数组，循环执行前面的 1，2，3，直到不可再分，并且有序。
  

六、归并排序

• 将长度为 n 的数组分割成为 n/2 的两个子数组。
• 子数组也不断分割成为更小的子数组，直到不能分割。
• 最小子数组之间开始两两合并，合并之后的结果再合并。合并的时候可以申请一个临时空间，利用两个索引指针比较的方式，将两个子数组的结果合并到临时数组中去。
• 循环 3 步骤，直到合并成为长度为 n 的已经排序的数组。
  

七、计数排序

• 遍历数组，找出最大值和最小值。
• 根据最大值和最小值，初始化对应的统计元素数量的数组。
• 遍历元素，统计元素个数到新的数组。
• 遍历统计的数组，按照顺序输出排序的数组元素。
  

八、桶排序

• 遍历数组，查找数组的最大最小值，设置桶的区间（非必需），初始化一定数量的桶，每个桶对应一定的数值区间。
• 遍历数组，将每一个数，放到对应的桶中。
• 对每一个非空的桶进行分别排序（桶内部的排序可以选择 JDK 自带排序）。
• 将桶中的子数组拼接成为最终的排序数组。
  

九、堆排序

• 大顶堆：每个节点的数值都大于或者等于其左右孩子节点的数值。
• 小顶堆：每个节点的数值都小于或者等于其左右孩子节点的数值。
  

• 将无序的数组构建出一个大顶堆，也就是上面的元素比下面的元素大。
• 将堆顶的元素和堆的最末尾的元素交换，将最大元素下沉到数组的最后面（末端）。
• 重新调整前面的顺序，继续交换堆顶的元素和当前末尾的元素，直到所有元素全部下沉。
  

十、基数排序

• 将所有元素统一称为统一数位长度，前面补 0。
• 从最高位开始，依次排序，从最高位到最低位遍历完，数组就是有序的。
  

• 冒泡排序：基本最慢，时间复杂度最好为 O(n)，最坏为 O(n2)，平均时间复杂度为 O(n2)，空间复杂度为 O(1)，稳定排序算法。
• 选择排序：时间复杂度很稳定，最好最坏或者平均都是 O(n2)，空间复杂度为 O(1)，可以做到稳定排序。
• 插入排序：时间复杂度最好为 O(n)，最坏为 O(n2)，平均时间复杂度为 O(n2)，空间复杂度为 O(1)，稳定排序算法。
• 希尔排序：希尔增量下最坏的情况时间复杂度是 O(n2)，最好的时间复杂度是 O(n) （也就是数组已经有序），平均时间复杂度是 O(n3/2)，属于不稳定排序。
• 快速排序：时间复杂度最差的情况是 O(n2)，平均时间复杂度为 O(nlogn)，空间复杂度，虽然快排本身没有申请额外的空间，但是递归需要使用栈空间，递归数的深度是 log2n，空间复杂度也就是 O( log2n)，属于不稳定排序。
• 归并排序：排序复杂度为 nlog2n，不存在好坏的情况，但是代价就是需要申请额外的空间，申请空间的大小最大为 n，所以空间复杂度为 O(n)，属于稳定排序。
• 计数排序：时间复杂度为 O(n+k)，申请了一个统计数组和一个新数组，空间复杂度为 O(n+k)，没有所谓最好最坏，都是一个复杂度，一般适用于小范围整数排序，属于稳定排序。
• 桶排序：最好情况时间复杂度 O(n)，最坏情况时间复杂度为 O(n2)，平均的时间复杂度为 O(n+k)。由于在中间过程中会申请桶的数量 m，所以空间复杂度为 O(n+m)，稳定性决定于桶内部排序。
• 堆排序：时间复杂度为 O(nlogn)，没有申请额外的空间，空间复杂度为 O(1)，属于不稳定排序。
• 基数排序：时间复杂度为 O(d(2n))。一般只使用于整数排序，不适合小数或者文字排序。由于需要申请桶的空间，假设有 k 个桶(上面是 10 个桶)，则空间复杂度为 O(n+k)，一般 k 较小，所以近似为 O(n)，属于稳定排序。