《算法导论》学习总结——快速排序.docx

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