快速排序
快速排序使用的是分治思想,将原问题分成若干个子问题进行递归解决。
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
代码头部
初始化随机数组
swap
partion分区
学习视频 av46502941
3.6bili
public class QucikSort {
public static void main(String[] args) {
int N = 9;
int[] arr = new int[N];//N-1个数字
for (int i = 0; i < arr.length - 1; i++) {//length-1是留下一个 来写多的数字
arr[i] = (new Random().nextInt(5) + 1) * (new Random().nextInt(N - 1) + 1);
}
System.out.println(Arrays.toString(arr));
qucikSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
//交换
public static void swap(int[] arr, int x, int y) {
int tamp = arr[x];///换轴 作为下次的 mid
arr[x] = arr[y];
arr[y] = tamp;
}
public static void qucikSort(int[] A, int left, int right) {
if (left < right) {
int mid = partion2(A, left, right);//分区1 或者2
qucikSort(A, left, mid - 1);//左部分
qucikSort(A, mid + 1, right);//右部分
}
}
}
单轴排序
单向扫描划分 快速排序
private static int partion(int[] A, int left, int right) {
int pivot = A[left];//最最左边的数 作为轴 Pivot 中心点
int sp = left + 1;//扫描指针//位A[p+1]
int bigger = right;//左侧指针
while (sp <= bigger) {//索引 没有相互跨界
if (A[sp] <= pivot)//小于 轴(轴的左边 小)
sp++;//左指针 右移
else { //比轴大 应该在右边 因为是从左边开始扫描 大于轴的元素 和最右边的 数交换 书--
// swap(A[sp], A[bigger]);//大于主元 元素交换 指针左移
swap(A, sp, bigger);//将中心点交换到中间。
bigger--;
}
}
//左右排完 复位轴
swap(A, left, bigger);///换轴 作为下次的 mid 因为lift 一直是没有变的 他交给了 sp
return bigger;//->mid 让partion的右边界 作为轴 而 这个 数值 就是初始化的Pivot
}
双轴快排
//双向扫描划分
public static int partion2(int[] A, int p, int r) {//3.4
int povit = A[p];
int left = p + 1;
int right = r;
while (left <= right) {
//left不听的往右边走
while (left <= right && A[left] <= povit) left++;//循环退出时 left一定只想第一个大 于主元的元素
while (left <= right && A[right] > povit) right--;//循环退出时 right一定只想第一个小 于主元的元素
if (left < right)
swap(A, left, right);
}
swap(A, p, right);
return right;//返回right
}
关于QuickSort的实践工程优化
三点中值法 (普遍pivot)
主元 取 left right midIndex 这三个指针处的 中间数值
int midIndex=left+(right-left)/2;
绝对中值法
待排序列表较短时用插入排序 such as:8
https://github.com/Dxoca/Arithmetic/blob/master/src/A2_1%E6%8E%92%E5%BA%8F/QucikSort.java
自己的代码撸完了 再配合CSDN的 大佬的 分析讲解 完美!
本文地址:https://dxoca.cn/StudyNotes/173.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
ありがとう,学到了很多,快速排列的最坏时间复杂度是O(n^2),而归并排列的时间复杂度无论最好还是最坏的时间复杂度均为O(n lgn),那为什么人们认为快速排列快速呢?是因为就地排列吗?比如对于一个已经排列好的数组,进行快速排列就正是快速排列的最坏情况,复杂度为O(n^2),而对于归并而言,时间复杂度还是O(n lgn),有着惊人的(!)稳定性
欸,应该是temp而不是tamp吧
哈哈哈 是的(╯°A°)╯︵○○○