中国空间站科幻作文1000字,新网站建设ppt,免费 搭建公司网站,建筑工程证书查询快速排序 快排的基本过程 快速排序是将分治法运用到排序问题的典型例子 快速排序基本思想是#xff1a;通过一个标记pivot元素将n个元素的序列划分为左右两个子序列left和right,.其中left中的元素都比pivot小#xff0c;right的都比pivot的大#xff0c;然后再次对Ieft和r… 快速排序 快排的基本过程 快速排序是将分治法运用到排序问题的典型例子 快速排序基本思想是通过一个标记pivot元素将n个元素的序列划分为左右两个子序列left和right,.其中left中的元素都比pivot小right的都比pivot的大然后再次对Ieft和right各自再执行快速排序在将左右子序列排好序之后整个序列就有序了。这里排序进行左右划分的时候是一直划分到子序列只包含一个元素的情况然后再递归返回。 我们以关键字序列{26,53,48,15,13,48,32,15}看一下一次划分的过程 上面红框位置表示当前已经被赋值给了pot或者其他位置可以空出来放移动来的新元素了。我们可以看到26最终被放到了属于自己的位置上不会再变化。而左侧的都比26小左侧都比26大因此26的左右两侧可以分别再进行排序。
代码实现 前面部分是利用快慢指针慢指针可以确定枢轴然后对枢轴两侧的序列通关递归继续快排
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);}}快排有很多种实现方式这是第二种“二叉树的前序遍历对撞型双指针”
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每次都正好在中间效率是最高的但是这是无法保证的因此我们需要从最好、最坏和中间情况来分析 1.最坏情况就是如果每次选择的恰好都是Iow结点作为pivot,如果元素恰好都是逆序的此时时间复杂度为O(n^2) 2.如果元素恰好都是有序的则时间复杂度为O(n) 3.折中的情况是每次选择的都是中间结点此时序列每次都是长度相等的序列此时的时间复杂度为(O(nlogn))
