东莞好的网站建设效果,网站里的课程配图怎么做,交互做的不好的网站,网站建设国内外现状快速排序的核心框架是“二叉树的前序遍历对撞型双指针”。我们在《一维数组》一章提到过”双指针思路“#xff1a;在处理奇偶等情况时会使用两个游标#xff0c;一个从前向后#xff0c;一个是从后向前来比较#xff0c;根据结果来决定继续移动还是停止等待。快速排序的每…快速排序的核心框架是“二叉树的前序遍历对撞型双指针”。我们在《一维数组》一章提到过”双指针思路“在处理奇偶等情况时会使用两个游标一个从前向后一个是从后向前来比较根据结果来决定继续移动还是停止等待。快速排序的每一轮进行的时候都是类似的双指针策略而递归的过程本质上就是二叉树的前序递归调用。 1 快速排序的基本过程
快速排序是将分治法运用到排序问题的典型例子 快速排序基本思想是 通过一个标记pivot元素将n个元素的序列划分为左右两个子序列left和right其中left中的元素都比pivot小right的都比pivot的大然后再次堆left和right各自再执行快速排序在将左右子序列排好序之后整个序列就有序了。这里排序进行左右划分的时候是一直划分到子序列只包含一个元素的情况然后再递归返回。 我们以关键字序列{26,53,48,15,13,48,32,15}看一下一次划分的过程: 上面红框位置表示当前已经被赋值给了pivot或者其他位置可以空出来放移动来的新元素了。我们可以看到26最终被放到了属于自己的位置上不会再变化。而左侧的都比26小左侧都比26大因此26的左右两侧可以分别再进行排序。 这一轮过程是什么呢就是数组增删的时候经常用的双指针策略我们在数组部分讲过不再赘述。而这里的每一轮都是一个相向的双指针而已没有任何神秘的。 根据上述原理我们可以写代码了在实现过程中为了方便实现会对部分代码微调一下详细代码如下
//原文件QuickSortBasic.java
public static void quickSort(int[] arr, int left, int right) {if (left right) {int pivot arr[right];int i left - 1;for (int j left; j right; j) {if (arr[j] pivot) {i;int temp arr[i];arr[i] arr[j];arr[j] temp;}}//哨兵移动到位置pivotIndex上int pivotIndex i 1;int temp arr[pivotIndex];arr[pivotIndex] arr[right];arr[right] temp;quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex 1, right);}
}
2.第二种实现方式
至于实现有很多种方式下面再给一种实现方式
void quickSort(int[] array, int start, int end) {if (start end) {return;}//这里就是一个对撞的双指针操作int left start, right end;int pivot array[(start end) / 2];while (left right) {while (left right array[left] pivot) {left;}while (left right array[right] pivot) {right--;}if (left right) {int temp array[left];array[left] array[right];array[right] temp;left;right--;}}//先处理元素再分别递归处理两侧分支与二叉树的前序遍历非常像quickSort(array, start, right);quickSort(array, left, end); }
复杂度分析 快速排序的时间复杂度计算比较麻烦一些。从原理来看如果我们选择的pivot每次都正好在中间效率是最高的但是这是无法保证的因此我们需要从最好、最坏和中间情况来分析
最坏情况就是如果每次选择的恰好都是low结点作为pivot如果元素恰好都是逆序的此时时间复杂度为O(n^2)如果元素恰好都是有序的则时间复杂度为O(n)折中的情况是每次选择的都是中间结点此时序列每次都是长度相等的序列此时的时间复杂度为(O(nlogn))
