会计学数据结构课程(kèchéng)的内容9.1概述9.2插入排序9.3交换(jiāohuàn)排序9.4选择排序9.5归并排序9.6基数排序9.1概述(ɡàishù)4.什么(shénme)叫内部排序？什么(shénme)叫外部排序？注：大多数排序算法都是针对(zhēnduì)顺序表结构的(便于直接移动元素)7.内部(nèibù)排序的算法有哪些？1)直接(zhíjiē)插入排序直接(zhíjiē)插入排序算法例2：关键字序列T=（21，25，49，25*，16，08），请写出直接插入排序的具体(jùtǐ)实现过程。若设待排序的对象个数为n，则算法需要进行n-1次插入。最好情况(qíngkuàng)下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较1次，移动2次对象。因此，总的关键码比较次数为n-1，对象移动次数为2(n-1)。最坏情况下，第i趟插入时，第i个对象必须与前面i-1个对象都做关键码比较，并且每做1次比较就要做1次数据(shùjù)移动。则总的关键码比较次数KCN和对象移动次数RMN分别为若待排序对象序列中出现各种可能(kěnéng)排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为o(n2)。直接插入排序是一种稳定的排序方法。2）折半(zhébàn)插入排序折半(zhébàn)插入排序的算法分析3）表插入排序1intLinkInsertSort(staticlinklis<Type>&list){list.v[0].Key=MaxNum;list.v[0].Link=1;list.v[1].Link=0;//形成(xíngchéng)循环链表表插入排序算法(suànfǎ)分析：4）希尔（shell）排序(páixù)（又称缩小增量排序(páixù)）38voidShellSort(SqList&L，intdlta[]，intt){//按增量(zēnɡliànɡ)序列dlta[0…t-1]对顺序表L作Shell排序for(k=0；k<t；++k)ShellSort(L，dlta[k])；//增量(zēnɡliànɡ)为dlta[k]的一趟插入排序}//ShellSort附：希尔排序(páixù)算法分析voidShellInsert(SqList&L，intdk){for(i=dk+1；i<=L.length；++i)if(r[i].key<r[i-dk].key){r[0]=r[i]；for(j=i-dk;j>0&&(r[0].key<r[j].key);j=j-dk)r[j+dk]=r[j]；r[j+dk]=r[0]；}}课堂练习：原始(yuánshǐ)序列：256，301，751，129，937，863，742，694，076，4389.3交换(jiāohuàn)排序1)冒泡排序冒泡排序的算法(suànfǎ)分析2）快速(kuàisù)排序()，1.这种不断划分子表的过程，计算机如何(rúhé)自动实现？pivotkey=r[low].key;//取支点(zhīdiǎn)的关键码存入pivotkey变量Low=high=3，本趟停止，将支点定位并返回位置(wèizhi)信息j从高端扫描(sǎomiáo)寻找小于pivot的元素voidQSort(SqList&L,intlow,inthigh){if(low<high){pivot=Partition(L,low,high);QSort(L,low,pivot-1);QSort(L,pivot+1,high);}}例3：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序(páixù)结束时，关键字序列的状态。快速排序(páixù)算法详细分析：在最坏的情况，即待排序对象序列已经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过n-1趟才能把所有对象定位，而且第i趟需要经过n-i次关键码比较才能找到第i个对象的安放位置，总的关键码比较次数将达到n2/2快速(kuàisù)排序是一个不稳定的排序方法讨论2.“快速排序”是否真的(zhēnde)比任何排序算法都快？