数据结构-排序-快速排序

快速排序实现原理：

首先设定一个分界值，通过该分界值将数组分成左右两部分。将大于等于分界值的数据元素放到数组的右边（该分界值的右边），小于分界值的数据元素放到数组的左边（该分界值的左边）。然后，左边和右边的数据分别进行快速排序。排序过程如下：

快速排序算法实现：（不稳定算法）

public static void main(String[] args) { // 测试 int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8}; sort(arr); for (int i : arr) { System.out.print(i+"\t"); } } /* * 快速排序 */ // 判断v是否小于w private static boolean less(int v, int w) { return v < w; } // 交换a数组中，索引i和j位置的元素值 private static void exch(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } // 对数组内元素进行排序 public static void sort(int[] a) { int lo = 0; int hi = a.length - 1; sort(a, lo, hi); } // 对数组a中从索引lo到hi之间的元素进行排序 private static void sort(int[] a, int lo, int hi) { // 安全性校验 if(hi <= lo) { return ; } // 需要对数组中lo索引到hi索引处的元素进行分组（左子组合右子组） int partition = partition(a, lo, hi); //返回的是分组的分界值所在的索引，分界值位置变换的索引 // 让左子组有序 sort(a, lo, partition-1); // 让右子组有序 sort(a, partition + 1, hi); } // 对数组a中，从索引lo到hi之间的元素进行分组，并返回分组界限对应的索引 private static int partition(int[] a, int lo, int hi) { // 确定分界值 int key = a[lo]; // 定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置 int left = lo; int right = hi + 1; // 分割切分 while(true) { // 先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止 while(less(key, a[--right])) { if(right == lo) { break; } } // 再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止 while(less(a[++left], key)) { if(left == hi) { break; } } // 判断left>=right，如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可 if(left >= right) { break; } else { exch(a, left, right); } } // 交换分界值 exch(a, lo, right); // exch(a, lo, left); 等同的代码 return right; }

程序执行结果：