八大排序算法之快速排序

基本思想

1. 选择一个基准元素，通常选择第一个元素或者最后一个元素；
2. 通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大；
3. 此时基准元素在其排好序后的正确位置；
4. 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

算法的实现

package com.zyg.sort;

public class QuickSortAlgorithm
{
    // 快速排序
    public static void quickSort(int a[], int left, int right)
    {
        if (left < right)
        {
            // 获取数组中第left个元素在数组中的位置，将数组分为两部分
            int q = partition(a, left, right);
            // 左边部分进行排序
            <!--more-->
            quickSort(a, left, q - 1);
            // 右边部分进行排序
            quickSort(a, q + 1, right);
        }
    }
    
    public static int partition(int a[], int left, int right)
    {
        // 记录第left个元素的值
        int pivot = a[left];
        while (left < right)
        {
            // 从右边开始遍历数组，找到一个比pivot值小的元素
            while (left < right && pivot <= a[right])
                right--;
            // 将找到的元素值赋给第left个元素
            a[left] = a[right];
            
            // 从左边开始遍历数组，找到一个比pivot值大的元素
            while (left < right && pivot >= a[left])
                left++;
            // 将找到的元素值赋给第right个元素
            a[right] = a[left];
        }
        // 找到第left个元素的位置并插入
        a[left] = pivot;
        return left;
    }
    
    // 打印数组
    public static void printArray(int a[])
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
    
    public static void main(String[] args)
    {
        // 定义初始化数组
        int a[] =
        { 4, 3, 6, 7, 33, 15, 90, 65 };
        // 进行快速排序
        quickSort(a, 0, a.length - 1);
        // 打印数组
        printArray(a);
    }
}

效率

时间复杂度

平均情况：O(nlog₂n)
最好情况：O(nlog₂n)
最坏情况：O(n²)

空间复杂度

O(nlog₂n)

稳定性

不稳定