大学计算机类数据结构排序原理例题期末考研必会【排序原理】

大学计算机类数据结构排序原理例题期末考研必会【排序原理】

直接插入排序
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
初始：49，38，65，97，76，13，27
第一趟38，49，65，97，76，13，27
第一趟38，49，65，97，76，13，27
第一趟38，49，65，97，76，13，27
第一趟38，49，65，76，97，13，27
第一趟13，38，49，65，76，97，27
第一趟13，27，38，49，65，76，97

希尔排序
第i, i + d, i + 2d,…, i + kd的有序，最后d=1。（以相同格式代表不同增量）
初始：49，38，65，97，76，13，27，48
d=4 ： [49]，【13】，27，(48)，[76]，【38】，65，(97)
d=2 ： 27，13，49，38，65，48，76，97
d=1 ： 13，27，38，48，49，65，76，97

冒泡排序
从后往前（或从前往后)两两比较相邻元素的值，这两个元素若逆序则交换，若顺序则不变并比较下两个。
初始49，38，65，97，76，13，27，49
第一趟
49，38，65，97，76，13，27，48
49，38，65，97，76，13，27，48
49，38，65，97，13，76，27，48
49，38，65，13，97，76，27，48
……
13，49，38，65，67，76，27，48
第二趟（同理）
13，27，49，38，65，97，76，48
第三趟
13，27，38，49，65，97，76，48
第四趟
13，27，38，48，49，65，97，76
第五趟
13，27，38，48，49，65，76，97
快速排序（考研考频max）
第一个元素将待排序序列划分成左右两个部分
初始 49，38，65，97，76，13，27，49‘
第一次划分：基准/数轴49
先从后往前找小的换一次
27，38，65，97，76，13，49，49‘
再从前往后找大的换一次
27，38，49，97，76，13，65，49’
再先从后往前找小的换一次
27，38，13，97，76，49，65，49‘
再从前往后找大的换一次
27，38，13，49，76，97，65，49’
第二次划分：分基准27 ， 76得
【13】，27，【38】，49，【49‘，65】，76，【97】
第三次划分： 分基准49’
13，27，38，49，49’，65，76，97
快速排序草稿纸方法

简单选择排序
每次把最小的和第一个数交换
初始49，38，65，97，76，13，27，49‘
第一趟
13，38，65，97，76，49，27，49’
第二趟
13，27，65，97，76，49，38，49‘
第三趟
13，27，38，97，76，49，65，49’
第四趟
13，27，38，49，76，97，65，49‘
第五趟
13，27，38，49，49’，97，65，76
第六趟
13，27，38，49，49‘，65，97，76
第七趟
13，27，38，49，49’，65，76，97
最后剩一个不用再处理

堆排序（和树有关）
大根堆：根>左子树，根>右子树
小根堆：根<左子树，根<右子树

1. 初始序列化为大根堆
   初始序列：53,17,78,09,45,65,87,32
   
   方法：把分支节点依次处理,从底到高—“更大的孩子变爹，小元素不断下坠”
   得互换顺序：09-32，78-87，17-45，53-87，53-78
   
   得出大根堆：87,45,78,32,17,65,53,09
2. 将大根堆进行堆排序
   每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一个元素交换)
   第一趟 09,45,78,32,17,65,53,87
   调成大根堆 78,45,65,32,17,09,53
   第二趟 53,45,65,32,17,09,78,87
   调成大根堆65,45,53,32,17,09
   第三趟 09,45,53,32,17,65,78,87
   调成大根堆53,45,09,32,17
   第四趟 17,45,09,32,53,65,78,87
   调成大根堆45,32,09,17
   第五趟 17,32,09,45,53,65,78,87
   调成大根堆32,17,09
   第六趟 09,17,32,45,53,65,78,87
   调成大根堆17,09
   第七趟 09,17,32,45,53,65,78,87
   最后一趟完成，不处理

归并排序
核心 *** 作 : 把数组内的两个有序序列归并为一个----二路归并
初始：49 38 65 97 76 13 27
第一趟：【38 49】 【65 97】 【13 76 】【27】
第二趟：【38 49 65 97】 【13 27 76】
第三趟：【13 27 38 49 65 76 97】

基数排序
初始520->211->438->888->007->111->985->666->996->233->168 得到按关键字“递减”的有序序列。
答：创建9个队列以数组存（队列先入先出）Q9 Q8 Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0
第一趟: 以“个位"进行“分配”，得到按“个位"递减排序的序列

第二趟:以“十位”进行“分配” ，由于基于第一趟，所以“个位"越大的越先入队

第三趟:以“百位”进行“分配” ，由于基于第二趟，“十位"越大的越先入队

收集得996 ->985 -> 888 ->666 ->520 ->438 -> 233 ->211 -> 168 ->111 ->007