算法之快速排序详解

介绍：

快速排序是许多排序中非常常见的一种排序。其思想有取自归并排序，也包含分治思想。时间复杂度为nlog(n)，效率相当的高，因为数组的排列顺序是不固定的，最差的情况时间复杂度为O（n^2）,当给定的数组是完全有序的，快速排序就的运行原理就相当于冒泡排序，所以时间复杂度就等于冒泡排序的时间复杂度。

工作原理：

高位（High）：一般为序列最后一个元素，不固定，随着快排的进行不断的变换index。
低位(Low)：一般为序列的首个元素，不固定，随着快排的进行不断的变换index。
支点(Temp)：分治思想是将一个大序列不断的切分为若干小序列，分别进行排序。支点的位置即为切割序列的断点。支点的位置可以指定为随机的index，没有指定的话，在第一次快排的时候筛选出支点。
替代参数(@)：高低位交替比较的时候，存放支点的值的参数，没有实际作用，存放临时数据。
参照图（这种情况下手写表达起来更直观）：

拿到一组序列，进行一次快排，确定高低位和支点的值。
先假设第一个数是低位（L），最后一个数是高位（H），然后进行比较，if list[L] > list[H] ①将高位的值赋给低位②将低位的值赋给temp③将@赋值给高位。反之，低位的index将不断地后移，直到满足条件为止。
当@标识在低位的时候，然后开始判断高位，反之当@标识在高位的时候，判断低位。
当@在高位的时候，if list[low] < temp 低位的index后移。反之， if list[low] >temp ①低位元素的值赋给高位元素②高位index前移③@移到低位。开始比较高位。
if list[high] > temp 高位index前移，继续比较新的高位值。反之，同上。
一次快排之后，确定支点的位置，然后将序列截成两个序列，每个序列再进行上述操作。
当高位和低位重合的时候，再将temp赋值给高低位。

简单的说，上面的三组操作上为了找出temp的最终位置，每一步都保证L前面都比temp小，H后面都比temp大。所以，H与L重合的位置上的元素只能是temp的值了
上面提到的三组操作可以简化成下面的几条规则，便于记忆：
1.L指向的值小则L移动，反之赋值并移动指针
2.H指向的值大则H移动，反之同上
3.若HL重合，则赋值temp
4.H，L轮流与temp比较，规则是赋值一次后算一轮结束（所以一开始也可以从L与temp开始比较，下一轮H与temp比，再下一轮…）

最后

以上就是忧伤月亮为你收集整理的算法之快速排序详解的全部内容，希望文章能够帮你解决算法之快速排序详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。