快速排序

1.快速排序思想1.1分治法1.2 主要思路

1.快速排序思想

1.1分治法

快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

1.2 主要思路

以一个数字为锚点，例如初始时取第一个数字。设两个指针分别指向数组的头和尾，然后依次移动指针，至两指针重合时，退出本次循环。

public static void main(String[] args) { int[] arr = {22,6,22,3,9,34,27,18,28,87,12,33}; qsort(arr, 0, arr.length-1); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } public static int[] qsort(int arr[],int start,int end) { int pivot = arr[start]; int i = start; int j = end; while (i < j) { while ( (i<j) && (arr[j] > pivot)) { j--; } while ( (i<j) && (arr[i] < pivot)) { i++; } if ((arr[i] == arr[j]) && (i<j)) { i++; } else { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } if ( i - 1 > start) arr = qsort(arr, start, i-1); if (j + 1 < end) arr = qsort(arr, j+1, end); return (arr); } ``` ## 1.3 示意图