排序查找 概述 插入排序 交换排序 选择排序 归并排序 主讲：朱佳 博士.

Presentation on theme: "排序查找 概述 插入排序 交换排序 选择排序 归并排序 主讲：朱佳 博士."— Presentation transcript:

1 排序查找 概述 插入排序 交换排序 选择排序 归并排序 主讲：朱佳 博士

2 简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来。
什么是排序(Sorting)？ 简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来。 排序是计算机中经常遇到的操作。 表述

3 数据表(Data List) 待排序的数据对象的有限集合。 关键码(Key) 作为排序依据的数据对象中的属性域。
排序的几个基本概念 数据表(Data List) 待排序的数据对象的有限集合。 关键码(Key) 作为排序依据的数据对象中的属性域。 主关键码 不同的数据对象若关键码互不相同，则这种关键码称为主关键码。 排序的确切定义 使一组任意排列的对象变成一组按关键码线性有序的对象。

4 内排序与外排序 区分标准：排序过程是否全部在内存进行。
排序的几个基本概念 排序算法的稳定性 判断标准：关键码相同的数据对象在排序过程中是否保持前后次序不变。如 2, 2*,1，排序后若为1, 2*, 2 则该排序方法是不稳定的。 内排序与外排序 区分标准：排序过程是否全部在内存进行。 排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量 因为2 从 2*的前面编导了后面

5 const int DefaultSize = 100;
静态排序中的数据表的类定义 const int DefaultSize = 100; Template <class Type> class datalist; Template<class Type>class Element{ friend class datalist<Type>; private: Type key; field otherdata; } ; public: Type getKey( ) { return key;} void setKey(const Type x) {key=x;} Element<Type>&operator=(Element<Type>&x) {key=x->key;otherdata=x->otherdata;} 经典代码模版，get, set

6 Type operator == (Type &x) {return key==x->key;}
template<class Type>class datalist{ private: Element<type>*Vector; int MaxSize,CurrentSize; int Partition(const int low,const int high) public; datalist (int MaxSz = DefaultSize):MaxSize( MaxSz) { }; void Swap(Element <Type> &x, Element <Type> &y) {Element <Type> temp=x;x=y;y=temp;} void Sort(); } Partition 进行分片折半处理， swap， 元素交换常用函数， sort 具体算法，其实就是如何调用上面各种函数

7 基本原理，每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。
插入排序(Insert Sorting) 基本原理，每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。

8 分类原理，根据已经排好序的有序数据表中寻找插入位置的方法的不同而区分。
三种常见的插入排序 分类原理，根据已经排好序的有序数据表中寻找插入位置的方法的不同而区分。 直接插入排序(Insert Sort) 折半插入排序(Binary Insert Sort) 链表插入排序

9 直接插入排序(Insert Sort) 基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用v[i]的关键码与V[i-1], V[i-2],…的关键码顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。

10 i (0) (1) (2) (3) (4) (5) temp [21] 25 49 25* 16 08 25
直接插入排序举例 i (0) (1) (2) (3) (4) (5) temp [21] * 1 [ ] * 2 [ ] 25* * 3 [ * 49] 4 [ * 49] 5 [ * 49]

