首页  

快速排序     所属分类 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 命令