内部排序

在信息处理过程中，最基本的操作是查找。从查找来说，效率最高的是折半查找，折半查找的前提是所有的数据元素(记录)是按关键字有序的。需要将一个无序的数据文件转变为一个有序的数据文件。

将任一文件中的记录通过某种方法整理成为按(记录)关键字有序排列的处理过程称为排序。

排序是数据处理中一种最常用的操作。

1. 排序的基本概念

1.1 排序(Sorting)

排序是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程，其定义为：给定一组记录序列：，其相应的关键字序列是 。确定1, 2, … n的一个排列p1 , p2 ,…, pn，使其相应的关键字满足如下非递减(或非递增)关系： Kp1≤Kp2 ≤…≤Kpn的序列 ，这种操作称为排序。

关键字Ki可以是记录Ri的主关键字，也可以是次关键字或若干数据项的组合。

◆ Ki是主关键字：排序后得到的结果是唯一的；

◆ Ki是次关键字：排序后得到的结果是不唯一的。

1.2 排序的稳定性

若记录序列中有两个或两个以上关键字相等的记录： Ki =Kj(i≠j，i, j=1, 2, … n)，且在排序前Ri先于Rj(i

排序算法有许多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。

评价排序算法的标准有：执行时间和所需的辅助空间，其次是算法的稳定性。

若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是O(1) ，则称排序方法是就地排序，否则是非就地排序。

排序的分类

待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。

① 待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序；

② 待排序的记录数太多：所有的记录不可能存放在内存中， 排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。

1.3 内部排序的基本操作

对内部排序地而言，其基本操作有两种：

◆ 比较两个关键字的大小；

◆ 存储位置的移动：从一个位置移到另一个位置。

第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是：

① 记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的；

② 记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录；

③ 记录存储在一组连续地址的存储空间：构造另一个辅助表来保存各个记录的存放地址(指针) ：排序过程不需要移动记录，而仅需修改辅助表中的指针，排序后视具体情况决定是否调整记录的存储位置。

①比较适合记录数较少的情况；而②、③则适合记录数较少的情况。 为讨论方便，假设待排序的记录是以①的情况存储，且设排序是按升序排列的；关键字是一些可直接用比较运算符进行比较的类型。

2 插入排序

采用的是以 “玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1, R2 ,…., Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。

最基本的插入排序是直接插入排序(Straight Insertion Sort) 。

2.1 直接插入排序

2.1.1排序思想

将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。

设待排序的记录顺序存放在数组R[1…n]中，在排序的某一时刻，将记录序列分成两部分：

◆ R[1…i-1]：已排好序的有序部分；

◆ R[i…n]：未排好序的无序部分。

显然，在刚开始排序时，R[1]是已经排好序的。

例：设有关键字序列为：7, 4, -2, 19, 13, 6，直接插入排序的过程如下图1所示：

2.1.2 算法实现

class Solution:

def straight_insert_sort(self,nums):

"""

:type nums: List

:rtype: None

"""

if len(nums)

return

numsLen=len(nums)

for i in range(1,numsLen):

j=i

tmp=nums[j]

while j>=1:

if tmp

nums[j]=nums[j-1]

j-=1

else:

break

nums[j]=tmp

2.1.3 算法说明

算法中的R[0]开始时并不存放任何待排序的记录，引入的作用主要有两个：

① 不需要增加辅助空间： 保存当前待插入的记录R[i]，R[i]会因为记录的后移而被占用；

② 保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录，起“哨兵监视”作用，避免在内循环中每次都要判断j是否越界。

2.1.4 算法分析

⑴ 最好情况：若待排序记录按关键字从小到大排列(正序)，算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次(R[i]→R[0], R[0]→R[j+1])，则整个排序的关键字比较次数和记录移动次数分别是n-1和2(n-1)

⑵ 最坏情况：若待排序记录按关键字从大到小排列(逆序)，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。

则就整个排序而言比较次数为(n-1)(n+1)/2，移动次数为(n-1)(n+4)/2。

一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n2/4，则复杂度为O(n2) 。

3 希尔排序

希尔排序(Shell Sort，又称缩小增量法)是一种分组插入排序方法。

3.1 排序思想

① 先取一个正整数d1(d1

② 取新的增量d23.2 排序示例

设有10个待排序的记录，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希尔排序的过程如图所示。

3.3 算法实现

class Solution:

def shell_pass(self,nums,inc):

"""

:type nums: List

:rtype: None

"""

if len(nums)

return

numsLen=len(nums)

for i in range(1,numsLen):

j=i-inc

tmp=nums[i]

while j>=0:

if tmp

nums[j+inc]=nums[j]

j-=inc

else:

break

nums[j+inc]=tmp

def shell_sort(self,nums,dk):

"""

:type nums,dk: List

:rtype: None

"""

if len(nums)

return

numsLen=len(dk)

for i in range(0,numsLen):

self.shell_pass(nums,dk[i])

先给出一趟希尔排序的算法，类似直接插入排序。

然后在根据增量数组dk进行希尔排序。

希尔排序的分析比较复杂，涉及一些数学上的问题，其时间是所取的“增量”序列的函数。

希尔排序特点

子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。

希尔排序可提高排序速度，原因是：

◆ 分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了；

◆ 关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序。

增量序列取法

◆ 无除1以外的公因子；

◆ 最后一个增量值必须为1。

4 冒泡排序

4.1 排序思想

依次比较相邻的两个记录的关键字，若两个记录是反序的(即前一个记录的关键字大于后前一个记录的关键字)，则进行交换，直到没有反序的记录为止。

① 首先将L->R[1]与L->R[2]的关键字进行比较，若为反序(L->R[1]的关键字大于L->R[2]的关键字)，则交换两个记录；然后比较L->R[2]与L->R[3]的关键字，依此类推，直到L->R[n-1]与L->R[n]的关键字比较后为止，称为一趟冒泡排序，L->R[n]为关键字最大的记录。

② 然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作。

一般地，第i趟冒泡排序是对L->R[1 … n-i+1]中的记录进行的，因此，若待排序的记录有n个，则要经过n-1趟冒泡排序才能使所有的记录有序。

4.2 排序示例

设有9个待排序的记录，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的过程如图所示。

4.3 算法实现

class Solution:

def bubble_Sort(self,nums):

"""

:type nums: List

:rtype: None

"""

if len(nums)

return

numsLen=len(nums)

for i in range(numsLen-1):

for j in range(numsLen-i-1):

if nums[j]>nums[j+1]:

nums[j],nums[j+1]=nums[j+1],nums[j]

4.4 算法分析

时间复杂度

◆ 最好情况(正序)：比较次数：n-1；移动次数：0；

◆ 最坏情况(逆序)：比较次数n(n-1)/2，移动次数3n(n-1)/2，故时间复杂度：T(n)=O(n²)，空间复杂度：S(n)=O(1)

5 快速排序

5.1 排序思想

通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。

5.2 排序过程

设待排序的记录序列是R[s…t] ，在记录序列中任取一个记录(一般取R[s])作为参照(又称为基准或枢轴)，以R[s].key为基准重新排列其余的所有记录，方法是：

◆ 所有关键字比基准小的放R[s]之前；

◆ 所有关键字比基准大的放R[s]之后。

以R[s].key最后所在位置i作为分界，将序列R[s…t]分割成两个子序列，称为一趟快速排序。

5.3 一趟快速排序方法

从序列的两端交替扫描各个记录，将关键字小于基准关键字的记录依次放置到序列的前边；而将关键字大于基准关键字的记录从序列的最后端起，依次放置到序列的后边，直到扫描完所有的记录。

设置指针low，high，初值为第1个和最后一个记录的位置。

设两个变量i，j，初始时令i=low，j=high，以R[low].key作为基准(将R[low]保存在R[0]中) 。

① 从j所指位置向前搜索：将R[0].key与R[j].key进行比较：

◆ 若R[0].key≤R[j].key ：令j=j-1，然后继续进行比较， 直到i=j或R[0].key>R[j].key为止；

◆ 若R[0].key>R[j].key ：R[j]R[i]，腾空R[j]的位置， 且令i=i+1；

② 从i所指位置起向后搜索：将R[0].key与R[i].key进行比较：

◆ 若R[0].key≥R[i].key ：令i=i+1，然后继续进行比较， 直到i=j或R[0].key

◆ 若R[0].key

重复①、②，直至i=j为止，i就是R0所应放置的位置。

5.4 一趟排序示例

设有6个待排序的记录，关键字分别为29, 38, 22, 45, 23, 67，一趟快速排序的过程如图所示。

5.5 算法实现

当进行一趟快速排序后，采用同样方法分别对两个子序列快速排序，直到子序列记录个为1为止。

class Solution:

def quick_Sort(self,nums,low,high):

"""

:type nums: List,low,high:int

:rtype: None

"""

if len(nums)

return

if low>=high:

return

tmp=nums[low]#选择low所在位置值为轴

i,j=low,high

#采用插空法来保证左边都比轴值小，右边都比轴值大

while i

while j>i and nums[j]>=tmp:#找到右边第一个比轴值小的值

j-=1

nums[i]=nums[j]

while i

i+=1

nums[j]=nums[i]

nums[i]=tmp

#递归处理

self.quick_Sort(nums,low,i-1)

self.quick_Sort(nums,i+1,high)

5.6 算法分析

快速排序的主要时间是花费在划分上，对长度为k的记录序列进行划分时关键字的比较次数是k-1 。设长度为n的记录序列进行排序的比较次数为C(n)，则C(n)=n-1+C(k)+C(n-k-1) 。

◆ 最好情况：每次划分得到的子序列大致相等，则C(n)≤O(n×㏒2n) ；

◆ 最坏情况：每次划分得到的子序列中有一个为空，另一个子序列的长度为n-1。即每次划分所选择的基准是当前待排序序列中的最小(或最大)关键字，比较次数C(n)=O(n2)

◆ 一般情况： 对n个记录进行快速排序所需的时间T(n)组成是：

① 对n个记录进行一趟划分所需的时间是：n×C ，C是常数；

② 对所得到的两个子序列进行快速排序的时间：

Tavg(n)=C(n)+Tavg(k-1)+Tavg(n-k)

若记录是随机排列的，k取值在1~n之间的概率相同，则快速排序的平均时间复杂度是O(n㏒2n)。从排序的稳定性来看，快速排序是不稳定的。

6 选择排序

选择排序(Selection Sort)的基本思想是：每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。

简单选择排序(Simple Selection Sort ，又称为直接选择排序)的基本操作是：通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录，然后和第i个记录进行交换，i=1, 2, … n-1 。

6.1 排序示例

例：设有关键字序列为：7, 4, -2, 19, 13, 6，直接选择排序的过程如下图所示。

6.2 算法实现

class Solution:

def selection_sort(self,nums):

"""

:type nums: List

:rtype: None

"""

if len(nums)

return

numsLen=len(nums)

for i in range(numsLen-1):

for j in range(i+1,numsLen):

if nums[i]>nums[j]:

nums[i],nums[j]=nums[j],nums[i]

6.3 算法分析

整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。

进行第i趟排序时，关键字的比较次数为n-i，则：比较次数n(n-1)/2,时间复杂度是：T(n)=O(n2)

空间复杂度是：S(n)=O(1)

从排序的稳定性来看，直接选择排序是不稳定的。

7 堆排序

7.1 堆的定义

堆是n个元素的序列H= ，满足：

由堆的定义知，堆是一棵以k1为根的完全二叉树。若对该二叉树的结点进行编号(从上到下，从左到右)，得到的序列就是将二叉树的结点以顺序结构存放，堆的结构正好和该序列结构完全一致。

7.2 堆的性质

① 堆是一棵采用顺序存储结构的完全二叉树， k1是根结点；

② 堆的根结点是关键字序列中的最小(或最大)值，分别称为小(或大)根堆；

③ 从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的；

堆中的任一子树也是堆。

利用堆顶记录的关键字值最小(或最大)的性质，从当前待排序的记录中依次选取关键字最小(或最大)的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。

7.3 堆排序思想

① 对一组待排序的记录，按堆的定义建立堆；

② 将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的；

③ 堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区；

④ 重复上述步骤，直到全部记录排好序为止。

结论：排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。

堆排序的关键：

① 如何由一个无序序列建成一个堆？

② 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？

7.4 堆的调整——筛选

⑴ 堆的调整思想

输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值，将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选”，如图所示。

注意：筛选过程中，根结点的左、右子树都是堆，因此，筛选是从根结点到某个叶子结点的一次调整过程。

⑵ 堆调整算法实现

7.5 堆的建立

利用筛选算法，可以将任意无序的记录序列建成一个堆，设R[1],R[2], …,R[n]是待排序的记录序列。

将二叉树的每棵子树都筛选成为堆。只有根结点的树是堆。第⌊n/2⌋个结点之后的所有结点都没有子树，即以第n/2个结点之后的结点为根的子树都是堆。因此，以这些结点为左、右孩子的结点，其左、右子树都是堆，则进行一次筛选就可以成为堆。同理，只要将这些结点的直接父结点进行一次筛选就可以成为堆。

只需从第n/2个记录到第1个记录依次进行筛选就可以建立堆。

7.6 堆排序算法实现

堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，则进行一次筛选就可以成为堆。

class Solution:

def heap_adjust(self,nums,m):

"""

:type nums: List,m:int

:rtype: None

"""

if len(nums)

return

flag=m//2

for i in range(flag,-1,-1):

pos=i

while pos

index=-1

#维持堆的性质

if 2*pos+2

nums[pos],nums[2*pos+2]=nums[2*pos+2],nums[pos]

index=2*pos+2

if 2*pos+1

nums[pos],nums[2*pos+1]=nums[2*pos+1],nums[pos]

index=2*pos+1

#迭代处理

if index!=-1:

pos=index

else:

break

def heap_sort(self,nums):

"""

:type nums: List

:rtype: None

"""

if len(nums)

return

numsLen=len(nums)

for i in range(numsLen):

#调整最大值堆，使之满足堆的性质，同时交换第一个值和最后一个值

self.heap_adjust(nums,numsLen-i-1)

nums[0],nums[numsLen-i-1]=nums[numsLen-i-1],nums[0]

7.7 算法分析

主要过程：初始建堆和重新调整成堆。设记录数为n，所对应的完全二叉树深度为h 。

◆ 初始建堆：每个非叶子结点都要从上到下做“筛选” 。第i层结点数≤2i-1，结点下移的最大深度是h-i，而每下移一层要比较2次，则比较次数C1(n)≤4(n-㏒2n-1)。

◆ 筛选调整：每次筛选要将根结点“下沉”到一个合适位置。第i次筛选时：堆中元素个数为n-i+1；堆的深度是㏒2(n-i+1)+1，则进行n-1次“筛选”的比较次数C2(n)8 归并排序

归并(Merging) ：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表(无论是那种存储结构)易于实现，其时间复杂度为O(m+n) 。

归并思想实例：两堆扑克牌，都已从小到大排好序，要将两堆合并为一堆且要求从小到大排序。

◆ 将两堆最上面的抽出(设为C1，C2)比较大小，将小者置于一边作为新的一堆(不妨设C1

◆ 重复上述过程，直到某一堆已抽完，然后将剩下一堆中的所有牌转移到新堆中。

8.1 排序思想

① 初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列；

② 对所有有序子序列进行两两归并，得到n/2个长度为2或1的有序子序列——一趟归并；

③ 重复② ，直到得到长度为n的有序序列为止。

上述排序过程中，子序列总是两两归并，称为2-路归并排序。其核心是如何将相邻的两个子序列归并成一个子序列。设相邻的两个子序列分别为：和，将它们归并为一个有序的子序列：

例：设有9个待排序的记录，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，归并排序的过程如图所示。

8.2 归并实现

8.2.1 一趟归并

一趟归并排序都是从前到后，依次将相邻的两个有序子序列归并为一个，且除最后一个子序列外，其余每个子序列的长度都相同。设这些子序列的长度为d，则一趟归并排序的过程是：

从j=1开始，依次将相邻的两个有序子序列R[j…j+d-1]和R[j+d…j+2d-1]进行归并；每次归并两个子序列后，j后移动2d个位置，即j=j+2d；若剩下的元素不足两个子序列时，分以下两种情况处理：

① 剩下的元素个数>d：再调用一次上述过程，将一个长度为d的子序列和不足d的子序列进行归并；

② 剩下的元素个数≤d：将剩下的元素依次复制到归并后的序列中。

8.2.2 归并排序的算法

开始归并时，每个记录是长度为1的有序子序列，对这些有序子序列逐趟归并，每一趟归并后有序子序列的长度均扩大一倍；当有序子序列的长度与整个记录序列长度相等时，整个记录序列就成为有序序列。

class Solution:

def merge_sort(self,nums,low,high):

"""

:type nums: List,low,high:int

:rtype: None

"""

if len(nums)

return

if low>=high:

return

#递归处理

mid=(low+high)//2

self.merge_sort(nums,low,mid)

self.merge_sort(nums,mid+1,high)

#归并处理

numsLen=high-low+1

tmp=[]

i,j=low,mid+1

while i

if nums[i]

tmp.append(nums[i])

i+=1

else:

tmp.append(nums[j])

j+=1

#若其中一个序列还没有归并，则迭代加入

while i

tmp.append(nums[i])

i+=1

while j

tmp.append(nums[j])

j+=1

nums[low:high+1]=tmp

8.3 算法分析

具有n个待排序记录的归并次数是㏒2n，而一趟归并的时间复杂度为O(n)，则整个归并排序的时间复杂度无论是最好还是最坏情况均为O(n㏒2n)。在排序过程中，使用了辅助向量DR，大小与待排序记录空间相同，则空间复杂度为O(n)。归并排序是稳定的。

9 基数排序

基数排序(Radix Sorting) 又称为桶排序或数字排序：按待排序记录的关键字的组成成分(或“位”)进行排序。

基数排序和前面的各种内部排序方法完全不同，不需要进行关键字的比较和记录的移动。借助于多关键字排序思想实现单逻辑关键字的排序。

9.1 多关键字排序

设有n个记录， 每个记录Ri的关键字是由若干项(数据项)组成，即记录Ri的关键字Key是若干项的集合： (d>1) 。

记录有序的，指的是i, j∈[1,n]，i

即Kip ≤Kjp (p=1, 2, … d)

多关键字排序思想

先按第一个关键字K1进行排序，将记录序列分成若干个子序列，每个子序列有相同的K1值；然后分别对每个子序列按第二个关键字K2进行排序，每个子序列又被分成若干个更小的子序列；如此重复，直到按最后一个关键字Kd进行排序。

最后，将所有的子序列依次联接成一个有序的记录序列，该方法称为最高位优先(Most Significant Digit first)。

另一种方法正好相反，排序的顺序是从最低位开始，称为最低位优先(Least Significant Digit first)。

9.2 链式基数排序

若记录的关键字由若干确定的部分(又称为 “位”)组成，每一位(部分)都有确定数目的取值。对这样的记录序列排序的有效方法是基数排序。

设有n个待排序记录， (单)关键字是由d位(部分)组成，每位有r种取值，则关键字R[i].key可以看成一个d元组： R[i].key= 。

基数排序可以采用前面介绍的MSD或LSD方法。以下以LSD方法讨论链式基数排序。

9.2.1 排序思想

⑴ 首先以静态链表存储n个待排序记录，头结点指针指向第一个记录结点；

⑵ 一趟排序的过程是：

① 分配： 按Kd值的升序顺序，改变记录指针，将链表中的记录结点分配到r个链表(桶)中，每个链表中所有记录的关键字的最低位(Kd)的值都相等，用f[i]、e[i]作为第i个链表的头结点和尾结点；

② 收集：改变所有非空链表的尾结点指针，使其指向下一个非空连表的第一个结点，从而将r个链表中的记录重新链接成一个链表；

⑶ 如此依次按Kd-1, Kd-2, … K1分别进行，共进行d趟排序后排序完成。

9.2.2 链式基数排序算法

为实现基数排序，用两个指针数组来分别管理所有的缓存(桶)，同时对待排序记录的数据类型进行改造.

9.3 基数排序实现

class RecType(object):

def __init__(self, x):

self.data = x

self.next=None

class Solution:

def radix_sort(self,nums):

"""

:type nums: List[int]

:rtype: None

"""

if len(nums)

return

numsLen=len(nums)

flag=True

base=1

#基数排序，迭代处理

while flag:

flag=False

bucket=[None]*10

for i in range(numsLen):

index=(nums[i]%(10*base))//base

#将值入桶

if bucket[index]==None:

bucket[index]=RecType(nums[i])

else:

tmp=bucket[index]

while tmp.next!=None:

tmp=tmp.next

tmp.next=RecType(nums[i])

#判断继续还需要排序

if index>0:

flag=True

#更新基数

base=10*base

#将此轮排序结果保存

nums.clear()

for i in range(10):

tmp=bucket[i]

while tmp!=None:

nums.append(tmp.data)

tmp=tmp.next

9.4 算法分析

设有n个待排序记录，关键字位数为d，每位有r种取值。则排序的趟数是d；在每一趟中：

◆ 链表初始化的时间复杂度：O(r) ；

◆ 分配的时间复杂度：O(n) ；

◆ 分配后收集的时间复杂度：O(r) ；

则链式基数排序的时间复杂度为： O(d(n+r))

在排序过程中使用的辅助空间是：2r个链表指针， n个指针域空间，则空间复杂度为：O(n+r)

基数排序是稳定的。

10 各种内部排序的比较

各种内部排序按所采用的基本思想(策略)可分为：插入排序、交换排序、选择排序、归并排序和基数排序，它们的基本策略分别是：

1 插入排序：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序一个子序列的适当位置，直到所有的记录都插入为止。具体的方法有：直接插入、表插入、2-路插入和shell排序。

2 交换排序：对于待排序记录序列中的记录，两两比较记录的关键字，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。具体的方法有：冒泡排序、快速排序。

3 选择排序：不断地从待排序的记录序列中选取关键字最小的记录，放在已排好序的序列的最后，直到所有记录都被选取为止。具体的方法有：简单选择排序、堆排序。

4 归并排序：利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序序列为止。

5 基数排序：按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位”的值将所有记录分配到相应的桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序列。

各种内部排序方法的性能比较如下表：

选取排序方法的主要考虑因素：

◆ 待排序的记录数目n；

◆ 每个记录的大小；

◆ 关键字的结构及其初始状态；

◆ 是否要求排序的稳定性；

◆ 语言工具的特性；

◆ 存储结构的初始条件和要求；

◆ 时间复杂度、空间复杂度和开发工作的复杂程度的平衡点等。