快速排序QuickSort
排序 快速
2023-06-13 09:13:14 时间
通过递归算法对比基准值而进行快速的排序
快速排序利用分而治之的思想,它的最好和平均实际复杂度为O(nlogn),但是,如果选取基准的规则正好与实际数值分布相反,例如我们选取第一个数为基准,而原始序列是倒序的,那么每一轮循环,快排都只能把基准放到最右侧,故快排的最差时间复杂度为O(n2)。快排算法本身没有用到额外的空间,可以说需要的空间为O(1);对于递归实现,也可以说需要的空间是O(n),因为在递归调用时有栈的开销,当然最坏情况是O(n),平均情况是O(logn)。快速排序是不稳定的。
实现一 以左边第一个数为基准
public class QuickSort {
public static void main(String[] args) {
int[] arr={54,12,42,21,67,34,21};
quickSort(arr,0,arr.length-1);
}
//这个方法就是取找基准数的
private static void quickSort(int[] arr, int left, int right) {
// 递归需要出口
if(left > right){
return;
}
int i = left;
int j = right;
int baseNum = arr[left];
while( i != j){
while(arr[j] >= baseNum && j > i ){
j--;
}
while(arr[i] <= baseNum && i <j){
i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 相遇的基准数归位
arr[left] = arr[j];
arr[j] = baseNum;
quickSort(arr,left,i-1);
quickSort(arr,j+1,right );
}
}
实现二 取中间一个数为基准分界值
public class quickSort {
public static void main(String[] args) {
int[] arr={54,12,42,21,67,34,21};
System.out.println("排序前:"+ Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("排序后:"+ Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right){
int ltemp=left,rtemp=right;
int temp,mid;
mid=arr[(left+right)/2]; //分界值
while(ltemp<rtemp){
while (arr[ltemp]<mid){
ltemp++;
}
while (arr[rtemp]>mid){
rtemp--;
}
if(ltemp<=rtemp){
temp=arr[ltemp];
arr[ltemp]=arr[rtemp];
arr[rtemp]=temp;
--rtemp;
++ltemp;
}
}
if(ltemp==rtemp){
ltemp++;
}
if(left<rtemp){
quickSort(arr,left,ltemp-1); //递归调用
}
if(ltemp<right){
quickSort(arr,rtemp+1,right); //递归调用
}
}
}
Post Views: 70
相关文章
- 史上最详细图解快速排序的方法_快速排序的基本步骤
- javascript对象数组内元素排序
- 基础算法篇——快速排序
- C语言冒泡排序升序_c语言快速排序和冒泡排序
- 快速排序及其改进
- 排序算法
- 【算法】归并排序
- 经典排序算法:冒泡排序(Bubble Sort)详解编程语言
- 快速排序优化详解编程语言
- MySQL 中的排序功能实现(mysqlin排序)
- 功能Redis实现高性能排序功能(redis排序)
- Linux下的排序与统计技巧(linux排序统计)
- 阿里云远超 Spark,取得四个全球排序基准竞赛冠军!
- MySQL汉字拼音排序:一种实用的解决方案(mysql汉字拼音排序)
- MySQL汉字拼音排序实战指南(mysql汉字拼音排序)
- Redis排序让你不再盲目探索(有人用redis排序吗)
- Oracle中文字段进行排序的sql语句
- C++快速排序的分析与优化详解