排序


冒泡排序

通过比较两个相邻元素大小,不断交换位置,最后使得整序列有序。效率较低,但可以优化。

插入排序

每个元素从前向后扫,到自己截止,若有元素比自己大,则插到其前面。

希尔排序

假设有一组{$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$

若还有更高数位,依次排序即可。


文章作者: 王大神——A001
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 王大神——A001 !
  目录