快速排序算法动图
终极管理员 知识笔记 60阅读
排序算法有哪些？
答：排序算法可以分为 内部排序 和 外部排序 。 内部排序是数据记录在内存中进行排序。 而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
什么是快速排序？
答：快速排序由C. A. R.Hoare在1960年提出。 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 接着，对两个“ [ ]”中的数据进行排序之后，整体的排序便完成了。 对“ [ ]”里面的数据 进行排序时同样也会使用快速排序。 先找一个基准数（一个用来参照的数），为了方便，我们选最左边的 6，希望将 >6 的放到 6 的右边，<6 的放到 6 左边。
如何重新排序数列？
答：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。 在这个分区退出之后，该基准就处于数列的中间位置。 这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。