• 1. 第六章 排序排序定义——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫~ 排序分类 按待排序记录所在位置 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序 按排序依据原则内部排序分为: 插入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 归并排序:2-路归并排序 基数排序
  • 2. 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的;若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。按照排序的稳定性分类
  • 3. 按照排序的稳定性分类稳定排序是指对待排序文件或者数据记录中,当关键字均不相同时,排序结果是惟一的,而在待排序文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录相对次序保持不变,则称这种排序方法为稳定排序。 不稳定排序是指对待排序文件或者数据记录中,对具有相同关键字的记录经过排序后,其相对次序和原来对比发生了变化,则称这种排序方法为不稳定排序。
  • 4. #define MAXSIZE 100 //待排序记录序列中的最大数据元素个数 typedef int KeyType; typedef struct node { KeyType key; //数据元素的关键字 infotype otherdata; }RecordType; //待排序的数据元素类型 typedef RecordType RecData[MaxSize]; 顺序存储结构描述如下:
  • 5. 6.2 插入排序 将无序子序列中的一个或几个记录“插入”到有序序列中,从而增加记录的有序子序列的长度。 直接插入排序 排序过程:对于n个记录的序列,排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序
  • 6. 一次直接插入排序过程一次直接插入排序过程将30插入到有序序列(10、21、35、62、85、90)中:
  • 7. 例49 38 65 97 76 13 27i=1 38 (38 49) 65 97 76 13 27i=2 65 (38 49 65) 97 76 13 27i=3 97 (38 49 65 97) 76 13 27i=4 76 (38 49 65 76 97) 13 27i=5 13 (13 38 49 65 76 97) 27i=0 ( )i=6 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果:算法描述
  • 8. 课堂练习1、线性表采用顺序存储,写一算法实现直接插入排序,函数原型: void InsertSortSeq(SeqList *L); 2、线性表采用单链表存储,写一算法实现直接插入排序,函数原型: void InsertSortLink(LNode *head);
  • 9. 完整的直接插入排序算法为: void insertSort(int data[], int n) { for(int i = 0; i < n; i++) for(int j = i - 1; j >= 0; j--) { if(data[j + 1] < data[j]) { int tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp; } } }
  • 10. 直接插入排序算法简单、容易实现,其特点: 1.当待排序记录较少时,排序速度较快,但是,当待排序的记录数量较大时,直接插入排序算法的效率降低,平均时间复杂度o(n2); 2.当待排序的数据元素基本有序时,移动次数大大减少,从而效率会有所提高。 3.插入排序是一种稳定的排序方法。
  • 11. 希尔排序 (Shell Sort)基本思想设序列有 n 个对象, 首先取一个整数 d< n(n/2) 作为间隔, 将全部对象分为 d个子序列, 所有距离为 d 的对象放在同一个子序列中, 在每一个子序列中分别进行直接插入排序。然后缩小间隔 d, 例如取 d = d/2,重复上述的子序列划分和排序工作。直到最后取 d== 1, 将所有对象放在同一个序列中排序为止。 希尔排序方法又称为缩小增量排序。
  • 12. 希尔排序 (Shell Sort)设待排序序列{23,56,70,25,12,32,50,59,82,16},现利用希尔排序法对该序列进行排序,其排序过程如图所示,以升序为例:
  • 13. 希尔排序 (Shell Sort)
  • 14. (本页无文本内容)
  • 15. (本页无文本内容)
  • 16. (本页无文本内容)
  • 17. (本页无文本内容)
  • 18. (本页无文本内容)
  • 19. (本页无文本内容)
  • 20. i = 3d = 30 1 2 3 4 52108254925*160 1 2 3 4 52108254925*16i = 2d = 22108254925*162108254925*16i = 1d = 12108254925*162108254925*16希尔排序过程
  • 21. void shellsort(RecData R, int n) { int i,j,d; RecType temp; d=n/2; while(d>0) { for(i=d;i=0&&temp.key
  • 22. 直接插入排序算法简单、容易实现,其特点: 1.当待排序记录较少时,排序速度较快,但是,当待排序的记录数量较大时,直接插入排序算法的效率降低,平均时间复杂度o(n2); 2.当待排序的数据元素基本有序时,移动次数大大减少,从而效率会有所提高。 3.插入排序是一种稳定的排序方法。直接插入排序算法分析
  • 23. 希尔排序算法分析对于希尔排序的执行时间依赖于增量序列,希尔排序增量序列的选择具有共同的特征: (1)最后一个增量必须为1,d的取值一般不取2的倍数或者整数次幂的形式; (2)应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况; (3)希尔排序的性能分析过程比较复杂,经过大量实验得出,其时间复杂度为O(n3/2)。
  • 24. 冒泡排序 排序思路 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r[1].key>r[2].key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止6.3 交换排序
  • 25. 210825492516214925251608214925251608214925251608214925251608初 始 关 键 字第 一 趟 排 序第 四 趟 排 序第 二 趟 排 序第 三 趟 排 序214925251608第 五 趟 排 序冒泡排序的过程
  • 26. 冒泡排序算法: void bubbleSort(int data[], int count) { for(int i = 1; i < count; i++) { for(int j = 0; j < count - i; j++) { if(data[j] > data[j+1]) { int tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp; } } } }
  • 27. 冒泡排序比较简单,当初始序列基本有序时,冒泡排序有较高的效率,反之效率较低; 其次冒泡排序只需要一个记录的辅助空间,用来作为记录交换的中间暂存单元; 冒泡排序是一种稳定的排序方法。
  • 28. 内部排序的时间分析:实现内部排序的基本操作有两个:(2)“交换”记录。(1)“比较”序列中两个关键字的 大小;
  • 29. 时间分析:最好的情况(关键字在记录序列中顺序有序): 只需进行一趟冒泡“比较”的次数:最坏的情况(关键字在记录序列中逆序有序): 需进行n-1趟冒泡“比较”的次数:0“交换”的次数:“交换”的次数:n-1
  • 30. 快速排序 基本思想:通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序 排序过程:对r[s……t]中记录进行一趟快速排序,附设两个指针i和j,设支点记录tmp=r[s] 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于tmp的记录,并将r[j]移到r[i]的位置 再从i所指位置起向后搜索,找到第一个关键字大于tmp的记录,并将r[i]移到r[j]的位置 重复上述两步,直至i==j为止,再将tmp移入i所指位置 再分别对两个子序列进行快速排序,直到每个子序列只含有一个记录为止
  • 31. 快速排序的过程2108254925*16初始关键字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交换二次交换三次交换四次交换完成一趟排序ijijjiijjiji
  • 32. 08254925*1621完成一趟排序分别进行快速排序08254925*1621快速排序08492525*1621有序序列08254925*1621
  • 33. 快速排序例:对待排序序列{49,38,65,97,76,13,27,49}进行一趟快速排序
  • 34. 快速排序练习:对待排序序列{30,12,52,23,15,65,31,58,20,63}进行一趟快速排序
  • 35. 课堂练习1、线性表采用顺序存储,写一算法实现一趟快速排序,函数原型: void QuickSort(SeqList *L,int low,int high); 2、修改以上算法,实现快速排序,函数原型: void QuickSort(SeqList *L,int low,int high); 课后作业: 完成教材361页-363页作业
  • 36. 快速排序算法: void quickSort(int data[], int start , int end) { int i = start, j = end; if(i < j) { int tmp = data[i]; while(i != j) { while(j > i && data[j] >= tmp) j--; if(j > i) { data[i] = data[j]; i++; } while(j > i && data[i] <= tmp) i++; if(j > i) { data[j] = data[i]; j--; } } data[i] = tmp; quickSort(data, start, i-1); quickSort(data, i+1, end); } }
  • 37. 1.快速排序平均时间复杂度为 O(nlogn) 2、当待排序序列的关键字是随机分布时,快速排序的平均时间复杂度最优 3.若待排记录的初始状态为按关键字有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n2)。 4、快速排序是一种不稳定排序
  • 38. 直接选择排序 排序过程 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换 重复上述操作,共进行n-1趟排序后,排序结束8.4 选择排序
  • 39. 例初始: [ 49 38 65 97 76 13 27 ]kjjjjjjtti=11349一趟: 13 [38 65 97 76 49 27 ]i=2ttjjjjj2738二趟: 13 27 [65 97 76 49 38 ]三趟: 13 27 38 [97 76 49 65 ]四趟: 13 27 38 49 [76 97 65 ]五趟: 13 27 38 49 65 [97 76 ]六趟: 13 27 38 49 65 76 [97 ]排序结束: 13 27 38 49 65 76 97
  • 40. 直接选择排序练习:对待排序序列{30,25,12,37,15,58,8,13}进行直接选择排序,写出每一趟排序的结果
  • 41. 课堂练习1、线性表采用顺序存储,写一算法实现直接选择排序,函数原型: void SelectSort(SeqList *L); 2、线性表采用单链表存储,写一算法实现直接插入排序,函数原型: void SelectSort(LNode *L); 课后作业: 完成教材361页-364页作业
  • 42. 完整算法: void selectSort(int data[], int count) { for(int i = 0; i < count; i++) { for(int j = i+1 ; j < count; j++) { if(data[i] > data[j]) { int tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } } }
  • 43. 时间性能分析   对 n 个记录进行简单选择排序,所需进行的 关键字间的比较次数 总计为:  移动记录的次数,最小值为 0. 简单选择排序算法简单,但是速度较慢,时间复杂度为o(n2),并且是一种稳定的排序方法
  • 44. 归并——将两个或两个以上的有序表组合成一个新的有序表,叫~ 2-路归并排序 排序过程 设初始序列含有n个记录,则可看成n个有序的子序列,每个子序列长度为1 两两合并,得到n/2个长度为2或1的有序子序列 再两两合并,……如此重复,直至得到一个长度为n的有序序列为止6.5 归并排序
  • 45. 6.6 各种排序方法的综合比较
  • 46. 一、时间性能1. 平均的时间性能时间复杂度为 O(nlogn)快速排序、堆排序和归并排序时间复杂度为 O(n2):直接插入排序、冒泡排序和简单选择排序2、当待排序序列的关键字是随机分布时,快速排序的平均时间复杂度最优
  • 47. 3. 当待排记录序列按关键字顺序有序时4. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 直接插入排序和起泡排序能达到O(n)的时间复杂度, 快速排序的时间性能蜕化为O(n2) 。
  • 48. 二、空间性能:排序过程中所需的辅助空间大小所有的简单排序方法(包括:直接插入、起 泡和简单选择) 和堆排序的空间复杂度为O(1);2. 快速排序为O(logn),为递归程序执行过程中,栈所需的辅助空间;3. 归并排序所需辅助空间最多,其空间复杂度为 O(n);
  • 49. 三、排序方法的稳定性能 1. 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。排序之前 : { · · · · · Ri(K) · · · · · Rj(K) · · · · · }排序之后 : { · · · · · Ri(K) Rj(K) · · · · ·· · · · · }
  • 50. 例如: 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的;若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。
  • 51. 2. 对于不稳定的排序方法,只要能举出一个实例说明即可。3. 快速排序、堆排序是不稳定的排序方法。例如 : 对 { 4, 3, 4, 2 } 进行快速排序, 得到 { 2, 3, 4, 4 }
  • 52. 各种内部排序方法的比较排序方法简单排序快速排序堆排序归并排序最坏情况辅助空间稳定性平均时间O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n2)O(n2)O(n2)O(1)O(n)O(1)O(logn)稳定不稳定不稳定稳定