快速排序是什么

快速排序算法是最常用的排序算法之一，尤其是對大型列表進行排序時，大多數(shù)編程語言、庫都以一種或另一種方式實現(xiàn)了它。在 Java 中，Arrays.sort()方法使用由 Joshua Bloch 等人編寫的雙樞軸 快速排序 算法對原始數(shù)據(jù)類型進行排序。這種實現(xiàn)為大量數(shù)據(jù)集提供了更好的性能，傳統(tǒng)的快速排序算法降低了二次性能。此方法還使用另一種很好的排序算法 MergeSort來對對象進行排序。C++ STL 庫中也提供了快速排序實現(xiàn)。

為什么選擇快速排序

你有沒有想過為什么快速排序如此受歡迎？

1、它是我們擁有的最快的排序算法之一。平均而言，快速排序是一種 O(n log n) 算法，而最壞的情況是 O(n^2)，與冒泡排序或插入排序相比要好得多。

2、排序發(fā)生在同一個數(shù)組中，不需要額外的內存。

3、快速排序在對大量數(shù)字列表進行排序時非常高效，因為它不需要額外的內存，是一種非常節(jié)省空間的排序算法?？焖倥判蛞彩且环N自然遞歸算法，

如何實現(xiàn)快速排序

快速排序算法的實現(xiàn)步驟:

1. 從列表或數(shù)組中選擇一個元素，稱為基準值?；鶞手低ǔＪ菙?shù)組的中間元素。

2. 重新排序列表，使所有值小于基準值的元素位于基準值之前，所有值大于基準值的元素位于基準值之后(相等的元素可以從兩個方向排列)。這也稱為分區(qū)。分區(qū)后，基準值就到了它的最終位置。

3.遞歸地將上述步驟應用于值較小的元素的子列表，并分別應用于值較大的元素的子列表。如果數(shù)組只包含一個元素或零個元素，則該數(shù)組是有序的。

import java.util.Arrays;

/**
 * Test class to sort array of integers using Quicksort algorithm in Java.
 * @author Javin Paul
 */
public class QuickSortDemo{

    public static void main(String args[]) {

        // unsorted integer array
        int[] unsorted = {6, 5, 3, 1, 8, 7, 2, 4};
        System.out.println("Unsorted array :" + Arrays.toString(unsorted));

        QuickSort algorithm = new QuickSort();

        // sorting integer array using quicksort algorithm
        algorithm.sort(unsorted);

        // printing sorted array
        System.out.println("Sorted array :" + Arrays.toString(unsorted));

    }

}

/**
 * Java Program sort numbers using QuickSort Algorithm. QuickSort is a divide
 * and conquer algorithm, which divides the original list, sort it and then
 * merge it to create sorted output.
 *
 * @author Javin Paul
 */
class QuickSort {

    private int input[];
    private int length;

    public void sort(int[] numbers) {

        if (numbers == null || numbers.length == 0) {
            return;
        }
        this.input = numbers;
        length = numbers.length;
        quickSort(0, length - 1);
    }

    /*
     * This method implements in-place quicksort algorithm recursively.
     */
    private void quickSort(int low, int high) {
        int i = low;
        int j = high;

        // pivot is middle index
        int pivot = input[low + (high - low) / 2];

        // Divide into two arrays
        while (i <= j) {
            /**
             * As shown in above image, In each iteration, we will identify a
             * number from left side which is greater then the pivot value, and
             * a number from right side which is less then the pivot value. Once
             * search is complete, we can swap both numbers.
             */
            while (input[i] < pivot) {
                i++;
            }
            while (input[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                // move index to next position on both sides
                i++;
                j--;
            }
        }

        // calls quickSort() method recursively
        if (low < j) {
            quickSort(low, j);
        }

        if (i < high) {
            quickSort(i, high);
        }
    }

    private void swap(int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}

Output?:?

Unsorted?array?:[6,?5,?3,?1,?8,?7,?2,?4]

?Sorted?array?:[1,?2,?3,?4,?5,?6,?7,?8]

?文章來源地址http://www.zghlxwxcb.cn/news/detail-429855.html

到了這里，關于如何使用快速排序算法對整數(shù)數(shù)組進行就地排序？的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！