快速排序 - 数据结构与算法
算法思想
将待排序集合以该集合中随机的一个数为分界点分成左右两个集合,一次排序使其右边的集合的数据全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述排序操作,直到递归集合没有数据,递归结束完成排序。
算法描述
- 现有待排序数组s
- 令变量i=0,j=s.length
- 将待排序的数组s分成两个部分a和b,随机从a或b中取一个中间量temp
- 分别用开始用i变量从左向右遍历a,和用j变量从右向左遍历b,直到找到两个变量s[i]和s[j]使s[i]>temp和s[j]<temp并且i<j 然后交换两个变量,然后继续按照上述条件遍历,直到i>=j,使得集合b中的元素全部大于集合a中的元素
- 按照递归的方式,将a和b分别当作s继续过程2
public class Test{
static int a[]= new int[]{5,6,8,7,4,2,9,1,1,1,2,4,5,7,8,7,7,8};
public static void main(String args[]){
quick_sort(0,a.length-1);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println("--");
}
public static void quick_sort(int left,int right){
int i=left,j=right,k=a[left];
while(i<j){
while(i<j&&a[i]<k){
i++;
}
while(i<j&&a[j]>k){
j--;
}
if(i<j&&a[i]==a[j]){
i++;
}else{
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
if(i-1>left){
quick_sort(left,i-1);
}
if(right>j+1){
quick_sort(j+1,right);
}
}
}
时间空间复杂度
平均时间复杂度:O(nlogn)
平均空间复杂度:O(n)
评论区
请写下您的评论...
猜你喜欢
blog
算法-快速排序
数据结构与算法
3931
外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。java实现:packagesort.fast;/***快速排序*@aut
blog
算法-快速排序
数据结构与算法
4172
快速排序的排序流程--来自百度百科首先设定一个分界值,通过该分界值将数组分成左右两部分。将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分
blog
插入排序 - 数据结构与算法
数据结构与算法
1390
算法思想:把所有需要排序的数据分成两个集合,一个是待排序集合,一个是已排序的集合,算法每次从未排序集合顺序或随机拿取一个数据,把它加入到已排序集合使其有序,直到未排序集合中的数据被取走完,算法结束
blog
归并排序(递归)- 数据结构与算法
数据结构与算法
1488
序,若数组只有一个元素则无需操作。每次递归结束时,左右两个数组都是有序的,然后对这两个中的数据进行排序,使整个数组有序。直到算法结束。publicclassTest8{ publicstaticint
blog
希尔排序 - 数据结构与算法
数据结构与算法
1506
算法思想:希尔排序是插入排序的增强版,其主要的算法思想还是插入排序的思想。算法描述:在插入排序的基础上,对待排序数组进行间隔为inc的分组,然后对每个分组进行直接插入排序,一次排序完成后,减小inc
blog
数据结构+算法-堆排序
数据结构与算法
4919
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
blog
冒泡排序 - 数据结构与算法
数据结构与算法
1314
算法思想:每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完算法描述:用变量i遍历整个数组,用变量j遍历i后面的数组,每次交换i比j大的元素,使得i遍历过
数据结构与算法
1965
算法思想把所有需要排序的数据分成两个集合,一个是待排序集合,一个是已排序的集合,算法每次从未排序集合顺序或随机拿取一个数据,把它加入到已排序集合使其有序,直到未排序集合中的数据被取走完,算法结束案例
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
2024-08
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。