冒泡排序
通过比较两个相邻元素大小,不断交换位置,最后使得整序列有序。效率较低,但可以优化。
插入排序
每个元素从前向后扫,到自己截止,若有元素比自己大,则插到其前面。
希尔排序
假设有一组{$9, 1, 2, 5, 7, 4, 8, 6, 3, 5$}无序序列。
第一趟排序:
$\frac{10}{2}=5$,即相隔距离为 $5$ 的元素组成一组,可以分为 $5$ 组。接下来,按照直接插入排序的方法对每个组进行排序。
第二趟排序:
将上次的长度缩小一半,即 $\frac{5}{2}$ (取整数)。这样每相隔距离为 $2$ 的元素组成一组,可以分为 $2$ 组。按照直接插入排序的方法对每个组进行排序。
第三趟排序:
再缩小一半,即 $\frac{2}{2}=1$。 这样相隔距离为 $1$ 的元素组成一组,即只有一组。按照直接插入排序的方法对每个组进行排序。
此时,排序已经结束。
选择排序
每回选择最小的数换到当前位置。
快速排序
从元素之中挑一个基准,所有比他小的排到左边,比他大的排到右边。
归并排序
将整个序列拆成子序列,子序列排成有序后,合并子序列时,再将两个子序列排序,排序时有技巧。
例子:
子序列 $1$:$1,3,4$
子序列 $2$:$2,7,8$
第一步:比较第一位($1,2$)比较
合并序列:$1$
第二步:大的数比较小的数的后一位($2,3$)比较
合并序列:$1,2$
第三步:重复第二步,比较($3,7$)
合并序列:$1,2,3$
第四步:重复第二步,比较($4,7$)
合并序列:$1,2,3,4$
最后,一个序列已经比较完了,另一个序列剩下的直接补到序列尾。
合并序列:$1,2,3,4,7,8$
堆排序
本质是一颗二叉树。
先将所有的数建一棵二叉树。
每次将比对父节点和儿子的值,值大的向上传。
此时根节点至最大。
最大值入数组,与树的子节点交换后删除此节点。
不断出最大值,最后数组倒序。
计数排序
将所有的数直接存入相应的下标,最后按下标从小到大输出。
存入时要计数,输出时,输出下标是记得数的个数。
桶排序
先将最大值除去数组长度 $-1$ 后,将所有的数值同样除去数组长度 $-1$ 后,按计数排序存入数组。
每一个数组的下标用链表存储数据,数据存入时,按链表顺序与值比对大小,使之有序。
基数排序
将数字按位排序,例子:
$12,43,23,45,61,29,57,49,92$
第一步:将个位排序
$61,12,92,43,23,45,57,29,49$
第二步:将十位排序
$12,23,29,43,45,49,57,61,92$
若还有更高数位,依次排序即可。