十大经典排序算法

超链接

https://github.com/hustcc/JS-Sorting-Algorithm

https://sort.hust.cc/

来源网络：

1. 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序

4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于时间复杂度

排序后两个相等键值的顺序和排序之前它们的顺序相同

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

关于稳定性

n：数据规模

k：“桶”的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

名词解释：

Introduction 介绍

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

1. 算法步骤

2. 动图演示

Python

JavaScript

Go

Java

PHP

3. 代码实现

稳定

稳定性

3. insertionSort 插入排序

插入排序的一种

2. 按增量序列个数 k，对序列进行 k 趟排序；

3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

不稳定

4. shellSort 希尔排序

插入排序

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3. 重复第二步，直到所有元素均排序完毕。

2. selectionSort 选择排序

1. 从数列中挑出一个元素，称为 “基准”（pivot）;

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

C++

6. quickSort 快速排序

选择排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

3. 什么时候最快

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

4. 什么时候最慢

5. 代码实现

1. bubbleSort 冒泡排序

1. 将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；

2. 把堆首（最大值）和堆尾互换；

3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

4. 重复步骤 2，直到堆的尺寸为 1。

7. heapSort 堆排序

交换排序

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

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

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

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

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

5. mergeSort 归并排序

分治递归

1. 动图演示

2. 代码实现

8. countingSort 计数排序

当输入的数据可以均匀的分配到每一个桶中。

1. 什么时候最快

当输入的数据被分配到了同一个桶中。

2. 什么时候最慢

9. bucketSort 桶排序

基数排序有两种方法：这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异案例看大家发的： - 基数排序：根据键值的每位数字来分配桶；
 - 计数排序：每个桶只存储单一键值；
 - 桶排序：每个桶存储一定范围的数值；

1. 基数排序 vs 计数排序 vs 桶排序

2. LSD 基数排序动图演示

10. radixSort 基数排序

'桶' 排序

十大经典排序算法