当前位置：文档之家 › 第21讲 排序之交换排序和选择排序

第21讲 排序之交换排序和选择排序

  • 格式：pptx
  • 大小：468.75 KB
  • 文档页数：96

下载文档原格式

  / 96

合集下载

选择排序数学公式

选择排序数学公式

选择排序数学公式选择排序（Selection Sort）是一种简单直观的排序算法。

它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

选择排序的数学公式可以这样理解：假设我们要对一个包含 n 个元素的数组进行排序。

在每一轮遍历中，我们都要找出未排序部分的最小（或最大）元素，并与当前位置的元素进行交换。

第一轮，我们从 n 个元素中找到最小的元素，与第 1 个位置的元素交换。

第二轮，我们从剩下的 n - 1 个元素中找到最小的元素，与第 2 个位置的元素交换。

以此类推，第 i 轮，我们从剩下的 n - i + 1 个元素中找到最小的元素，与第 i 个位置的元素交换。

直到第 n - 1 轮结束，整个数组就排序完成了。

为了更直观地理解选择排序的数学公式，咱们来举个例子。

比如说，有一组数字：5，2，9，1，8 。

第一轮，我们从这 5 个数字中找到最小的 1 ，把它和第 1 个位置的5 交换，数组变成了 1，2，9，5，8 。

第二轮，从剩下的 4 个数字 2，9，5，8 中找到最小的 2 ，和第 2个位置的 9 交换，数组变成 1，2，9，5，8 。

第三轮，在剩下的 3 个数字 9，5，8 中找到最小的 5 ，和第 3 个位置的 9 交换，数组变成 1，2，5，9，8 。

第四轮，在剩下的 2 个数字 9，8 中找到最小的 8 ，和第 4 个位置的 9 交换，数组变成 1，2，5，8，9 。

经过这四轮，数组就排序完成啦。

在实际应用中，选择排序的性能并不是特别出色。

它的平均时间复杂度为 O(n²)，空间复杂度为 O(1) 。

这意味着，当数据量较大时，选择排序可能会比较慢，但对于小型数据集或者某些特定场景，它仍然是一种可行的选择。

就像我们在生活中做选择一样，有时候要从一堆选项里挑出最好的或者最适合的。

各种经典排序算法

各种经典排序算法

希尔插入排序——过程
设待排序共有10个记录，其关键字分别为47, 33, 61, 82, 71,
11, 25, 47, 57, 02，增量序列取值依次为5, 3, 1。
排 序
希尔插入排序——特点
希尔排序实质上还是一种插入排序，其主要特点是： 每一趟以不同的增量进行排序。在每趟的插入排序中，记录 的关键字是和同一组中的前一个关键字进行比较，所以关键
排 序
3、排序的基本操作
排序的概念：就是要整理文件中的记录，使之按关键字 递增(或递减)次序排列起来。
排序过程的组成步骤：首先比较两个关键字的大小； 然 后将记录从一个位置移动到另一个位置。 对记录的关键字大小进行比较 将记录从一个位置移动到另一个位置 当待排序记录的关键字均不相同时，则排序结果是唯一 的，否则排序的结果不一定唯一。
3．将L.r[i] 插入到L.r[j+1]的位臵上。
具体方法：先将第一个数据看成是一个有序的子序列， 然后从第2个数据起逐个插入到这个有序的子序列中去， 相应的元素要移动。
排 序
例：
待排元素序列：[53] 第一次排序： 第二次排序： 第三次排序： 第四次排序： 第五次排序： [27 [27 [15 [15 [15 27 53] 36 27 27 27 36 36 53] 36 36 36 15 15 15 53] 53 42 69 69 69 69 69] 53 42 42 42 42 42 69] 对于有n个数 据元素的待排 序列，插入操 作要进行n-1 次
有序序列L.r[1..i-1]
L.r[i]
无序序列 L.r[i..n]
有序序列L.r[1..i]
无序序列 L.r[i+1..n]

