- 排序之快速排序
- 前言
- 快速排序定义和时间复杂度分析
- 定义
- 算法复杂度
- 快速排序的优越性
- 解题思路及实例解答
- 解题思路
- Java实现
- 1.Java代码
- 升序排序
- 快速排序
- 随机化快速排序(改进版)
- 改进效果
- 2.代码运行示例:
- 样例输入:
- 样例输出:
- 总结
前言
本博客仅做学习笔记,如有侵权,联系后即刻更改
科普:快速排序
快速排序定义和时间复杂度分析
定义解题思路及实例解答算法复杂度是对冒泡排序算法的一种改进
快速排序算法的性能取决于划分的对称性快速排序的优越性(1)最坏情况:O(n^2)
√
(2)最好情况:O(nlogn)
√
(3)一般情况:O(nlogn)
√
平均时间复杂度:T(n) = O(nlogn)数据量越大,节省的计算资源越多!
解题思路Java实现 1.Java代码数据分区:一部分比另一部分小
递归排序:递归处理两部分
代码如下:
//主函数
import java.util.Scanner;
import static java.lang.Math.random;
public class quick_sort_main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int[] sort = new int[n];
for (int i = 0; i < n; i++) {
sort[i] = scanner.nextInt();
}
//1.
// quick_sort(0,n-1,sort);
//2.
quickSort(sort, 0 , n-1);
//3.生成随机数
// randomizedQuickSort(sort ,0 ,n-1);
for (int i = 0; i < n; i++) {
System.out.print(sort[i]+" ");
}
}
}
}
>交换函数
static void swap(int []sort,int i,int j){
int middle = sort[i];
sort[i] = sort[j];
sort[j] = middle;
}
升序排序这个可以实现排序,但是不知道是不是快速排序,有知道的可以评论留言告诉我一下,不甚感激
static void quick_sort(int low,int height,int[] sort){
if(low > height)
return ;
int i, j,temp,t;
i = low;
j = height;
temp = sort[low];
while (i
//从左边找比基准数小的第一个数
while (sort[j] >= temp && i < j) j--;
//从右边找比基准数大的第一个数
while (sort[i] <= temp && i < j) i++;
//满足条件,交换sort[i]和sort[j]
if (i < j) swap(sort,i,j);
}
sort[low] = sort[i];
sort[i] = temp;
quick_sort(low,j-1,sort);
quick_sort(j+1,height,sort);
}
快速排序
//2.分区函数
static int partition(int sort[], int p, int q){
int x = sort[p];
int i = p;
for(int j = p+1; j <= q; j++){
if(sort[j] <= x){
i++;
swap(sort, i , j);
}
}
swap(sort,p,i);
return i;
}
//2.快速排序
static void quickSort(int []sort, int p ,int q){
if(p < q){
int r = partition(sort, p ,q);
quickSort(sort, p ,r-1);
quickSort(sort, r+1, q);
}
}
随机化快速排序(改进版)快速排序算法的性能取决于划分的对称性
√
通过修改算法Partition,可以设计出采用随机选择策略的快速排序算法
√
在A[p..q]中随机选出一个元素作为划分基准
//3.随机数产生
static int rand(int p, int q){
return (int) (random()%(q-p+1) + p);
}
//3.分区函数
```java
static int randomizedPartition(int []sort, int p, int q){
int r = rand(p , q);
swap(sort, p , r);
int i = partition(sort, p, q);
return i;
}
//3.快速排序
static void randomizedQuickSort(int[] sort ,int p ,int q){
if (p < q) {
int r = randomizedPartition(sort , p, q);
randomizedQuickSort(sort ,p ,r-1);
randomizedQuickSort(sort ,r+1 ,q);
}
}
改进效果随机化快速排序时间复杂度:T(n)= O(nlogn)
2.代码运行示例:
样例输入:总结6 1 8 6 5 3 4
样例输出:
5 12 42 2 5 81 3 4 5 6 8
2 5 8 12 42
时间复杂度:
平均时间复杂度:T(n) = O(nlogn)
最坏情况:O(n^2)
经过随机数优化后,随机化快速排序时间复杂度:T(n)= O(nlogn)
小小励志
有些事你现在不做,一辈子都不会做了。
如果你想做一件事,全世界都会为你让路。
《搭车去柏林》



