【A】排序-快速排序_vlambda技术博客

vlambda
2022-03-23

【A】排序-快速排序

上图为快速排序的排序的过程图.

快排算法中所包含的算法思想

在计算机科学中，分治法（英語：Divide and conquer）是建基於多項分支遞歸的一种很重要的算法範式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

算法思想：

- 选择Pivot中心轴

- 将小于Pivot的数字放在Pivot的左边

- 将大于Pivot的数字放在Pivot的右边

- 分别对左右子序列重复前三步操作

算法实现

/** * 快速排序 *  * @param arr * @param low * @param high */public static void quickSort(int[] arr, int low, int high) { if (arr == null || arr.length < 2) { return; }
 if (low < high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high);
 // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }}
static int partition(int[] arr, int low, int high) { // pivot int pivot = arr[high];
 // Index of smaller element and // indicates the right position // of pivot found so far int i = (low - 1);
 for (int j = low; j <= high - 1; j++) {
 // If current element is smaller // than the pivot if (arr[j] < pivot) {
 // Increment index of // smaller element i++; SwapUtils.swap(arr, i, j); } } SwapUtils.swap(arr, i + 1, high); return (i + 1);}