几种常见的排序方法

几种常见的排序方法

⼏种常见的排序⽅法常见算法效率⽐较：⼀. 冒泡排序冒泡排序是是⼀种简单的排序算法。

它重复地遍历要排序的数列，⼀次⽐较两个元素，如果他们的顺序错误就把它们交换过来。

遍历数列的⼯作是重复的进⾏直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.冒泡排序算法的运作如下：（1）⽐较相邻的元素。

如果第⼀个⽐第⼆个⼤（升序），就交换他们两个（2）对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。

这步做完后，最后的元素还是最⼤的数（3）针对所有的元素重复以上的步骤，除了最后⼀个2.冒泡排序的分析：交换过程图⽰（第⼀次）那么我们需要进⾏n-1次冒泡过程，每次对应的⽐较次数如下图所⽰代码如下：def bubble_sort(alist):# j为每次遍历需要⽐较的次数，是逐渐减⼩的for j in range(len(alist)-1,0,-1):for i in range(j):if alist[i] > alist[i+1]:alist[i], alist[i+1] = alist[i+1],alist[i]li = [1,3, 4, 5, 2, 11, 6, 9, 15]bubble_sort(li)print(li)3. 时间复杂度算法的时间复杂度是指算法执⾏的过程中所需要的基本运算次数（1）最优时间复杂度：O（n）（表⽰遍历⼀次发现没有任何可以交换的元素，排序结束）（2）最坏时间复杂度：O(n2)（3）稳定性：稳定假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj 之前，⽽在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的常见算法的稳定性（要记住）、、、不是稳定的排序算法，⽽、、、、是稳定的排序算法。

⼆. 选择排序选择排序是⼀种简单直观的排序算法。

置换-选择排序 总结

置换-选择排序 总结

Prim 算法和Kruskal算法的执行过程以及时间复杂度等。 Dijkstra算法和Floyd算法在执行过程中，辅助数据结构的变化 （即迭代过程）。拓扑排序的过程和结果。AOE网求关键路径的 过程中各参量的变化，包括事件的最早发生事件和最迟发生时 间、活动的最早开始时间和最晚开始时间。有关图的算法设计 都可以通过修改图的遍历算法实现。 静态和动态查找的具体方法、平均查找长度的定义等。折 半查找重点。二叉排序树的算法设计。平衡二叉树的定义和平 衡调整的过程，判断平衡旋转的类型、进行平衡旋转等。 B—树与B+树的定义、特点、深度与关键码个数之间的关 系、B—树的插入和删除的操作过程等。 散列的基本思想、处理冲突的方法、平均查找长度的计算 等。主要考查应用各种散列函数以及各种处理冲突的方法构造 散列表的过程，以及计算查找成功情况下的平均比较次数。
[示例]利用败者树
FO 空 WA(4个记录) 空 FI 36,21,33,87,23,7,62,16, 54,43,29,… 空 21 21,23 21,23,33 21,23,33,36 21,23,33,36,62 21,23,33,36,62,87 21,23,33,36,62,87||7 … 36,21,33,87 36,23,33,87 36,7,33,87 36,7,62,87 16,7,62,87 1,62,16,54, 43,29,… 7,62,16,54, 43,29,… 62,16,54,43,29,… 16,54,43,29,… 54,43,29,… 43,29,… 29,… …
k阶哈夫曼树示例
长度分别为2，3，6，9，12，17，18，24的8 个初始归并段进行3路归并，求最佳归并树。 91 24 9
5 0 2 3
20 6

概述插入排序交换排序选择排序归并排序基数排序外部排序小结

概述插入排序交换排序选择排序归并排序基数排序外部排序小结

