一、快速排序介绍百度百科是这样介绍快速排序的： 二、快速排序的算法思想
其实快速排序算法是基于一种“二分法”的思想，关于二分法的算法可以参考另一篇博客 经典算法（2）一文搞懂二分法查找（循环和递归两种方式），有关冒泡排序的算法参考 经典算法（1）冒泡排序及其优化
三、快速排序的实现过程我们随机取一个数字作为基准元素，为了方便，取第一个数字为基准元素，在此博客中演示的例子中，基准元素取为6；设置两个指针 i 和 j，它们分别指向数组的第一个元素和数组最后一个元素，即i=0，j=9。
首先让指针 j 开始向左挪动，直到找到一个小于6的数停下来。切换到指针 i 再向右挪动，直到找到一个数大于6的数停下来。 最后指针 j 停在了数字 1上，指针 i 停在了数字8上。让指针 i 和指针 j 指向的元素进行交换位置。 四、代码实现public class QuickSort { public static void main(String[] args) { int[] array = {6, 2, 4, 8, 9, 5, 7, 3, 1, 10}; System.out.println('排序之前的数组: ' + Arrays.toString(array)); quickSort(array, 0, array.length - 1); System.out.println('排序之后的数组: ' + Arrays.toString(array)); } private static void quickSort(int[] array, int startIndex, int endIndex) { if (startIndex < endIndex) { // 找基准元素 int baseIndex = divide(array, startIndex, endIndex); // 递归调用,对分隔后的左边数组快速排序 quickSort(array, startIndex, baseIndex - 1); // 递归调用,对分隔后的右边数组快速排序 quickSort(array, baseIndex + 1, endIndex); } else { return; } } /** * 利用双边循环法分隔数组 * * @param array 需要排序的数组 * @param startIndex 数组的开始下标 * @param endIndex 数组的结束下标 * @return 返回分隔点所在的位置 */ private static int divide(int[] array, int startIndex, int endIndex) { // 用数组的第一个元素作为起始元素 int base = array[startIndex]; int i = startIndex; int j = endIndex; while (i != j) { // 从右向左寻找第一个小于基准数的值 while (i < j && array[j] > base) { j--; } // 从左向右寻找第一个大于基准数的值 while (i < j && array[i] <= base) { i++; } // 交换位置 if (i < j) { swap(array, i, j); } } // 指针i 与指针j 相遇，把重合点的元素与基准元素交换位置 array[startIndex] = array[i]; array[i] = base; // 返回分隔点所在的位置 return i; } /** * 交换i 与 j 位置的值 * * @param array * @param i * @param j */ private static void swap(int[] array, int i, int j) { int temp; temp = array[i]; array[i] = array[j]; array[j] = temp; }}
代码执行结果： |
|
|
