Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
前言 快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序 快速排序思想:
1)先从数列中取出一个数作为基准数; 2)分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边; 3)再对左右区间重复第二步,直到各区间只有一个数。
快速排序解析:
快速排序动图:
快速排序代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 public class QuickSort { public static void main (String[] args) { int [] arr = new int [8000000 ]; for (int i = 0 ; i < 8000000 ; i++) { arr[i] = (int ) (Math.random() * 8000000 ); } long start = System.currentTimeMillis(); quickSort(arr, 0 , arr.length - 1 ); long end = System.currentTimeMillis(); System.out.println("8000000个数字排序所用时间:" + (end - start)); } public static void quickSort (int [] arr, int left, int right) { int l = left; int r = right; int pivot = arr[(left + right) / 2 ]; int temp = 0 ; while (l < r) { while (arr[l] < pivot) { l++; } while (arr[r] > pivot) { r--; } if (l >= r) { break ; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; if (arr[l] == pivot) { r--; } if (arr[r] == pivot) { l++; } } if (l == r) { l++; r--; } if (left < r) { quickSort(arr, left, r); } if (right > l) { quickSort(arr, l, right); } } }
延伸 快速排序 快速排序算法 图解 快速排序 韩顺平数据结构和算法 Data Structure and Algorithms - Quick Sort
<
Algorithm Merge Sort
Design Patterns(二十二) Chain of Responsibility
>