插入排序交换排序选择排序归并排序基数排序3.ppt

插入排序 交换排序 选择排序 归并排序 基数排序 排序问题 定义 给定一组纪录 R1,R2,········,Rn其关键码分别为k1,k2,········,kn,将这组纪录重新排成顺序为Rp1,Rp2,········,Rpn的一个序列，使其关键码具有不减顺序kp1 ≤ kp2 ≤ ········ ≤ kpn. 不同的纪录可以具有相同的关键码。 稳定的排序：关键码相同的纪录在排序前和排序后的次序保持不变。 约定：关键码用整数代替 排序的基本操作 比较 比较关键码的大小。 移动 将纪录从一个位置移到另一个位置。 排序方法的分类 内部排序 不用外设 外部排序 原始记录 #define MaxDataSize 100 templateclass T struct Data { T element; int key; DataT operator=(const DataT a); int operator(const DataT a,const DataT b) {return a.keyb.key;} istream operator(istream, const DataT); }; template class T class Array //array.h 通用数组 抽象数组类型 { T *alist; int size; public: Array(int s=50)； //构造函数 Array(const ArrayTX); //拷贝构造函数 ~Array( ){delete[ ] element;} //析构函数 ArrayToperator=(const ArrayTX); T operator[ ](int i)； operator T*( )const; int ArraySize( )const; //取数组长 void Resize(int sz); //数组长重定义 friend ostream operator(ostream, const ArrayT); }； 待排序原始记录数组的输入 templateclass T void InputDataList(ArrayTL,int n) for(int i=1;in;i++) { cout“Please enter L[”i“]:”; cinL[i];} ArrayDataT L; InputDataList(L,50); 一、插入排序 逐个将纪录插入到已排好次序的有序表中 得到一个新的有序表。 1.直接插入排序 49 38 65 97 76 13 27 49 49 49 38 49 65 49 65 97 38 49 65 76 97 13 38 49 65 76 97 27 38 49 65 76 97 13 27 38 49 49 65 76 97 2.折半插入排序 用折半法比较查找到适当的位置再插入 减少比较次数 不减少移动次数 最坏时间复杂度 O(nlogn)+O(n2/2)=O(n2) 3. 2路插入排序 49 38 65 97 76 13 27 49 49 49 38 49 65 38 49 65 97 38 49 65 76 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 4. 表插入排序 静态链表 不移动 5. 链表插入排序 动态链表 不移动 6.希尔排序Shell Sort 缩小增量排序Diminishing Increment Sort 基本思想：先将待排纪录分成若干子列分别用直 接插入法排序，再对全体纪录用直接插