一、排序的概念

课本概念（P165）

• (1）内部排序。内部排序指待排序记录全部存放在内存中进行排序的过程。
• (2）外部排序。外部排序指待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

在排序过程中需要进行下列两种基本操作：比较两个关键字的大小；将记录从一个位置移动到另一个位置。前一种操作对大多数排序方法来说都是必要的，后一种操作可以通过改变记录的存储方式来避免。

二、直接插入排序

直接插入排序：即当插入第i个记录时，Ri，Ra，…，R,均己排好序，因此，将第i个记录R,依次与R1，.，R，R进行比较，找到合适的位置插入。它简单明了，但速度很慢。

希尔排序

希尔(Shell） 排序：先取一个小于n的整数d，作为第一个增量，把文件的全部记录分成d个组。所有距离为q的倍数的记录放在同一个组中。先在各组内进行直接插入排序然后，取第二个增量d2d_2d2​<d1d_1d1​重复上述的分组和排序，直至所取的增量d=1(d<dt−1d_{t-1}dt−1​<o<d2d_2d2​<d1d_1d1​），即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

三、直接选择排序

直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依次类推，直到所有记录排完为止。

四、堆排序

1、堆的概念

设有n个元素的序列{K，K，⋯，K,}，当且仅当满足下述关系之一时，称之为堆。
(1) kik_iki​≤k2ik_{2i}k2i​, 且kik_iki​≤k2i+1k_{2i+1}k2i+1​;
(2）kik_iki​≥k2ik_{2i}k2i​, 且kik_iki​≥k2i+1k_{2i+1}k2i+1​;
其中(1)称为小顶堆，（2)称为大顶堆

2、堆排序

五、冒泡排序

冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。

六、快速排序

快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组合成原问题的解。快速排序通常包括两个步骤：第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。第二步，采用相同的方法对左、右两组分别进行排序，直到所有记录都排到相应的位置为止。

七、归并排序

归并也称为合并，是将两个或两个以上的有序子表合井成一个新的有序表。若将两个有序表合井成一个有序表，则称为二路合并。合并的过程是：比较A[i]和A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。

八、基数排序

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。

排序算法的时间复杂度和空间复杂度