歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Java實現快速排序算法

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序。它采用了一種分治的策略,通常稱其為分治法(Divide-and-ConquerMethod)。

  1. 基本思想

    1. 先從數組中找出一個數作為基准數
    2. 分區過程,將比這個數小的數全部放到它的左邊,大於它的數全部放到右邊
    3. 再對左右區間重復第二步,直到各區間都只有一個數
  2. 排序過程

    在一篇博客上看到一個很有趣的講解方法:叫做 挖坑填數+分治法

    假如有一個10個數的數組:i=0,j=9,pivot=array[i]=x

    由於已經array[0]中的數保存到pivot中,可以理解成在數組array[0]上挖了個坑,可以將其他數據填充到這裡來。

    然後j向前找比當前基准數pivot小的數,當符合條件時(比如是第8個參數),那麼將array[8]挖出填充到array[0]這個坑。這時就多出了array[8]這個坑,於是從i開始向後找大於pivot的數,填充array[8]這個坑。

    重復操作。

    最後i==j時會退出循環,這時多出了array[i]這個坑,怎麼辦呢?將pivot填充到array[i]。這時對左右兩個區間繼續進行排序就好了。

  3. 算法實現

    /**
 * 快速排序
 */
public class QuickSort {
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 通過劃分,基於分治思想,遞歸執行子任務排序最後合並
     * @param low 數組首位索引
     * @param high 數組末尾索引
     */
    private void quickSort(int[] array, int low, int high) {
        int pivotPos;
        if (low < high) {
            pivotPos = partition(array, low, high);
            quickSort(array, low, pivotPos - 1);
            quickSort(array, pivotPos + 1, high);
        }
    }

    /**
     * 簡單劃分方法
     */
    private int partition(int[] array, int i, int j) {
        int pivot = array[i]; // array[i] 就是 第一個坑

        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--; // 從右向左找出小於基准數pivot的數來填充array[i]
            }

            if (i < j) {
                array[i] = array[j]; // 將array[j]填充到array[i]中,array[j]就形成了一個新的坑
                i++;
            }

            while (i < j && array[i] <= pivot) {
                i++; // 從左向右找出大於基准數pivot的數來填充array[j]
            }

            if (i < j) {
                array[j] = array[i]; // 將array[i]填充到array[j]中,array[i]就形成了一個新的坑
                j--;
            }
        }

        array[i] = pivot; // 退出時,i等於j。將pivot填到這個坑中。
        return i;
    }
}

Copyright © Linux教程網 All Rights Reserved