快捷導(dǎo)航

Java經(jīng)典排序算法之快速排序代碼實例

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

這篇文章主要介紹了Java經(jīng)典排序算法之快速排序代碼實例,快速排序?qū)崿F(xiàn)的思想是指通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序,需要的朋友可以參考下

1.簡介

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

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

快速排序?qū)崿F(xiàn)的思想是：指通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序。

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

總的來說：

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

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

2.圖解步驟

1.假設(shè)這有個待排序數(shù)組。我們定義基準(zhǔn)數(shù)為5，定義兩個指針 i、j

在這里插入圖片描述

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

在這里插入圖片描述

3.找到了，停下。

在這里插入圖片描述

4.交換兩個元素。

在這里插入圖片描述

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

在這里插入圖片描述

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

7.現(xiàn)在使用分治法策略，先排左邊，再排右邊，重復(fù)上面的步驟。

在這里插入圖片描述

左邊完成：

在這里插入圖片描述

同理。右邊也是。

在這里插入圖片描述

最終，完成排序。

在這里插入圖片描述

3.代碼實現(xiàn)

接下來，我們用java語言來實現(xiàn)一下這個過程吧。

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)當(dā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;
        }
        //定義變量保存基準(zhǔn)數(shù)
        int base = arr[left];
        //定義變量i，指向最左邊
         int i = left;
        //定義變量j，指向最右邊
        int j = right;
        //開始檢索
        while (i != j) {
            //由j從右往左檢索。檢索到比基準(zhǔn)數(shù)小的就停下，檢索到比基準(zhǔn)數(shù)小大的就據(jù)徐檢索
            while (arr[j] >= base && i < j) {
                j--;   //表示從右往左移動
            }
            //i從左往右檢索
            while (arr[i] <= base && i < j) {
                i++;   //表示從左往右移動
            }
            //到這，表示i、j都停下了，代表都找到了符合的元素，開始交換對應(yīng)元素。
            swap(arr, i, j);
        }
               //到這，說明i = j，表示相遇了
               //停止檢索，把基準(zhǔn)數(shù)和相遇位置的數(shù)交換。
               arr[left] = arr[i];
               arr[i] = base;
              //基準(zhǔn)數(shù)在這就歸位了，這樣，左邊的數(shù)都比它小，右邊的數(shù)都比他大
              //現(xiàn)在開始排左邊。
            quickSort(arr, left, i-1);
        //現(xiàn)在開始排右邊。
        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;
   }
}