《算法导论》学习总结——快速排序排序算法总结所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。一、插入排序插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。①.直接插入排序（稳定）接插入排序的过程为。在插入第i个记录时，r1，r2，..ri-1已经排好序，将第i个记录的排序码ki依次和r1，r2，..，ri-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。代码如下：voiddir_insert（inta，intn）//直接插入排序{intj，t;for（inti=1;it）{a[j+1]=a[j];j--;}a[j+1]=t;}}1②.希尔排序（不稳定）：希尔（shell）排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d20）{for（j=k;j=0a[i]>t）{a[i+k]=a[i];i=i-k;}a[i+k]=t;}if（k==1）break;（k/2）%2==0。k=k/2+1：k=k/2;}}第1页共2页二、选择排序选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排2序。①.直接选择排序（不稳定）直接选择排序的过程是。首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n（n-1）/2=o（n^2）。当初始文件为正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3（n-1）。直接选择排序的平均时间复杂度为o（n^2）。直接选择排序是不稳定的。代码如下：voiddir_choose（inta，intn）//直接选择排序{intk，t;for（inti=0;i第2页共2页
