快速排序

快速排序 1.快速排序 注：经典快速排序总是指定数组的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。 （1）主要思想快速排序的主要思想是分治思想： 任取一个元素作为分界点pivot 对数组区间进行调整（调整方式有很多种），所有比pivot小的元素都放在前面，比pivot大的元素都放在后面，形成左右两个子表 递归处理左右两端区间 （2）局限性快速排序局限性： 快速排序是所有内部排序方法中最好的一个 快速排序是一种不稳定的排序方法 快速排序不是原地排序（程序中使用了递归需要递归调用栈的支持，而栈的长度取决于递归调用的深度） 平均时间复杂度O(nlog2n)：QSort—O(log2n)、Partition—O(n) 平均情况下需要使用O(logn)的栈空间，最坏情况下栈空间可以达到O(n) 快速排序不适用与对原本有序或基本有序的记录序列进行排序（划分元素值的随机性越好，排序速度越快，即非自然排序） 改变划分元素的选取方法，最多只能改变算法平均时间性能，无法改变最坏情况下的时间性能O(n2) 由于每次枢轴pivot记录的关键字都是大于其他所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时的快速排序就已经退化成为了没有改进措施的冒泡排序了。 2.快速排序模板（1）思路1： 将low值取出单独存放在key中， 对数组进行排序，排序方式为：当右侧比key小时将high覆盖low处值、当左侧比key大时将low覆盖high处 直到low与high相遇时，将key放回low与high相遇的位置 一轮排序完毕（key所在位置为最终有序位置） 递归处理左右两边区间 1234567891011121314151617181920//写法1:使用2个变量 low highint partition(int arr[], int low, int high) { int key = arr[low];//取low处元素的值作为比较参考 while(low < high) {\] while(low < high && arr[high] >= key) --high;//右侧比key元素大的元素结点不动 arr[low] = arr[hi ...