快速排序动图
终极管理员 知识笔记 117阅读
什么是快速排序？
答：快速排序由C. A. R.Hoare在1960年提出。 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 接着，对两个“ [ ]”中的数据进行排序之后，整体的排序便完成了。 对“ [ ]”里面的数据 进行排序时同样也会使用快速排序。 先找一个基准数（一个用来参照的数），为了方便，我们选最左边的 6，希望将 >6 的放到 6 的右边，<6 的放到 6 左边。
什么是插入排序？
答：插入排序在实现上，通常采用in-place排序（即只需用到O (1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 1959年Shell发明，第一个突破O (n 2 )的排序算法，是简单插入排序的改进版。
如何重新排序数列？
答：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。 在这个分区退出之后，该基准就处于数列的中间位置。 这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。