快捷導(dǎo)航

Java排序算法中的快速排序算法實(shí)現(xiàn)

更新時(shí)間：2023年12月12日 08:57:07 作者：warybee

這篇文章主要介紹了Java排序算法中的快速排序算法實(shí)現(xiàn),通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,需要的朋友可以參考下

Java快速排序算法

1.介紹

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列

2.排序原理

如果要排序數(shù)組（int[p--r]）中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到 r 之間的任意一個(gè)數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）,遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過(guò)這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的。然后再使用遞歸，排序從下標(biāo)p 到 q-1 之間的數(shù)據(jù)和從下標(biāo) q+1 到 r 之間的數(shù)據(jù)，直到區(qū)間縮小為 1，就說(shuō)明所有的數(shù)據(jù)都有序了。

在這里插入圖片描述

3.代碼實(shí)現(xiàn)

基于java實(shí)現(xiàn)（沒(méi)有使用java的一些高級(jí)語(yǔ)言，可以擴(kuò)展為你熟悉的語(yǔ)言）

public static void main(String[] args) {
        int[] array=new int[]{6,4,3,2,7,9,5};
        quickSort(array,0,array.length-1);
        System.out.println(array.length);
    }
    public static void   quickSort(int[] array, int p, int r) {
        //遞歸結(jié)束條件
        if (p>=r) return;
         int q=partition(array, p, r); // 獲取分區(qū)點(diǎn)
        quickSort(array,  p, q-1);
        quickSort(array, q+1, r);
    }
    //獲取分區(qū)點(diǎn)
    private static int partition(int[] array, int p, int r) {
        int pivot=array[r];//選取數(shù)組中最后一個(gè)作為分區(qū)點(diǎn)
        int i=p;//分區(qū)點(diǎn)下標(biāo)索引，默認(rèn)為數(shù)組的開始位置
        //遍歷數(shù)組，依次與pivot比較，小于pivot的放到左側(cè)，大于pivot的在右側(cè)
        for (int j=p;j<r;j++){
            if (array[j]<pivot){
                int tmp=array[j];
                array[j]=array[i];
                array[i]=tmp;
                i++;
            }
        }
        //把數(shù)組的最后一個(gè)元素(pivot 分區(qū)點(diǎn))拷貝到具體,分區(qū)點(diǎn)對(duì)應(yīng)位置
        int tmp=array[r];
        array[r]=array[i];
        array[i]=tmp;
        return i;
    }