4.4 基本排序
4.4.1 概 述
1、排序的功能,将一个数据元素（或记录）的 任意序列,重新排成一个按关键字 有序 的序列。
2、排序过程的组成步骤：
首先 比较 两个关键字的大小；
然后将记录从一个位置 移动 到另一个位置。
3,用于内存文件的排序假设待排序的记录存放在地址连续的一组存储单元中,那么这种存储方式下的数据类型可描述为：
MAX
0
1
2
3
4
…
…
…
key info#define MAX 20
typedef struct
{ int key;
float otherinfo;
}RedType;
基本排序插入排序选择排序交换排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序快速排序基数排序
shell排序
4.4.2 插入排序插入排序基本思想,
每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。
该算法适合于 n 较小的情况,时间复杂度为 O(n2).
基本思想,从数组的第 2号元素开始，顺序从数组中取出元素，
并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列,[53] 27 36 15 69 42
第一次排序,[27 53] 36 15 69 42
第二次排序,[27 36 53] 15 69 42
第三次排序,[15 27 36 53] 69 42
第四次排序,[15 27 36 53 69] 42
第五次排序,[15 27 36 42 53 69]
直接插入排序示例对于有 n个数据元素的待排序列，插入操作要进行 n-1
次直接插入排序,
void insertSort(RedType L[ ],int n)
{ int i,j;
for(i=2; i<=n; i++)
if(L[i].key<L[i-1].key)
{ L[0]=L[i]; /* 作为监视哨 */
for( j=i-1; L[0].key<L[j].key;j )
L[j+1]=L[j]; /* 记录后移 */
L[j+1]=L[0]; /* 插入 */
}
}
插入算法如下：
方法,Ki与 Ki-1,K i-2,… K1依次比较,直到找到应插入的位置 。
基本思想,
每一趟在 n-i+1个记录中选取关键码最小的记录作为有序序列中第 i个记录。
4.4.3 选择排序思想,首先从 1~n个元素中选出关键字 最小 的记录交换到 第一个 位置上。然后再从第 2 个到第 n个元素中选出次小的记录交换到 第二个 位置上，依次类推。
时间复杂度为 O(n2)，
适用于 待排序元素较少 的情况。
初态 8 3 9 1 6
8 3 9 1 6
8 3 9 1 6
8 3 9 1 6
i j
k
i jk
i jk
i jk
1 3 9 8 6
互换
i j
k
1 3 9 8 6
i
k
j
1 3 9 8 6
i
k
j
第一趟第二趟
1 3 9 8 6
i k j
第三趟简单选择排序简单选择排序的算法如下：
void SelectSort( RedType L[ ],int n)
{ int i,j,k,t;
for (i=1,i<=n;++i） /*选择第 i小的元素，并交换到位 */
{ k=i；
for(j=i+1;j<=n;++j)
if ( L[j].key<L[k].key) k=j; /*L[k] 中存放的是第 I小的元素 */
if(k!=i) { t=L[i]; /*交换 */
L[i]=L[k]; L[k]=t ； }
} /*FOR*/
} /* SelectSort*/
4.4.4 交 换 排 序（互换排序）
互换排序：
借助数据元素之间的相互交换进行的一种排序方法。
特点,交换 。
有冒泡和快速排序两种。
1,冒泡排序 （ 起泡排序 ）
思想,小的浮起，大的沉底。 从左端开始比较。
第一趟：第 1个与第 2个比较,大则交换；第 2个与第 3个比较,
大则交换,…… 关键字最大的记录交换到最后一个位置上；
第二趟：对前 n-1个记录进行同样的操作,关键字次大的记录交换到第 n-1个 位置上；
依次类推,则完成排序 。
时间复杂度：
正序：时间复杂度为 O(n) 逆序：时间复杂度为 O(n2)
适合：数据较少的情况。
排序 n个 记录的文件最多需要 n-1趟冒泡排序。
第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字思 想,小 的浮起,大的沉底 。
4936416511
7836
653641
56364165
413641561178
36364149115649
25252511494956
11111125252525
冒泡排序的 C程序段：
Void bubsort(RedType L[ ],int n)
{ int i,x,j=1,k=1;
while (j<n)&&(k>0);
{ k=0;
for (i=1;i<=n-j; i++)
if (L[i+1].key<L[i].key)
{k++;x=L[i];L[i]=L[i+1];L[i+1]=x;}
j++;
} /*while*/
} /*Bobsort*/
思想,通过一趟排序将待排序列 分成两部分,使其中 一部分记录 的关键字均比 另一部分小,再分别对这两部分排序，以达到整个序列有序。
关键字通常取第一个记录的值为基准值 。
做法,附设两个指针 low和 high,初值分别指向 第一个记录 和 最后一个记录,设关键字为 key,首先从 high所指位置起 向前 搜索,找到第一个 小于 基准值的记录与基准记录交换,然后从 low 所指位置起 向后 搜索,找到第一个 大于 基准值的记录与基准记录交换,重复这两步直至 low=high为止 。
时间复杂度,O(log2n)
2、快速排序 (对冒泡排序的改进）
快速排序过程示意图：
有序序列 6 18 23 52 67
key
初始序列 23 52 6 67 18
low high
一次交换 18 52 6 67 23
low high
二次交换 18 23 6 67 52
high
三次交换 [18 6] 23 [67 52]
// 完成一趟排序后分别进行快速排序
low high
4.4 小结基本排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有,待排序的记录个数；记录本身的大小；记录的键值分布情况 等。
若待排序的记录个数 n较小时，可采用简单排序方法。
若 n 较大时，应采用快速排序。
若待排序的记录已基本有序，可采用直接插入排序或起泡排序。
4.5 索引树用于外存文件的索引 。
040008
375
04 5 1 12 2 36 39 2 4 90 5 60 63 1 67 0
1
10
050 212142135 279240237 388381378 471435400396393 553502492 629626557 660652633 678673671
一棵 6阶的 B树当 m=2时,m阶 B树实际上就是二叉排序树。所以 m阶
B树是二叉排序树的推广。
4.4.1 概 述
1、排序的功能,将一个数据元素（或记录）的 任意序列,重新排成一个按关键字 有序 的序列。
2、排序过程的组成步骤：
首先 比较 两个关键字的大小；
然后将记录从一个位置 移动 到另一个位置。
3,用于内存文件的排序假设待排序的记录存放在地址连续的一组存储单元中,那么这种存储方式下的数据类型可描述为：
MAX
0
1
2
3
4
…
…
…
key info#define MAX 20
typedef struct
{ int key;
float otherinfo;
}RedType;
基本排序插入排序选择排序交换排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序快速排序基数排序
shell排序
4.4.2 插入排序插入排序基本思想,
每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。
该算法适合于 n 较小的情况,时间复杂度为 O(n2).
基本思想,从数组的第 2号元素开始，顺序从数组中取出元素，
并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列,[53] 27 36 15 69 42
第一次排序,[27 53] 36 15 69 42
第二次排序,[27 36 53] 15 69 42
第三次排序,[15 27 36 53] 69 42
第四次排序,[15 27 36 53 69] 42
第五次排序,[15 27 36 42 53 69]
直接插入排序示例对于有 n个数据元素的待排序列，插入操作要进行 n-1
次直接插入排序,
void insertSort(RedType L[ ],int n)
{ int i,j;
for(i=2; i<=n; i++)
if(L[i].key<L[i-1].key)
{ L[0]=L[i]; /* 作为监视哨 */
for( j=i-1; L[0].key<L[j].key;j )
L[j+1]=L[j]; /* 记录后移 */
L[j+1]=L[0]; /* 插入 */
}
}
插入算法如下：
方法,Ki与 Ki-1,K i-2,… K1依次比较,直到找到应插入的位置 。
基本思想,
每一趟在 n-i+1个记录中选取关键码最小的记录作为有序序列中第 i个记录。
4.4.3 选择排序思想,首先从 1~n个元素中选出关键字 最小 的记录交换到 第一个 位置上。然后再从第 2 个到第 n个元素中选出次小的记录交换到 第二个 位置上，依次类推。
时间复杂度为 O(n2)，
适用于 待排序元素较少 的情况。
初态 8 3 9 1 6
8 3 9 1 6
8 3 9 1 6
8 3 9 1 6
i j
k
i jk
i jk
i jk
1 3 9 8 6
互换
i j
k
1 3 9 8 6
i
k
j
1 3 9 8 6
i
k
j
第一趟第二趟
1 3 9 8 6
i k j
第三趟简单选择排序简单选择排序的算法如下：
void SelectSort( RedType L[ ],int n)
{ int i,j,k,t;
for (i=1,i<=n;++i） /*选择第 i小的元素，并交换到位 */
{ k=i；
for(j=i+1;j<=n;++j)
if ( L[j].key<L[k].key) k=j; /*L[k] 中存放的是第 I小的元素 */
if(k!=i) { t=L[i]; /*交换 */
L[i]=L[k]; L[k]=t ； }
} /*FOR*/
} /* SelectSort*/
4.4.4 交 换 排 序（互换排序）
互换排序：
借助数据元素之间的相互交换进行的一种排序方法。
特点,交换 。
有冒泡和快速排序两种。
1,冒泡排序 （ 起泡排序 ）
思想,小的浮起，大的沉底。 从左端开始比较。
第一趟：第 1个与第 2个比较,大则交换；第 2个与第 3个比较,
大则交换,…… 关键字最大的记录交换到最后一个位置上；
第二趟：对前 n-1个记录进行同样的操作,关键字次大的记录交换到第 n-1个 位置上；
依次类推,则完成排序 。
时间复杂度：
正序：时间复杂度为 O(n) 逆序：时间复杂度为 O(n2)
适合：数据较少的情况。
排序 n个 记录的文件最多需要 n-1趟冒泡排序。
第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字思 想,小 的浮起,大的沉底 。
4936416511
7836
653641
56364165
413641561178
36364149115649
25252511494956
11111125252525
冒泡排序的 C程序段：
Void bubsort(RedType L[ ],int n)
{ int i,x,j=1,k=1;
while (j<n)&&(k>0);
{ k=0;
for (i=1;i<=n-j; i++)
if (L[i+1].key<L[i].key)
{k++;x=L[i];L[i]=L[i+1];L[i+1]=x;}
j++;
} /*while*/
} /*Bobsort*/
思想,通过一趟排序将待排序列 分成两部分,使其中 一部分记录 的关键字均比 另一部分小,再分别对这两部分排序，以达到整个序列有序。
关键字通常取第一个记录的值为基准值 。
做法,附设两个指针 low和 high,初值分别指向 第一个记录 和 最后一个记录,设关键字为 key,首先从 high所指位置起 向前 搜索,找到第一个 小于 基准值的记录与基准记录交换,然后从 low 所指位置起 向后 搜索,找到第一个 大于 基准值的记录与基准记录交换,重复这两步直至 low=high为止 。
时间复杂度,O(log2n)
2、快速排序 (对冒泡排序的改进）
快速排序过程示意图：
有序序列 6 18 23 52 67
key
初始序列 23 52 6 67 18
low high
一次交换 18 52 6 67 23
low high
二次交换 18 23 6 67 52
high
三次交换 [18 6] 23 [67 52]
// 完成一趟排序后分别进行快速排序
low high
4.4 小结基本排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有,待排序的记录个数；记录本身的大小；记录的键值分布情况 等。
若待排序的记录个数 n较小时，可采用简单排序方法。
若 n 较大时，应采用快速排序。
若待排序的记录已基本有序，可采用直接插入排序或起泡排序。
4.5 索引树用于外存文件的索引 。
040008
375
04 5 1 12 2 36 39 2 4 90 5 60 63 1 67 0
1
10
050 212142135 279240237 388381378 471435400396393 553502492 629626557 660652633 678673671
一棵 6阶的 B树当 m=2时,m阶 B树实际上就是二叉排序树。所以 m阶
B树是二叉排序树的推广。
