首页 > 代码库 > 快速排序(Java实现)
快速排序(Java实现)
在《算法导论》的第7章快速排序(QuiclSort)采用分治思想(Divide and Conquer)。对一个典型的子数组A[p..r]进行快速排序的三步分治过程：
- 分解（divide）：数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分。
- 解决（Conquer）：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。
- 合并（Combine）：因为子数组都是原址排序，所以不需要合并操作：数组A[p..r]已经有序。
1 QUICKSORT(A, p, r)2 if p < r3 q = PARTITION(A, p, r)4 QUICKSORT(A, p, q-1)5 QUICKSORT(A, q+1, r)
为了排序一个数组A的全部元素，初始调用是QUICKSORT(A, 1, A.length)。
数组的划分
算法的关键部分是PARTITION过程，它实现了对子数组A[p..r]的原址重排。
1 PARTITION(A, p, r)2 x = A[r]3 i = p-14 for j = p to r-15 if A[j] <= x6 i = i+17 exchange A[i] with A[j]8 exchange A[i+1] with A[r]9 return i+1
快速排序实现：
快速排序及数组划分：QuickSort.java
1 package quicksort; 2 3 public class QuickSort { 4 5 public void QuickSort1(int[] a, int p, int r) { 6 if (p < r) { 7 int q = Partition(a, p, r); 8 QuickSort1(a, p, q-1); 9 QuickSort1(a,q+1, r); 10 }11 }12 13 private int Partition(int[] A, int p, int r) {14 int x = A[r]; //pivot = A[p]15 int i = p-1;16 for (int j = p; j < r; j++) {17 if (A[j] <= x) { //与pivot作比较18 i++;19 int tmp = A[j];20 A[j] = A[i];21 A[i] = tmp;22 }23 }24 25 int tmp = A[r];26 A[r] = A[i+1];27 A[i+1] = tmp;28 29 return i+1;30 31 }32 33 }
测试快速排序代码：QuickSortTest.java
1 package quicksort; 2 3 public class QuickSortTest { 4 5 static int[] a ={2, 8, 7, 1, 3, 5, 6, 4}; 6 // static int[] a ={13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11}; 7 public static void main(String[] args) { 8 // TODO Auto-generated method stub 9 QuickSort quickSort = new QuickSort();10 quickSort.QuickSort1(a, 0, a.length-1);11 for (int i = 0; i < a.length; i++) {12 System.out.print(a[i]+" ");13 }14 }15 16 }
运行结果：
1 2 3 4 5 6 7 8
快速排序(Java实现)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。