选择排序(Selection sort)是排序算法的一种,它是蛮力思想的一个体现。
选择排序开始的时候,我们扫描整个序列,找到它的最小元素,然后和第一个元素交换,将最小元素放到它在有序表中的最终位置上。然后我们从第二个元素开始扫描列表,找到最后 n−1 个元素中的最小者,再和第二个元素交换位置,把第二小的元素放在它的最终位置上。一般来说,在对该列表做第 i 遍扫描的时候(ii 的值从 0 到 n−2),该算法在最后 n−i 个元素中寻找最小元素,然后拿它和 Ai 交换。在 n−1 遍以后,该列表就被排好序了。
排序有内部排序和外部排序。内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
本文简要介绍流行的排序算法,以及它们的复杂度。
希尔排序(Shell sort)的名称源于它的发明者 Donald Shell,它通过比较相距一定间隔的元素来工作。各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。由于这个原因,希尔排序有时也叫做缩小增量排序(diminishing inc sort)。
基数排序(radix sort)是一种用在卡片排序机上的算法,因此有时也称为卡式排序(card sort)。基数排序分为 LSD(Least significant digital)和 MSD(Most significant digital)。LSD 从低位开始排到高位,每排一位都是把各个桶合并,再按下一位排序;MSD 从高位开始排到低位,排完一位后不合并桶,相同的高位划分子桶继续分配,最后再合并。
冒泡排序 (Bubble sort) 是排序算法的一种,它是蛮力思想的一个体现。
它重复地走访要排序的数列,一次比较相邻的两个元素,如果它们的顺序不符合要求就交换它们的位置。nn 个数需要 n−1n−1 趟排序,每一趟排序使得最大数冒出(升序)或最小数冒出(降序)。