快速排序
所属分类 algo
浏览量 759
快速排序 Quicksort 是对冒泡排序的一种改进
冒泡排序基础上的递归分治法
通过多次比较和交换来实现排序
非稳定 ,相同值的相对位置在排序结束后会改变
快速排序 最坏 O(n²) ,平均 O(nlogn)
且 O(nlogn) 记号中隐含的常数因子很小,比归并排序小很多
对绝大多数顺序性较弱的随机数列而言,快速排序优于归并排序
分治 Divide and conquer 和 递归
算法步骤
从数列中挑出一个元素,称为 基准 pivot
重新排序数列,小于基准的放左边,大于基准的放右边(相同可以放任一边) ,这个称为分区(partition)操作
递归地(recursive)排序 左右子数列
int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
left=0,right=8,partitionIndex=2
1 2 3 9 4 8 7 5 6
left=0,right=1,partitionIndex=0
1 2 3 9 4 8 7 5 6
left=3,right=8,partitionIndex=8
1 2 3 6 4 8 7 5 9
left=3,right=7,partitionIndex=5
1 2 3 5 4 6 7 8 9
left=3,right=4,partitionIndex=4
1 2 3 4 5 6 7 8 9
left=6,right=7,partitionIndex=6
1 2 3 4 5 6 7 8 9
public class QuickSort {
public static void main(String[] args) throws Exception {
int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
quickSort(arr);
System.out.println();
printArr(arr);
System.out.println();
int[] arr2 = { 3 };
quickSort(arr2);
System.out.println();
int[] arr3 = { 3, 2 };
quickSort(arr3);
System.out.println();
}
private static void quickSort(int[] arr) {
final int N = arr.length - 1;
quickSort(arr, 0, N);
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
// for debug
System.out.println("left=" + left + ",right=" + right + ",partitionIndex=" + partitionIndex);
printArr(arr);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
// 设定基准值 pivot
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private static void printArr(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]).append(" ");
}
System.out.println(sb.toString());
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/QuickSort.java
归并排序与快速排序
上一篇
下一篇
冒泡选择和插入排序比较
金庸小说人物英文名
希尔排序
Java assert
图论基础
Linux dd 命令