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

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

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

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

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

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 具体算法，其实就是如何调用上面各种函数

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

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

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

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

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; } 伪代码，如果发现后面位置的比前面的小，则互换，然后重新排

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

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

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

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; } 比较和前一段代码的不同

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

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

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

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

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){}; }

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 21 25 49 25* 16 8 link 1 0 0 0 0 0 0 2 link 1 2 0 0 0 0 0 3 link 1 2 3 0 0 0 0 4 link 1 2 4 3 0 0 0 5 link 5 1 2 4 3 0 0 6 link 6 5 1 2 4 3 0 重点,4,3指针互换， 0作为移动用，拿来指向当前最大， 红色是指针位置

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; }

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

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

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

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

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++;

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

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

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

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函数划分，同时做交换。

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;

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

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

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

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

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

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]); }

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 直接选择排序是不稳定的排序方法。 对象的初始排列有关， 所以不稳定

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

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

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]; 用树结构，回去自己学习

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;

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; 找到后更新树，

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; }

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

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

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

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

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]; }

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

归并排序的过程 重点

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];

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

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

#include<cstdio> #include<cmath> #include<iostream> using namespace std; #define N 100005 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

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。   输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。   Output 对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。 Sample Input 0051231232050775 Sample Output 0 77 12312320 字符串转数字

#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 结束。

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