金蟾岛复仇记,杏鲍菇的产地,洗牛站
(一)快速排序
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
1.算法描述;
(1)从数列中挑出一个元素,称为 “基准”(pivot);
(2)重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
(3)递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
2.手动模拟排序:
3.算法分析:
(1)最佳情况:平均情况:t(n) = o(nlogn)
(2)空间复杂度: o(logn)
(3)稳定性: 不稳定
(二)代码实现:
public class quicksort {
public static void main(string[] args) {
int[] arr = {3,4,1,2,7,8,6,5,9};
sort(arr);//快速排序
system.out.println("-----------------------------------------");
print(arr);//打印结果
}
public static void sort(int[] arr){
if(arr == null || arr.length <= 1){
return;
}
sort(arr,0,arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
//边界
if(left >= right){
return;
}
//获取基数
int pivot = arr[left];
int index = partition(arr,left,right);
sort(arr,left,index - 1);
sort(arr,index + 1,right);
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
// arr[left++] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
// arr[right--] = arr[left];
arr[right] = arr[left];
}
// left == right
arr[left] = pivot;
print(arr);
return left;
}
public static void print(int[] arr){
stringbuilder sb = new stringbuilder("[");
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]);
if(i != arr.length - 1){
sb.append(", ");
}
}
system.out.println(sb.append("]"));
}
}
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论