首页 > 代码库 > 排序之 快速排序
排序之 快速排序
采用算法导论上的实现方式，用java实现。
快排算法核心的部分便是partition过程，这里的partition采取最后一个元素作为pivot，i和j两个指针都从头向后扫描，如下图所示，数组被分为4个部分。
算法执行的过程：
代码实现：
import java.util.Arrays;public class MySort { public static void quickSort(int[] a) { qSort(a, 0, a.length - 1); } private static void qSort(int[] a, int p, int r) { if (p < r) { int q = partition(a, p, r); qSort(a, p, q - 1); qSort(a, q + 1, r); } } private static int partition(int[] a, int p, int r) { int x = a[r]; int i = p - 1; int j = p; for (j = p; j < r; j++) { if (a[j] <= x) { i++; swap(a, i, j); } } swap(a, i + 1, r); return i + 1; } private static void swap(int[] a, int i, int j) { if (i != j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } public static void main(String[] args) { int[] a = { 2, 8, 7, 1, 3, 5, 6, 4 }; System.out.println(Arrays.toString(a)); quickSort(a); System.out.println(Arrays.toString(a)); }}
正确性证明：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。