第八章 排序

⑵ 最坏情况：若待排序记录按关键字从大到小排列 (逆序)，则一趟排序时：算法中的内循环体执行 i-1 ，关键字比较次数i次，记录移动次数i+1。 则就整个排序而言：
比较次数： ∑ i= i=2 n 移动次数： ∑(i+1)= i=2 n
(n-1)(n+1)
2
(n-1)(n+4)
2
一般地，认为待排序的记录可能出现的各种排列的 概率相同，则取以上两种情况的平均值，作为排序的关 键字比较次数和记录移动次数，约为n2/4，则复杂度为 O(n2) 。
直接插入排序
1、排序思想：设待排序的记录顺序存放在数组 R[1…n]中，在排序的某一时刻，将记录序列分成两 部分： ◆ R[1…i-1]：已排好序的有序部分； ◆ R[i…n]：未排好序的无序部分。 将待排序的记录Ri，插入到已排好序的记录表 R1, R2 ,…., Ri-1中，得到一个新的、记录数 增加1的有序表。 直到所有的记录都插入完为 止 显然，在刚开始排序时，R[1]是已经排好序的。
设有9个待排序的记录，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的过程如图所 示。
初始关键字序列: 23 第一趟排序后: 第二趟排序后: 第三趟排序后: 第四趟排序后: 第五趟排序后: 第六趟排序后: 第七趟排序后: 23 22 22 22 22 15 38 22 23 23 23 15 22 22 38 23 45 23 38 23 45 31 67 31 15 31 15 41 15 41 45 45 45 45 45 41 67 67 67 67 67 67
4 4 4 4 4 4 4
-2 7 7 6 6 6 6
19 19 19 19 7 7 7
13 13 13 13 13 13 13
6 6 6 7 19 19 19
直接选择排序的过程
2.算法实现： void simple_selection_sort(int *R,int n) { int i, j , k; for (i=1; i<n; i++) { k=i ; for (j=i+1; j<=n; j++) if (R[j]<R[k]) k=j ; if (k!=j) {R[0]=R[j]; R[j]=R[k];R[j]=R[0];} } }
设有6个待排序的记录，关键字分别为29, 38, 22, 45, 23, 67，一趟快速排序的过程如图所示。
初始关键字序列: 0 29 29 i 23 38 22 45 23 67 31
j前移2个位置后, 29 R[j]放R[i]的位置: i后移1个位置后, R[i]放R[j]的位置:
38
22
22
（2)快速排序的算法
void quick_Sort(int *R,int low, int high) { int k ; if (low<high) { k=quick_one_pass(R, low, high); quick_Sort(R, low, k-1); quick_Sort(R, k+1, high); } /*序列分为两部分后分别对每个子序列排序 */ }
i=1 n-1
n(n-1)
2
i=1 n-1
3n(n-1)
2
故时间复杂度：T(n)=O(n² ) 空间复杂度：S(n)=O(1) 起泡排序是稳定排序。
快速排序
1、排序思想：通过一趟排序，将待排序记录分割成独 立的两部分，其中一部分记录的关键字均比另一部分 记录的关键字小，再分别对这两部分记录进行下一趟 排序，以达到整个序列有序。 设待排序的记录序列是R[s…t] ，在记录序列中任取 一个记录(一般取R[s])作为参照(又称为基准或枢轴)， 以R[s]为基准重新排列其余的所有记录，方法是： （1）所有关键字比基准小的放R[s]之前； （2）所有关键字比基准大的放R[s]之后。 （3）以R[s]最后所在位置i作为分界，将序列R[s…t] 分割成两个子序列，称为一趟快速排序。
2、排序的稳定性 若记录序列中有两个或两个以上关键字相等的记 录： Ki =Kj(i≠j，i, j=1, 2, … n)，且在排序前 Ri先于Rj(i<j)，排序后的记录序列仍然是Ri先于Rj， 称排序方法是稳定的，否则是不稳定的。 评价排序算法的标准有：执行时间和所需的辅助 空间，其次是算法的稳定性。
3. 算法分析
⑴ 最好情况：若待排序记录按关键字从小到大排列 (正序)，算法中的内循环无须执行，则一趟排序时： 关键字比较次数1次，记录移动次数2次(R[i]→R[0], R[0]→R[j+1])。则整个排序的关键字比较次数和记 录移动次数分别是：
比较次数： ∑1=n-1 i=2 n 移动次数： ∑ 2=2(n-1) i=2 n
19] 13 13
19] 6 19]
第五趟排序： [-2 4 6 7 13 直接插入排序的过程
2.算法实现
void straight_insert_sort(int *R ,int n) { int i, j ; for (i=2; i<=n; i++) { R[0]=R[i]; j=i-1; /* 设置哨兵 */ while(R[0]<R[j]) ) { R[j+1]=R[j]; j--; } /* 查找插入位置 */ R[j+1]=R[0]; /* 插入到相应位置 */ } }
3、排序的分类 待排序的记录数量不同，排序过程中涉及的存储 器的不同，有不同的排序分类。 ①待排序的记录数不太多：所有的记录都能存放 在内存中进行排序，称为内部排序； ②待排序的记录数太多：所有的记录不可能存放 在内存中， 排序过程中必须在内、外存之间进 行数据交换，这样的排序称为外部排序。
4、排序算法的性能 对内部排序地而言，其基本操作有两种： ◆比较两个关键字的大小； ◆存储位置的移动：从一个位置移到另一个位 置。 第一种操作是必不可少的；而第二种操作却不 是 必须的，取决于记录的存储方式。 内排序算法时间性能取决于排序过程中关键字 比较的次数和记录的移动次数。
简单选择排序
1.排序思想：通过n-i次关键字间的比较，从n-i+1个 记录中选取关键字最小的记录，然后和第i个记录进 行交换，i=1, 2, … n-1 。 例：设有关键字序列为：7, 4, -2, 19, 13, 6，直 接选择排序的过程如下图所示。
初始记录的关键字： 7 第一趟排序：-2 第二趟排序： -2 第三趟排序： -2 第四趟排序： -2 第五趟排序： -2 第六趟排序： -2
例：设有关接插入排序的过程如下图所示：
初始记录的关键字： [7] 第一趟排序： [4 第二趟排序： [-2 第三趟排序： [-2 第四趟排序： [-2 4 7] 4 4 4 -2 19 -2 19 7] 7 7 19 13 13 13 6 6 6 6
45
45 j 38 j 38
j 67 31 67 31
i 29 23 i 29 23 22
j前移2个位置后, R[j]放R[i]的位置: i i后前移1个位置后, 29 23 22 i和j的位置重合:
45
j 29 ij
67 67
31 31
45
38
一趟快速排序过程
2.算法实现
（1)一趟快速排序的算法 int quick_one_pass(int *R, int low, int high) { int i=low, j=high ; R[0]=R[i] ; do { while (R[0]<R[j]&&(j>i)) j-- ; if (j>i) {R[i]=R[j] ; i++; } while (R[i]<R[0]&&(j>i)) i++ ; if (j>i) { R[j]=R[i] ; j--; } } while(i!=j) ; /* i=j时退出扫描 */ return(i) ; }
3. 算法分析
快速排序的时间和空间性能取决于递归调用的深度， 可以用递归调用树来表示快速排序的过程。下图给出了 {23,13,49,6,31,19,28}快速排序的递归调用树： 23 19 6 13
31
28 49
（1）时间复杂度
最好情况：每次分割后左右长度基本相同，要进行 [log2n]+1次调用.时间复杂度为O(n [log2n]). 最差情况：每次分割后子比上一次少一个，要进行 n-1次调用。时间复杂度为O(n 2). 平均情况：元素为随机排列，时间复杂度为O(n [log2n]). （2）空间复杂度 快速排序是递归的需要用栈存储递归信息，栈的最 大容量和递归调用深度是一致的。最好情况O( [log2n]), 最差情况O(n),平均情况O( [log2n])。 （3）排序是不稳定的。
第8章
[内容提要]
1.排序的基本概念 2.插入排序
a.直接插入排序 b.希尔排序
排序
3.交换排序
a.冒泡排序 b.快速排序
4.选择排序
a.简单选择排序 b.堆排序
5.归并排序 6.基数排序
排序的基本概念
1、排序(Sorting) 排序是将一批(组)任意次序的记录重新排列成按 关键字有序的记录序列的过程，其定义为： 给定一组记录序列：{R1 , R2 ,…, Rn}，其相应 的关键字序列是{K1 , K2 ,…, Kn} 。确定1, 2, … n的一个排列p1 , p2 ,…, pn，使其相应的关键字满 足如下非递减(或非递增)关系： Kp1≤Kp2 ≤…≤Kpn的序列{Kp1 ,Kp2 , …,Kpn} ，这种操作 称为排序。
22 23
23
23 15 23 23
31
15 23 23 23