冒泡排序、选择排序、直接插入排序、二分法排序、希尔排序、快速排序、堆排序、归并排序、基数排序,共9中排序算法详解和代码示例。
示例中全部采用从小到大排序,编码方式为本人理解的思路,算法思想也是自己理解的口语表达方式,若想查看更准确的算法思想和代码示例可直接搜索各算法的百科
一、冒泡排序
1、算法思想
- 两两比较,如果后者比前者大则交换位置
- 每遍历一圈最大的数就会冒到最后,则确定了本轮比较中的最大值放到最后不动
- 循环1、2直至遍历完所有
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(n²)
二、选择排序
1、算法思想
- 找到所有数中最大值下标
- 找到最大值的下标与最后一个位置的数值交换位置,这样每次找到的最大值则固定到最后
- 循环1、2操作直至遍历找到所有
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(n²),但是由于选择排序每轮比较只交换一次,所以实际性能要优于冒泡
三、直接插入排序
1、算法思想
- 从位置1的数值n开始,将前面已经遍历过的数值集合看成数组m,则将n往m中插入
- n插入到集合m中时从后往前比较,如果比n大则往后移一位,如果比较到比n小,则当前位置就是插入n的位置
- 通过1、2的操作则可以保证每次插入n后m的集合都是排好的序列
- 循环1、2、3操作将集合中所有数值均插入一遍即排序完成
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(n²)
四、二分法排序
- 二分法排序是直接插入排序的改进版本,直接插入排序插入到前方集合中时采用的方式是逐个比较,二分法则是采用二分比较
1、算法思想
- 从位置1的数值为n,将前面已经遍历过的数值集合看成数组m,则将n往m中插入
- n插入到集合m中时采用二分法,先比较m中中间的数值,如果比n大则继续比较后面一半集合的中间的数值,直至比较到拆分的集合中左边一半或者右边一半没有值为止,则当前中间值的位置即为n插入到m中的位置
- 通过1、2的操作则可以保证每次插入n后m的集合都是排好的序列
- 循环1、2、3操作将集合中所有数值均插入一遍即排序完成
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(nlogn)
五、希尔排序
1、算法思想
- 定义一个增量m,集合的长度为n,则将集合拆分成n/m组,每组内部进行比较排序
- 每组内比较的方法无要求,可以用插入或者二分法都行
- 假如要排序一段集合为{4,1,2,3},定义m为2,则拆分成两组两两比较,即为4和2比,1和3比
- 因此按照1、2的思路每比较一次都可以将m组内的数值排序
- 不断变化m的值,多次分组遍历之后即可排序
2、代码示例
- m的变化方式有多种,不同的变化方式可能排序结果和效率不同。此处示例采用的方式是m=m/2
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(nlogn)
六、快速排序
1、算法思想
- 快速排序的思想主要是先设置一个基准点m,这里我们假设每次设置的基准点都是每一组的第一个数值
- 拿着基准点m在集合中进行比较,找到它应该放置的位置
- 比较方式主要是定义集合中最左边的下标left,最右边的下标right,从左边开始比较,比m小则left++,找到比m大的则停住,将left下标的值赋值成right下标的值,然后同理比较right,比m大的则right–,找到比m小的就赋值成left下标的值。当left==right之后则比较完成
- 经过步骤3的比较之后则可以找到m点排序所在的位置,然后集合被分成前后两半,各自按照1、2、3的方式排序,递归至全部拆分比较完成后即排序完成
- 由于步骤3思想较复杂一点,特此引用《啊哈!算法》一书中的插图演示一下,图中以第一个点6为基准点,找到6排序后应该所在的位置
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(nlogn)
七、堆排序
1、算法思想
- 将数组构建成大堆二叉树,即所有节点的父节点的值都大于叶子节点的完全二叉树
- 若叶子节点比父节点大,则交换位置
- 根节点即为最大值,则将根节点与最后的的一个叶子节点交换位置
- 重复1,2操作,每次都找最大值则放置最后即可排序完成
- 由于堆排序运用到了完全二叉树的数据结构,较难理解,特地在网上找了个算法演示的图片参考
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(nlogn)
八、归并排序
1、算法思想
- 将数据集合两分拆开
- 循环拆分至每组只剩一个为止
- 将拆分的数组进行排序组合
- 两两合并,直至合并成一个数组即排序完成
- 算法思想参考下图
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 时间复杂度O(nlogn)
九、基数排序
1、算法思想
- 基数排序又称桶排序,具体思想就是将数值当成数组的下标保存
- 将所有数值拿出个位来比较,例如值为m的就存入下标为m的数组中
- 将比较后的数组拿出即为按个位排序好的数组,再将这个排序好的数组按十位排序
- 比较完个十百千所有位数以后即排序完成
- 步骤一思想参考图
2、代码示例
1 | private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36}; |
- 基数排序的时间复杂度为O(d(n+r)),r为基数,d为位数