快速排序知乎
终极管理员 知识笔记 148阅读
什么是快速排序？
答：快速排序是对冒泡排序算法的一种改进，同冒泡排序一样，快速排序也属于 交换排序 ，通过元素之间的比较和交换位置来达到排序的目的。 不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序 在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分 ，这种思路就叫做 分治法 。 排序算法是为了让无序的数据组合变成有序的数据组合。
快速排序的优越性体现在哪些方面？
答：第二，假如我们已知， ,那么 就不需要进行比较了，再进行比较就算是 冗余 ，而在快排中这种情况是不会发生的，因为 就是递归排序的基准，因此 就只会在自己的区间进行排序，不会出现冗余排序了。 因此，我们可以了解到，快速排序的优越性体现在他没有多余的比较上，对于初学者，我们可以较为简单的认为，快排所需要的 指令数会比较少。
什么是比较类排序？
答：1、比较类排序,通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O (nlogn) ,因此也称为非线性时间比较类排序。 2、比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。 可以说，比较排序适用于一切需要排序的情况。 1、不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 2、非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。 所以对数据规模和数据分布有一定的要求。 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序和冒泡排序有什么区别？
答：1.快速排序总体来说较为复杂，在学习过程中，必须熟悉其基本原理，并且要求能很快的写出相关代码。 该排序算法在每次取基准之后，如果基准两边的子序列长度较为平均的话其时间复杂度为O（nlog n）。 2.快速排序之所比较快，因为相比冒泡排序，每次交换都是跳跃式的。