Type getKey ( ) { return key; } //提取关键字 void setKey ( const Type x ) { key = x; } //修改 Element<Type> & operator = //赋值 ( Element<Type> & x ) { this = x; } int operator == ( Type & x ) //判this == x { return ! ( this->key >x || x < this->key ); } int operator != ( Type & x ) //判this != x { return this->key < x || x < this->key ; } int operator <= ( Type & x ) //判this x { return ! (this->key > x ); } int operator >= ( Type & x ) //判this x { return ! (this->key < x ); } int operator < ( Type & x ) //判this < x { return this->key > x; }
KCN i n(n 1) / 2 n / 2,
2 i 1 n 1
RMN (i 2) (n 4)(n 1) / 2 n / 2
2 i 1
n 1


若待排序对象序列中出现各种可能排列的概 率相同，则可取上述最好情况和最坏情况的 平均情况。在平均情况下的关键字比较次数 和对象移动次数约为 n2/4。因此，直接插入 排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。

《数据结构排序》PPT课件

《数据结构排序》PPT课件

讨论：若记录是链表结构，用直接插入排序行否？折半插入 排序呢？
答：直接插入不仅可行，而且还无需移动元素，时间效率更 高！但链表无法“折半”！
折半插入排序的改进——2-路插入排序见教材P267。 （1）基本思想： P267 （2）举 例：P268 图10.2 （3）算法分析：移动记录的次数约为n2/8
13 20 39 39 42 70 85
i=8
0
1
2
3
4
5
6
7
8
Hj
折半插入排序的算法分析 • 折半查找比顺序查找快，所以折半插入排序
就平均性能来说比直接插入排序要快。
• 在插入第 i 个对象时，需要经过 log2i +1
次关键码比较，才能确定它应插入的位置。 • 折半插入排序是一个稳定的排序方法。
for ( j=i-1；j>=high+1；--j) L.r [j+1] = L.r [j]；// 记录
后移
L.r [high+1] = L.r [0]；
// 插入
} // for
} // BInsertSort
初始
30 13 70 85 39 42 6 20
012345678
i=2 13
30
13
数逐渐变多，由于前面工作的基础，大多数对象已基本有 序，所以排序速度仍然很快。
时间效率： O(n1.25）～O（1.6n1.25）——经验公式
空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：不稳定——因为49*排序后却到了49的前面
希尔排序算法（主程序）
参见教材P272
void ShellSort(SqList &L，int dlta[ ]，int t){

index排序


void BubbleSort(Elem R[ ], int n)
{ i = n; // i 指示无序序列中最后一个记录的位置 while (i >1)
{ lastExchangeIndex = 1; for (j = 1; j < i; j++) if (A[j+1] < A[j]) { Swap(A[j],A[j+1]); lastExchangeIndex = j; } i = lastExchangeIndex;
10.3 交换排序
交换排序的基本思想是：两两比较待排序记录的关键 码，如果发生逆序（即排列顺序与排序后的次序正好 相反），则交换之，直到所有记录都排好序为止。
交换排序的主要算法有：
1) 冒泡排序 2) 快速排序
1) 冒泡排序
基本思路：每趟不断将记录两两比较，并按“前小后大” （或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素；一旦下趟没有交换发 生，还可以提前结束排序。 前提：顺序存储结构
1
2
21
08
25
16
3 49
21
4
25*
25*
16
49
08
25
( 08 ，16 ） Low=high=3，本趟停止，将 支点定位并返回位置信息
21
（ 25* ，
*
49， 25 ）
25 跑到了前面，不稳定！
编程说明： ①每一趟子表的形成是采用从两头向中间交替式逼近法； ②由于每趟中对各子表的操作都相似，主程序可采用递归算法。
例：关键字序列 T=(21，25，49，25*，16，08），请写出 冒泡排序的具体实现过程。

数据结构使用C语言版朱战立丛书版本排序


{ span = d[m];
//取本次的增量值
for<k = 0; k < span; k++> //共span个小组
{
//组内是直接插入排序,区别是每次不是增1而是增
span
for<i = k; i < n-span; i = i+span>
{ temp = a[i+span];
j = i;
while<j > -1 && temp.key < a[j].key>
优点：实现简单
缺点：每趟只能确定一个元素,表长为n时需要n-1趟
算法如下：
void SelectSort<DataType a[], int n>
{
int i, j, small;
DataType temp;
for<i = 0; i < n-1; i++>
{ small = i;
//设第i个数据元素关键字
(a)初始最大堆 40
32
9
5
10
40 32 9 5 10 50 76 88 (d)交换顶点50后 9
5
76
50
40
5
10
9
32
76 50 40 5 10 9 32 88 (b)交换顶点88后 32
10
9
5
32 10 9 5 40 50 76 88 (e)交换顶点40后
5
9 5 10 32 40 50 76 88
{ a[j+span] = a[j];
j = j-span;
65

交替排序法名词解释

交替排序法名词解释1.引言1.1 概述交替排序法是一种常见的排序算法，也被称为奇偶排序法或定向冒泡排序法。

它是一种简单直观的排序方法，通过比较和交换相邻元素的位置来达到排序的目的。

这种排序算法最早是为并行计算机设计的，利用了并行计算的特性以提高排序的效率。

在并行计算中，数据被划分为多个子序列，并行处理这些子序列，最后再合并得到有序的结果。

交替排序法的基本思想是：将待排序的序列分为奇数位置和偶数位置两个子序列，然后分别对这两个子序列进行排序。

首先比较并交换奇数位置相邻的元素，然后比较并交换偶数位置相邻的元素，重复以上步骤，直到序列完全有序。

可以看出，每一轮排序都会有一个元素被放置在正确的位置上，因此需要多次迭代来完成排序过程。

交替排序法的优势在于其简单易懂的算法逻辑和相对较好的性能。

它的时间复杂度为O(n^2)，与冒泡排序类似，但交替排序法的并行化处理可以提高它的实际效率。

此外，交替排序法的算法思想也可以应用于其他排序算法的优化，例如快速排序和归并排序等。

总的来说，交替排序法是一种简单而实用的排序算法，它在并行计算和算法优化中有着重要的应用价值。

在接下来的章节中，我们将详细介绍交替排序法的定义和应用场景，以及总结其优点和展望其发展前景。

1.2 文章结构本文将围绕交替排序法展开论述，并且按照以下结构进行组织：引言部分将首先给出对交替排序法的概述，简要介绍该排序方法的基本原理和特点。

接着将介绍本文的整体结构，以引导读者对文章内容有一个清晰的了解。

最后，在引言部分说明文章的目的，即通过对交替排序法的深入探讨，分析其应用场景、优点以及未来的发展前景。

正文部分将分为两个主要部分，分别是交替排序法的定义和交替排序法的应用场景。

在第一个主要部分中，会详细阐释交替排序法的定义。

首先会从算法的基本原理出发，介绍排序的过程和步骤。

然后会对交替排序法的时间复杂度和空间复杂度进行分析，以评估其在实际应用中的效率。

此外，还将深入讨论交替排序法在处理不同规模和类型的数据时的优势和局限性。

排序算法


五、基数排序(Radix Sort)
基数排序和通常的排序算法并不走同样的路线。 它是一种比较新颖的算法，但是它只能用于整数 的排序，如果我们要把同样的办法运用到浮点数 上，我们必须了解浮点数的存储格式，并通过特 殊的方式将浮点数映射到整数上，然后再映射回 去，这是非常麻烦的事情，因此，它的使用同样 也不多。而且，最重要的是，这样算法也需要较 多的存储空间。 原理：将数字按位数划分出n个关键字，每次针对 一个关键字进行排序，然后针对排序后的序列进 行下一个关键字的排序，循环至所有关键字都使 用过则排序完成。
三、选择排序
3.1直接选择排序(Selection Sort)
1、基本思想： 每一趟从待排序的数据元素中选出最小（或最大） 的一个元素，顺序放在已排好序的数列的最后，直到全部 待排序的数据元素排完。 2、排序过程：【参见动画演示】 【示例】： 初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49］ 第二趟排序后 13 27 ［65 97 76 49 38 49］ 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97
四、归并排序(Merge Sort)
算法基本思路 设两个有序的子文件(相当于输入堆)放在同 一向量中相邻的位置上：R[low..m]， R[m+1..high]，先将它们合并到一个局部的 暂存向量R1(相当于输出堆)中，待合并完成 后将R1复制回R[low..high]中。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

23 23
i
13
35
6
19
j
50
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （4）找到比轴值小的数，则与轴值交换 if(i<j) {R[i]=R[j];i++;}

R[0]
23 19
i
13
35
6
**
j
50
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （4）找到比轴值小的数，则与轴值交换 if(i<j) {R[i]=R[j];i++;}

[ r1 … … ri-1 ] ri [ ri+1 … … rn ]
均≤ri
轴值
均≥ri
（2）求解子问题：分别对两个子序列进行轴值划分， 直到划分区域里只有一个元素 关键问题：如何选择轴值？如何实现划分？
7.3.2 快速排序
轴值选择不同，划分的效率不同，排序的速度也不同。 如何选择轴值？ （1）常用、最简单的做法：选当前序列第一个 （2）随机选取 （3）选择序列的中位数（最好）
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （6）找到后，与轴值交换 if(i<j) {R[j]=R[i];j−−;}

R[0]
23 19
13
**
i
6
35
j
50
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （6）找到后，与轴值交换 if(i<j) {R[j]=R[i];j−−;}

7.3.1 冒泡排序
基本思想： 将序列划分成有序区（左边）和无序区（右边） 初始时，有序区为空，无序区为序列全部
r1 r2 …ri-1 ri ri+1 … rn
有序区 无序区
7.3.1 冒泡排序
基本思想： 将序列划分成有序区（左边）和无序区（右边） 初始时，有序区为空，无序区为序列全部 每一次“冒泡”相邻元素依次两两比较，将较小/大者 交换到前面，成为有序区的第一个元素

7.3.1 冒泡排序

冒泡排序的具体实现
排序中各元素不断接近自己的位置，如果一趟下来没有交换， 则序列已经有序，可设一个标志flag判断，提前结束
void BubbleSort(list R,int n) {//上升法冒泡排序 int i,j,flag; for(i=1;i<=n−1;i++) { //做n−1趟扫描 flag=0; //置未交换标志 for(j=n;j>=i+1;j−−) //从下向上扫描 if(R[j].key<R[j−1].key) { //交换记录 flag=1; R[0]=R[j];R[j]=R[j−1];R[j−1]=R[0]; //交换，R[0]作辅助量 } if(!flag) break; //本趟未交换过，排序结束 } }
13
i
35
6
**
j
50
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （4）找到比轴值小的数，则与轴值交换 （5）换i行动，依次向后搜索一个比轴值大的数 while(R[i].key<=R[0].key && i<j) i++;

R[0]
23 19
13
35
i
6
**
j
50
上节回顾
（1）基本概念： 稳定性：检测相同的元素在排序是否保持先后顺序 内排序和外排序 有序区增长法和有序度增长法 （2）直接插入排序 思想：每次将无序区的第一个元素插入到有序区合适 的位置 时间复杂度：与数据分布有关

最好（基本有序）：O(n) 最坏（逆序）：O(n2) 平均：O(n2)

R[0]
23 19
13
i
35
6
**
j
50
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （4）找到比轴值小的数，则与轴值交换 （5）换i行动，依次向后搜索一个比轴值大的数 while(R[i].key<=R[0].key && i<j) i++;

R[0]
23 19
7.3.1 冒泡排序
（1）时间复杂度分析： 最好情况：序列正序，通过flag标志，序列只需要两两 比较一趟即结束，共需要比较n-1次，即 T(n)=n-1=O(n) 最坏情况：序列反序，每一趟不止要完成所有有序区 元素的两两比较，而且每比较一次要交换一次，因此， 对第i趟冒泡而言，最坏情况下要比较i-1次和交换i-1次， 即共需要操作的语句数为： T(n)=∑2(i-1)=O(n2) 平均情况：O(n2)
7.3.2 快速排序
int Partition(list R,int p,int q) { 如何实现划分？交替扫描 //对无序区R[p]到R[q]划分，返回划分后基准的位置 int i,j; i=p; j=q; R[0]=R[i]; //R[0]作辅助量，存基准(无序区第一个记录) while(i<j) { while(R[j].key>=R[0].key && i<j) j−−; //从右向左扫描 if(i<j) {R[i]=R[j];i++;} //交换R[i]和R[j] while(R[i].key<=R[0].key && i<j) i++; //从左向右扫描 if(i<j) {R[j]=R[i];j−−;} //交换R[i]和R[j] } R[i]=R[0]; //将基准移到最后位置 return i; }
r1 ≤ r2 ≤ … ≤ ri-1 ri ri+1 … rn-1 rn
有序区 无序区
7.3.1 冒泡排序
基本思想： 将序列划分成有序区（左边）和无序区（右边） 初始时，有序区为空，无序区为序列全部 每一次“冒泡”相邻元素依次两两比较，将较小/大者 交换到前面，成为有序区的第一个元素
r1 ≤ r2 ≤ … ≤ ri-1 ≤ ri ri+1 … rn-1 rn
课堂练习
1、用直接插入排序对下面4个序列进行递增排序，元素 比较次数最少的是（ ）。 A. 94,32,40,90,80,46,21,69 B. 32,40,21,46,69,94,90,80 C. 21,32,46,40,80,69,90,94 D. 90,69,80,46,21,32,94,40 答案：C。A选项总共比较24次；B选项总共比较17次； C选项总共比较9次；D选项总共25次
上升法和下沉法 上升法，每次扫描从序列尾部向头部扫，每次比较相 邻的元素，将较小(升序)/较大(降序)的元素交换到前 面，如此，有序的“气泡”就会从尾部往上“冒”

下沉法，每次扫描从序列头部向尾部扫，每次比较相 邻的元素，将较大(升序)/较小(降序)的元素交换到后 面，如此，有序的“气泡”就会从头部向下“沉” 本章主要讨论上升法
7.3.2 快速排序

对一个序列R[p,q]进行划分Partition
23
13
35
6
19
50
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （1）设下标i从头指向尾，下标j从尾指向头 i=p; j=q;

23
i
13
35
6
19
50
28
j
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （1）设下标i从头指向尾，下标j从尾指向头 （2）选择第1个数作为轴值
有序区 无序区
7.3.1 冒泡排序
第1次循环：
a[0] a[1] a[2] a[3] a[4] a[5]
45 36 4 45 36 4 45 36 4 45 36 4 45 4 36
5次比较
4 45 36
13 25
43
13 25
43
13 25
43
13 25
43
13 25
43
13 25
43
7.3.1 冒泡排序

23 23
i
13
35
6
19
50
28
j
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （1）设下标i从头指向尾，下标j从尾指向头 （2）选择第1个数作为轴值 （3）从j开始向前行动，寻找比轴值小的值 R[0] while(R[j].key>=R[0].key && i<j) j−−;
第21讲 排序 ——交换排序和选择排序
7.3 交换排序
基本思想： 每次比较两个待排序的记录，如果关键字的次序与排 序要求相反时就交换两者的位置，直到没有反序的记录 为止。 特点： 键值较大的记录向排序表的一端移动，键值较小的记 录向另一端移动。 经典算法： （1）冒泡排序 （2）快速排序
7.3.1 冒泡排序

23 23

13
35
6
19
50
j
28
7.3.2 快速排序
对一个序列R[p,q]进行划分Partition （1）设下标i从头指向尾，下标j从尾指向头 （2）选择第1个数作为轴值 （3）从j开始向前行动，寻找比轴值小的值 R[0] while(R[j].key>=R[0].key && i<j) j−−;