Java經典排序算法之快速排序代碼實例

更新時間：2023年10月20日 10:08:10 作者：惡魔青葉

這篇文章主要介紹了Java經典排序算法之快速排序代碼實例,快速排序實現的思想是指通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然后再按此方法對這兩部分數據分別進行快速排序,需要的朋友可以參考下

1.簡介

快速排序，快速排序（Quicksort）是對冒泡排序的一種改進。它采用了分治法的策略，數據量越大，越能體現快排的速度。

快速排序的平均時間復雜度是O(nlogn)，空間復雜度是O(log2n)，是不穩(wěn)定排序。

快速排序實現的思想是：指通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序。

整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

總的來說：

第一步、在數列中取出一個數作為基準數（一般是最左邊的數）。
第二步、定義兩個指針：一個從右往左移動，找到比基準數小的停下；另一個指針從左往右移動，找到比基準數大的停下，交換兩個指針對應的數。
第三步、交換完成，繼續(xù)檢索，重復第二步。
第四步、當兩個指針相遇，停止檢索，將基準數和相遇位置元素交換。此時，第一輪排序結束。這時候的數組特點：基準數左邊都小于基準數，基準數右邊都大于基準數
第五步、采用分治策略，按照上述步驟繼續(xù)排列基準數左邊，右邊同理。

看文字理解可能有點云里霧里，接下來我們用圖來解釋下這個過程。

2.圖解步驟

1.假設這有個待排序數組。我們定義基準數為5，定義兩個指針 i、j

在這里插入圖片描述

2.j指針先從右往左移動，找到比基準數小的，停下，然后i指針向右移動，找到比基準數大的，停下，

在這里插入圖片描述

3.找到了，停下。

在這里插入圖片描述

4.交換兩個元素。

在這里插入圖片描述

5.重復上述步驟，直到兩個指針相遇。

在這里插入圖片描述

6.到這里，基準數歸位了。你就會發(fā)現，基準數左邊的都小于基準數，基準數右邊的都大于基準數。

7.現在使用分治法策略，先排左邊，再排右邊，重復上面的步驟。

在這里插入圖片描述

左邊完成：

在這里插入圖片描述

同理。右邊也是。

在這里插入圖片描述

最終，完成排序。

在這里插入圖片描述

3.代碼實現

接下來，我們用java語言來實現一下這個過程吧。

package com.znzz.quicksort;
//快速排序
import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,3,65,7,4,6,2};
        System.out.println(Arrays.toString(arr));
       long start =  System.currentTimeMillis(); //獲取系統(tǒng)當前時間（ms）
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(System.currentTimeMillis() - start); //計算程序所用時間（ms）
    }
    // 定義方法，用來快速排序
    public static  void quickSort(int[] arr, int left, int right){
         //判斷，如果左邊大于右邊，不合法，直接return
        if (left > right){
            return;
        }
        //定義變量保存基準數
        int base = arr[left];
        //定義變量i，指向最左邊
         int i = left;
        //定義變量j，指向最右邊
        int j = right;
        //開始檢索
        while (i != j) {
            //由j從右往左檢索。檢索到比基準數小的就停下，檢索到比基準數小大的就據徐檢索
            while (arr[j] >= base && i < j) {
                j--;   //表示從右往左移動
            }
            //i從左往右檢索
            while (arr[i] <= base && i < j) {
                i++;   //表示從左往右移動
            }
            //到這，表示i、j都停下了，代表都找到了符合的元素，開始交換對應元素。
            swap(arr, i, j);
        }
               //到這，說明i = j，表示相遇了
               //停止檢索，把基準數和相遇位置的數交換。
               arr[left] = arr[i];
               arr[i] = base;
              //基準數在這就歸位了，這樣，左邊的數都比它小，右邊的數都比他大
              //現在開始排左邊。
            quickSort(arr, left, i-1);
        //現在開始排右邊。
        quickSort(arr, i+1, right);
    }
    public  static  void swap(int [] arr, int i, int j){
        int temp = arr[i];
           arr[i] = arr[j];
            arr[j] = temp;
   }
}