《《算法导论》学习总结——快速排序 (2)》由会员分享，可在线阅读，更多相关《《算法导论》学习总结——快速排序 (2)（3页珍藏版）》请在金锄头文库上搜索。
1、算法导论学习总结快速排序 一、冒泡排序 已知一组无序数据a1、a2、an，需将其按升序排列。首先比较a1与a2的值，若a1大于a2则交换两者的值，否则不变。再比较a2与a3的值，若a2大于a3则交换两者的值，否则不变。再比较a3与a4，以此类推，最后比较an-1与an的值。这样处理一轮后，an的值一定是这组数据中最大的。再对a1an-1以相同方法处理一轮，则an-1的值一定是a1an-1中最大的。再对a1an-2以相同方法处理一轮，以此类推。共处理n-1轮后a1、a2、an就以升序排列了。 优点：稳定； 缺点。慢，每次只能移动相邻两个数据。 二、选择排序 每一趟从待排序的数据元素中选出最小（或
2、最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 初始状态。无序区为r1.n，有序区为空。 第1趟排序 在无序区r1.n中选出关键字最小的记录rk，将它与无序区的第1个记录r1交换，使r1.1和r2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 第i趟排序 第i趟排序开始时，当前有序区和无序区分别为r1.i-1和r（1in-1）。该趟排序从当前无序区中选出关键字最小的记录rk，将它与无序区的第1个记录r交换，使r1.i和r分别变为记录个数增加1
3、个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 优点：移动数据的次数已知（n-1次）； 缺点。比较次数多。 三、插入排序 已知一组升序排列数据a1、a2、an，一组无序数据b1、b2、bm，需将二者合并成一个升序数列。首先比较b1与a1的值，若b1大于a1，则跳过，比较b1与a2的值，若b1仍然大于a2，则继续跳过，直到b1小于a数组中某一数据ax，则将axan分别向后移动一位，将b1插入到原来ax的位置这就完成了b1的插入。b2bm用相同方法插入。（若无数组a，可将b1当作n=1的数组a） 优点：稳定，快； 缺点。比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。 四、缩小增量排序 由希尔在1959年提出，又称希尔排序（shell排序）。 已知一组无序数据a1、a2、an，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d（d 第3页 共3页
