10.数据结构探析.ppt

10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较;10.1 概述;4. 什么叫内部排序？什么叫外部排序？ ;排序的定义： 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn };注：大多数排序算法都是针对顺序表结构的(便于直接移动元素);内部排序的方法;7. 内部排序的算法有哪些？;10.2 插入排序;有序序列R[1..i-1];实现“一趟插入排序”可分三步进行：;1) 直接插入排序;void D-InsertSort(datatype R[ ],int n) /*待排序的n个元素放在数组R中，用直接插入法进行排序*/ { for ( i=2; i=n; i++) /*i控制第i-1次插入,最多进行n-1次插入*/ if (R[i].keyR[i-1].key) /*小于时,需将R[i]插入有序表*/ { R[0]=R[i]; /*为统一算法设置监视哨*/ for ( j=i-1; R[0].keyR[j].key;j--) R[j+1]=R[j]; /*元素后移*/ R[j+1]= R[0]; /*将放在R[0]中的第i个元素插入到有序表中*/ } };例2：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。;直接插入排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。 优点：算法简单，容易实现。当n很小时，是一种很好的排序方法。 缺点：n很大时，不宜采用。;2） 折半插入排序;[5;3) 2-路插入排序;4）表插入排序;1;int LinkInsertSort ( staticlinklisType list ) { list.v[0].Key = MaxInt; list.v[0]. Link = 1; list.v[1].Link = 0; //形成循环链表 for ( int i = 2; i = list.length; i++ ) { int current = list.v[0]. Link; //current=当前记录指针 int pre = 0; //pre=当前记录current的前驱指针 while ( list.v[current]. Key = list.v[i]. Key) { pre = current; // current指针准备后移, pre跟上； current = list.v[current]. Link; //找插入位置(即p=p-link) } list.v[i]. Link = current; //新记录v[i]找到合适序位开始插入 list.v[pre]. Link = i; //在pre与current之间链入 } };表插入排序算法分析：;5）希尔（shell）排序（又称缩小增量排序）;将记录序列按增量d分成若干子序列，分别对每个子序列进行直接插入排序。;38;void ShellSort(SqList L，int dlta[ ]，int t){ //按增量序列dlta[0…t-1]对顺序表L作Shell排序 for(k=0；kt；++k) ShellSort(L，dlta[k])； //增量为dlta[k]的一趟插入排序 } // ShellSort;void ShellInsert(SqList L，int dk) { for (i=dk+1;i=L.length;++i) if ( r[i].key r[i-dk].key ) { r[0]=r[i]； for(j=i-dk; j0 (r[0].keyr[j].key); j=j-dk) r[j+dk]=r[j]； r[j+dk]=r[0]； } };附：希尔排序算法分析;10.3 快速排序（交换