排序算法之快速排序

简介

快速排序是由冒泡排序演变而来，比冒泡排序更快的排序算法。之所以快，是由于快速排序用了分治法。
雷同的是，与冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换来排序。
不同的是，冒泡排序每一轮只把一个元素冒泡到数列的一端，而快速排序每轮挑选一个基准元素，让比它小的元素移动到一端，让比它大的元素移动到另一端，从而把数列拆解成两个部分。
算法分析

双循环

• 基准线选择：一样平常使用头节点的值作为基准线
  
• 元素交换：使用两个下标，分别向中心移动，停止时举行元素交换
  
• 分治：当循环结束，根据停止时的下标分割数组，递归调用
  
  
  
  

单循环

• 基准线选择：一样平常使用头节点的值作为基准线
  
• 元素交换：定义mark 标记，循环向右侧移动，直到元素比基准线小，则mark标记+1，并交换
  
• 分治：当循环结束，根据停止时的下标分割数组，递归调用
  
  
  
  

代码实现

1. package com.zh.sort;
4. /**
5. * 快排分两种：
6. * 1. 双循环排序 ： 从列表两端循环
7. * 2. 单循环排序 ： 从列表一段循环
8. */
9. public class QuickSort {
12.     public void quickSort(int[] arr, int low, int high) {
13.         if (low < high) {
14.             // 找到基准值的位置
15.             int pivotIndex = doublePartition(arr, low, high);
16.             // 对基准值左边的子数组进行快速排序
17.             quickSort(arr, low, pivotIndex - 1);
18.             // 对基准值右边的子数组进行快速排序
19.             quickSort(arr, pivotIndex + 1, high);
20.         }
21.     }
23.     /**
24.      * 双循环排序法
25.      * @param arr
26.      * @param low
27.      * @param high
28.      * @return
29.      */
30.     private int doublePartition(int[] arr, int low, int high){
31.         // 定义基准线
32.         int p = arr[low];
33.         // 左指针
34.         int l = low;
35.         // 右指针
36.         int r = high;
37.         while (l < r){
38.             while (l < r && arr[r] >= p){
39.                 r--;
40.             }
41.             while (l < r && arr[l] <= p){
42.                 l++;
43.             }
44.             if (l < r){
45.                 swap(arr, l, r);
46.             }
47.         }
48.         arr[low] = arr[l];
49.         arr[l] = p;
50.         return l;
51.     }
52.    
53.         /**
54.      * 单循环排序法
55.      * @param arr
56.      * @param low
57.      * @param high
58.      * @return
59.      */
60.     private int partition(int[] arr, int low, int high) {
61.         // 选择最后一个元素作为基准值
62.         int pivot = arr[low];
63.         int mark = low;
64.         for (int j = low + 1; j <= high; j++) {
65.             // 如果当前元素小于基准值，则将其与i指向的元素交换位置
66.             if (arr[j] < pivot) {
67.                 mark++;
68.                 swap(arr, mark, j);
69.             }
70.             printArr(arr);
71.         }
72.         // 将基准值放到正确的位置
73.         arr[low] = arr[mark];
74.         arr[mark] = pivot;
75.         return mark;
76.     }
78.     private void swap(int[] arr, int i, int j) {
79.         int temp = arr[i];
80.         arr[i] = arr[j];
81.         arr[j] = temp;
82.     }
84.     private void printArr(int[] arr){
85.         for (int num : arr) {
86.             System.out.print(num + " ");
87.         }
88.         System.out.println(" ------------------- ");
89.     }
90. }

复制代码

测试调用

1. public static void main(String[] args) {
2.         int[] arr = {3, 4, 2, 1, 5};
3.         QuickSort qs = new QuickSort();
4.         qs.quickSort(arr, 0, arr.length - 1);
5.         for (int num : arr) {
6.             System.out.print(num + " ");
7.         }
8.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。