数据结构与算法基础–第14周06–第8章排序6–8.3交换排序2–快速排序1

快速排序 — 改进的交换排序 基本思想:递归排序 任意取一个元素(如第一个)作为中心【 pivot 】 所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表。 对子表重新选择中心元素,并依此规则调整。 直到每一个子表的元素只剩下一个。 通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序。 具体实现: 选定一个中间数作为参考,所有元素与之比较,小的调到其左边,大的调到其右边。【 小的从左往右放,大的从右往左放。】 中间数:可以是第一个数,最后一个数、中间一个数、任选一个数。 上述方法需