11 Template<class Type>void dataList<Type>::sort{
直接插入排序程序 Template<class Type>void dataList<Type>::sort{ Element<Type>temp;int j; for(int i=1;i<CurrentSize;i++){ //loop 1 temp=Vector[i]; //i 元素 j=i; for(int j=i;j>0;j--) //loop 2 if (temp<Vector[j-1]) Vector[j]=Vector[j-1]; else break; Vector[j]=temp; } 伪代码，如果发现后面位置的比前面的小，则互换，然后重新排

12 考虑关键码的比较次数和对象移动次数， 最好情况时两者分别为n-1与2(n-1)，最坏情况时两者分别为
直接插入排序的时间复杂度 考虑关键码的比较次数和对象移动次数， 最好情况时两者分别为n-1与2(n-1)，最坏情况时两者分别为 KCN= n-1 = n(n-1)/2 RMN= (1+2)+(2+2)+...+(n-1+2) = (n+4)(n-1)/2 Rmn 对象移动次数 kcn 比较次数

13 原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。
直接插入排序的稳定性 直接插入排序是一种稳定的排序方法。 原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。

14 折半插入排序(Binary Insert Sort)
基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用折半查找法寻找V[i]的插入位置移。

15 template <class Type> void datalist <Type> ::sort(){
折半插入排序程序 template <class Type> void datalist <Type> ::sort(){ int left, right; Element <Type> temp; for (int i=1;i<CurrentSize;i++){ left=0;right=i-1;temp=Vector[i]; while (left < =right) { int middle=(left+right)/2; if (temp <Vector[middle]) right=middle-1; else left=middle+1; for (int k=i-1;k>=left; k--) Vector[k+1]=Vector[k]; Vector[left] = temp; } 比较和前一段代码的不同

16 1. KCN 约为 n log 2 n，且与对象序列的初始排列无关
折半插入排序的时间复杂度 考虑关键码的比较次数和对象移动次数 1. KCN 约为 n log 2 n，且与对象序列的初始排列无关 当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况时要差。 2. RMN与直接插入排序相同。

17 原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。
折半插入排序的稳定性 折半插入排序是一种稳定的排序方法。 原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。

18 链表插入排序 基本思想：用链表来表示已排序的数据对象，当插入V[i]时，依次在链表中检查，找到V[i]应插入的位置，并修改相应的链接指针。如此重复，直到V[n]也插入到链表中排好序为止。 链表插入排序

19 template <class Type> class staticlinklist{
链表插入排序的数据结构 template <class Type> class staticlinklist{ template<class Type>class Element{ private: Type key; int link; public: Type getKey() {return key;} void setKey(const Type x) {key=x;} int getLink(){return link;} void setLink(const int ptr){link=ptr;} } 关键函数，getKey, getLink

20 template<class Type>class staticlinklist{ private:
链表插入排序的数据结构 template<class Type>class staticlinklist{ private: Element <Type> * Vector; int MaxSize, CurrentSize; public: staticlinklist(int MaxSz=DefaultSize): MaxSize(MaxSize),CurrentSize(0){}; }

21 i index (0) (1) (2) (3) (4) (5) (6) key MaxNum 21 25 49 25* 16 8
链表插入排序示例 i index (0) (1) (2) (3) (4) (5) (6) key MaxNum * link 2 link 3 link 4 link 5 link 6 link 重点,4,3指针互换， 0作为移动用，拿来指向当前最大， 红色是指针位置

22 template <class Type> int staticlinklist <Type>:: Sort(){
链表插入排序的算法 template <class Type> int staticlinklist <Type>:: Sort(){ Vector[0].key=MaxNum; Vector[0].link=1; Vector[1].link=0; for(int i=2; i<=CurrentSize; i++){ int current =Vector[0].link; int pre = 0; while (Vector[current].key <= Vector[i].key) { pre=i; current=Vector[current].link;} Vector[i].link=current; Vector[pre].link=i; }

23 链表插入排序方法是稳定的。 考虑关键码的比较次数和对象移动次数 1. KCN 最小为n-1，最大为 n (n-1)/2
链表插入排序的时间复杂度 考虑关键码的比较次数和对象移动次数 1. KCN 最小为n-1，最大为 n (n-1)/2 2. 对象移动次数为0 。 链表插入排序方法是稳定的。

24 交换排序 基本原理，两两比较待排序的对象的关键码，如果发生逆序，则交换之，直到全部对象都排好序为止。 两种常见的交换排序 起泡排序(Bubble Sort) 快速排序(Quick Sort)

25 起泡排序的基本过程 假设待排序的n个对象的序列为V[0],V[1],..., V[n-1]，起始时排序范围是从V[0]到V[n-1]
在整个排序过程中，最多执行(n-1)遍。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的比较。

26 起泡排序示例 i (0) (1) (2) (3) (4) (5) * * 16 * * 49 *

27 Template<class Type>void datalist<Type>::sort(){
起泡排序的算法 Template<class Type>void datalist<Type>::sort(){ int pass=1;int exchange=1; while (pass<CurrentSize&&exchange){ exchange=0; for (int j=CurrentSize-1;j>=pass;j--) if (Vector[j-1]>Vector[j]){ swap(Vector[j-1],vector[j]) exchange=1; } pass++;

28 起泡排序方法是稳定的。 考虑关键码的比较次数和对象移动次数 1. KCN 为 n * (n-1) /2
起泡排序的时间复杂度 考虑关键码的比较次数和对象移动次数 1. KCN 为 n * (n-1) /2 2. RMN 为 3/2 * n* (n-1) 。 起泡排序方法是稳定的。

29 快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。
快速排序的基本过程 快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。 其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。然后分别对这两个子序列重复实施上述方法.

30 i (0) (1) (2) (3) (4) (5) pivot（基准) 21 25 49 25* 16 08 21
快速排序示例 i (0) (1) (2) (3) (4) (5) pivot（基准) * * (左),25*(右) * (右) * * 再度分割

31 template <class Type> void QuickSort(
快速排序的递归算法 template <class Type> void QuickSort( const int left, const int right) { if (left<right) { int pivotpos = Partition (left, right); if (left<pivotpos-1) QuickSort(list,left,pivotpos-1); if (pivotpos+1>right) QuickSort(list,pivotpos+1,right); } Partition函数划分，同时做交换。

32 template <class Type> int Partition(
快速排序的递归算法 template <class Type> int Partition( const int low, const int high){ int pivotpos = low; Element <Type> pivot = Vector[low]; for (int i=low+1; i<=high; i++) if(Vector[i]<pivot){ pivotpos++; if (pivotpos!i)Swap(Vector[pivotpos], Vector[i]); } Swap(Vector[low], Vector[pivotpos]); return pivotpos;

33 1. 平均计算时间为O(n*log2n) ，实验表明，快速排序是我们所讨论过的内排序中，平均计算时间最快。
快速排序的时间复杂度 考虑关键码的比较次数和对象移动次数 1. 平均计算时间为O(n*log2n) ，实验表明，快速排序是我们所讨论过的内排序中，平均计算时间最快。 2. 最坏情况总的关键码比较次数为 n* (n-1) /2，例如，对一个已经排序的序列进行快速排序。 快速排序是不稳定的排序方法。 如序列2, 3, 3*, 1 根据不同的基准，情况不一样

34 基本原理，将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。
选择排序 基本原理，将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。 一组易到另一组

35 常见的选择排序 直接选择排序 锦标赛排序

36 在一组对象V[i]到V[n-1]中选择具有最小关键码的对象 若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。
直接选择排序的基本过程 在一组对象V[i]到V[n-1]中选择具有最小关键码的对象 若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。 删除具有最小关键码的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。

37 直接选择排序示例 i (0) (1) (2) (3) (4) (5) k [ * ] [ * ] [ * ] [25* ] * [ ] * [49]

38 for (int j=i+1; j<CurrentSize; j++)
直接选择排序的算法 template <class Type> void datalist <Type> :: sort() { for(int i=0;i<CurrentSize-1;i++){ int k=i; for (int j=i+1; j<CurrentSize; j++) if (Vector[j]<Vector[k]) k=j; if (k!=i) Swap(Vector[i], Vector[k]); }

39 1. KCN与对象的初始排列无关，总为 n* (n-1) /2
直接选择排序的时间复杂度 考虑关键码的比较次数和对象移动次数 1. KCN与对象的初始排列无关，总为 n* (n-1) /2 2. RMN与对象的初始排列有关，最少为0，最大为3(n-1) 。如：n-1,0,1,2,..., n-2 直接选择排序是不稳定的排序方法。 对象的初始排列有关， 所以不稳定

40 在一组对象V[i]到V[n-1]中选择具有最小关键码的对象 若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。
锦标赛排序的基本过程 在一组对象V[i]到V[n-1]中选择具有最小关键码的对象 若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。 删除具有最小关键码的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。 相当于淘汰赛，着重看

41 锦标赛排序示例 i (0) (1) (2) (3) (4) (5) (6) * ? * 08 * 16 重点观看，实际是和树状结构

42 template <class Type> class DataNode{ public:
锦标赛排序的算法 template <class Type> class DataNode{ public: Type data; int index; int active; } template <class Type> void TournamentSort( Type a[ ], int n){ DataNode <Type> *tree; DataNode <Type> item; int bottonRowSize = PowerOfTwo(n); int TreeSize = 2* bottomRowSize –1; int loadindex = bottomRowSize –1; tree = new DataNode <Type> [TreeSize]; 用树结构，回去自己学习

43 int j=0; for (int i= loadindex; i<TreeSize; i++) { tree[i].index = i; if (j<n) { tree[i].active =1 ; tree[i].data = a[j++];} else tree[i].active = 0; } i = loadindex; while(i){ j=i; while(j<2*i) { if (!tree[j+1].active || tree[j].data < tree[j+1].data) tree[(j-1)/2] = tree[j]; else tree[(j-1)/2] = tree[j+1]; j+=2; } i=(i-1)/2;

44 for (i=0; i<n-1; i++) { a[i] = tree[0].data;
tree[tree[0].index].active = 0; UpdateTree(tree,tree[0].index); } a[n-1] = tree[0].data; template <class Type> void UpdateTree (DataNode <Type> *tree, int i) { if ( i %2 == 0) tree[(i-1)/2] = tree[i-1]; else tree[(i-1)/2] = tree[i+1]; i=(i-1)/2; 找到后更新树，

45 while (i) { if ( i % 2 == 0) j= i-1; else j=i+1; if (! tree[i].active || ! tree[j].active) if ( tree[i].active) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; else if ( tree[i].data < tree[j].data) tree[(i-1)/2] = tree[i]; i = (i-1)/2; }

46 锦标赛排序是稳定的排序方法。 考虑关键码的比较次数和对象移动次数 1. 比较次数为 O(log2n) 2. 对象的移动次数不超过比较次数。
锦标赛排序的时间复杂度 考虑关键码的比较次数和对象移动次数 1. 比较次数为 O(log2n) 2. 对象的移动次数不超过比较次数。 所以总的时间复杂度为O(n log2n) 锦标赛排序是稳定的排序方法。

47 基本原理，通过对两个或两个以上的有序结点序列的合并来实现排序。
归并排序 基本原理，通过对两个或两个以上的有序结点序列的合并来实现排序。 如果是对两个已经排好序的序列的合并来实现排序，称为“两路归并”(2-way merging) 。

48 两路归并的基本思想 设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。设表C是归并后的新有序表，变量k是它的当前指针。i和j对A和B遍历时，依次将关键码小的对象放到C中，当A或B遍历结束时，将另一个表的剩余部分照抄到新表中。

49 initList 08 21 25 25* 49 62 72 93 16 37 54 归并后为 mergedList
两路归并的示例 initList * 归并后为 mergedList *

50 template <class Type> void merge(
两路归并的算法 template <class Type> void merge( datalist <Type> &mergedList, const int left, const int mid, const int right) { int i=left; j=mid+1; k=left; while(i<=m && j<=n) if (Vector[i]<Vector[j]) {mergedList.Vector[k]=Vector[i];i++;k++;} else {mergedList.Vector[k]=Vector[j];j++;k++;} if (I<=mid) for(int n1=k,n2=I;n2<=mid;n1++;n2++) mergedList.vector[n1]=vector[n2]; }

51 迭代的归并排序 假设初始的对象序列有n个对象，我们首先把它看成是n个长度为1的有序子序列，先做两两归并，得到n/2个长度为2的归并项（如果n为奇数，则最后一个有序子序列的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。

52 归并排序的过程 重点

53 template <class Type> void MergePass(
算法 template <class Type> void MergePass( datalist <Type> &mergedList, const int len) { int i=0; while(i+2*len <= CurrentSize-1) { merge(mergedList,i, i+len-1, i+2*len-1); i+=2*len; } if (I+len<=CurrentSize-1) else for(int j=i;j<=CurrentSize-1;j++) mergedlist.Vector[j]=Vector[j];

54 迭代的归并排序是稳定的排序方法。 MergeSort调用 log2n 次，总的时间复杂度为O(n log2n)
迭代的归并排序的时间复杂度 MergeSort调用 log2n 次，总的时间复杂度为O(n log2n) 空间开销为需要一个与原待排序对象数组同样大小的辅助数组。 迭代的归并排序是稳定的排序方法。

55 总时间限制: 1000ms 内存限制: 65536kB 描述 在一个非降序列中，查找与给定值最接近的元素。
输入 第一行包含一个整数n，为非降序列长度。1 <= n <= 。 第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。 第三行包含一个整数m，为要询问的给定值个数。1 <= m <= 10000。 接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。 输出 m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。 样例输入 样例输出 8 5 练习重点，查找后做运算,已排好序，基础二分查找， 找到x元素相近左右，然后比较

56 #include<cstdio> #include<cmath> #include<iostream>
using namespace std; #define N int n,m,x,l,r,mid; long long a[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); while(m--){ scanf("%d",&x); l=0,r=n+1; if(x<=a[1]) {printf("%d\n",a[1]);continue;} if(x>=a[n]) {printf("%d\n",a[n]);continue;} while(l<r){ mid=(l+r)>>1; if(a[mid]<x) l=mid; else if(a[mid]>x) r=mid; else {l=mid;break;} if(l==r-1&&a[l]<x&&a[r]>x) break; } //find the number if(abs(a[l]-x)<=abs(a[r]-x)) //compare printf("%d\n",a[l]); else printf("%d\n",a[r]); } return 0; } 在数组里比较，折半对比，需要移位的数字 >> 移位的次数 >>1相当于除以2

57 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15676    Accepted Submission(s): 4032 Problem Description 输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。 你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。 Input 输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于5000。   输入数据保证：分割得到的非负整数不会大于 ；输入数据不可能全由‘5’组成。 Output 对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。 Sample Input Sample Output 字符串转数字

58 #include<cstring> #include<algorithm> using namespace std;
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main(){ char s[5005]; int a[5005]; int i,len,k,n; while(scanf("%s",s)!=EOF) { n=0; k=0; len=strlen(s); s[len]='5'; i=0; while(s[i++]=='5'); //跳过前缀5,防止多输出0 for(i--;i<=len;++i) { if(i>0&&s[i]=='5'&&s[i-1]=='5') //忽略连续的5，防止多输出0 continue; if(s[i]!='5') k=k*10+s[i]-'0'; else //遇到5就增加一个数 { a[n++]=k; k=0; } } sort(a,a+n); printf("%d",a[0]); for(i=1;i<n;++i) printf(" %d",a[i]); printf("\n"); } return 0;} sort(a,a+n); 而是从a开始往后一共是n个的数据。数组当中，其内存的存储位置从0开始的，所以n个数据会是从0开始到 n-1 结束。

59 排序就是将一组杂乱无章的数据按一定的规律排列起来，是常规操作。
总结 排序就是将一组杂乱无章的数据按一定的规律排列起来，是常规操作。 排序是计算机中经常遇到的操作。 插入，交换，选择，归并排序。