首页 > 代码库 > 快速排序(Java实现)

快速排序(Java实现)

2024-10-18 17:53:40   209人阅读

在《算法导论》的第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实现)


联系
我们