快速排序算法,二分思想
程序员文章站
2022-06-28 17:28:24
package QuickSortAlgorithm;public class QuickSort {//快速排序算法,原地操作public static void quickSort(int[] arr, int start, int end) {//交换辅助变量int t;int i = start;int j = end;//结束条件if(start >= end) return;//快排的基元int temp = arr[start]...
package QuickSortAlgorithm;
public class QuickSort {
//快速排序算法,原地操作
public static void quickSort(int[] arr, int start, int end) {
//交换辅助变量
int t;
int i = start;
int j = end;
//结束条件
if(start >= end) return;
//快排的基元
int temp = arr[start];
//快排算法,就是借用了二分法的思路
while(true) {
//从右边开始侦查
while(temp <= arr[j] && i != j) {
j --;
}
//左边也开始侦查,注意这里必须是>=号,不然的话,这里的第一步执行起来就有问题了
while(temp >= arr[i] && i != j) {
i ++;
}
//交换
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
//跳出循环的条件
if(i == j) {
//交换基元和i元素
t = arr[i];
arr[i] = arr[start];
arr[start] = t;
//调用递归
quickSort(arr, start, i - 1);
quickSort(arr, i + 1, end);
break;
}
}
}
public static void main(String[] args) {
int[] arr = {3,5,6,2,12,0,5,3,46,74,15,4,8};
quickSort(arr, 0, arr.length - 1);
System.out.println("快速排序后的结果为:");
for(int obj : arr) {
System.out.print(obj + "\t");
}
}
}
运行截图:
快速排序后的结果为:
0 2 3 3 4 5 5 6 8 12 15 46 74
小结:快速排序之所以快,是因为他排序的时候是跳跃的,像传统的冒泡排序法,是在相邻的两个变量之间进行交换,而快速排序通过选择一个基变量,可以很好的实现排序,其实就是二分法思想,分而治之,虽然和冒泡排序最差的情况一致,都是O(n^2),但是在实际情况中,却比冒泡排序来的要快,平均时间是O(nlogn)
本文地址:https://blog.csdn.net/qq_44652489/article/details/110873091
上一篇: Spring框架概述以及重要知识点解析