快速排序是什么

快速排序算法是最常用的排序算法之一，尤其是对大型列表进行排序时，大多数编程语言、库都以一种或另一种方式实现了它。在 Java 中，Arrays.sort()方法使用由 Joshua Bloch 等人编写的双枢轴 快速排序 算法对原始数据类型进行排序。这种实现为大量数据集提供了更好的性能，传统的快速排序算法降低了二次性能。此方法还使用另一种很好的排序算法 MergeSort来对对象进行排序。C++ STL 库中也提供了快速排序实现。

为什么选择快速排序

你有没有想过为什么快速排序如此受欢迎？

1、它是我们拥有的最快的排序算法之一。平均而言，快速排序是一种 O(n log n) 算法，而最坏的情况是 O(n^2)，与冒泡排序或插入排序相比要好得多。

2、排序发生在同一个数组中，不需要额外的内存。

3、快速排序在对大量数字列表进行排序时非常高效，因为它不需要额外的内存，是一种非常节省空间的排序算法。快速排序也是一种自然递归算法，

如何实现快速排序

快速排序算法的实现步骤:

1. 从列表或数组中选择一个元素，称为基准值。基准值通常是数组的中间元素。

2. 重新排序列表，使所有值小于基准值的元素位于基准值之前，所有值大于基准值的元素位于基准值之后(相等的元素可以从两个方向排列)。这也称为分区。分区后，基准值就到了它的最终位置。

3.递归地将上述步骤应用于值较小的元素的子列表，并分别应用于值较大的元素的子列表。如果数组只包含一个元素或零个元素，则该数组是有序的。

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]