排序算法传送：

排序算法——java实现冒泡排序
排序算法——java实现选择排序
排序算法——java实现直接插入排序
排序算法——java实现二分法排序
排序算法——java实现希尔排序
排序算法——java实现快速排序

快速排序

1、算法思想
快速排序是由冒泡排序改进而得到的，是一种分区交换排序方法。思想如下：
一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序的记录。

（1）在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准，称为基准记录；
（2）定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”，key 表示“基准值”；
（3）首先，尾索引向前扫描，直到找到比基准值小的记录(left != righ)，并替换首索引对应的值；
（4）然后，首索引向后扫描，直到找到比基准值大于的记录(left != righ)，并替换尾索引对应的值；
（5）若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束;将基准值(key)替换首索引对应的值;
（6）再进行下一趟排序时，待排序列被分成两个区:[0,left-1],[righ+1,end]
（7）对每一个分区重复步骤2~6，直到所有分区中的记录都有序，排序成功。

图解：

2、代码实现

/**
 * 快速排序演示
 * @author Lvan
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};

        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }

    /**
     * @param arr        待排序列
     * @param leftIndex  待排序列起始位置
     * @param rightIndex 待排序列结束位置
     */
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[left];
        //从左右两边交替扫描，直到left = right
        while (left < right) {
            while (right > left && arr[right] >= key) {
                //从右往左扫描，找到第一个比基准值小的元素
                right--;
            }
            //找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) {
                //从左往右扫描，找到第一个比基准值大的元素
                left++;
            }
            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        //基准值归位
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }
}

3、复杂度

• 最优的情况下时间复杂度为：O( nlogn )
• 最差的情况下时间复杂度为：O( n^2 )
• 快速排序的平均时间复杂度也是：O(nlogn)
• 最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
• 最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

一、快速排序算法实现原理

基本思想

• 先从数列中取出一个数作为基准数。
• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 再对左右区间重复第二步，直到各区间只有一个数。

具体步骤

1. 先以一个基准开始（通常为第一个数）
2. 从右边开始找到第一个比基准小的数
3. 从左边开始找到第一个比基准大的数
4. 将比基准小的数和比基准大的数调换位置
5. 继续从右往左以及从左往右调到对应的数，直到二边重合结束
6. 将基准的数与重合的数调换位置，这是基准左边都是小的数，右边都是大的数
7. 重复1,2,3,4对左右两边的数进行排序

二、图解快速排序

三、py代码实现快速排序算法

关键代码：

def quit_sort(arr, left, right):
    """快速排序算法
        思想：快速排序是效率最高的排序算法之一,
        1.先以一个基准开始（通常为第一个数）
        2.从右边开始找到第一个比基准小的数
        3.从左边开始找到第一个比基准大的数
        4.将比基准小的数和比基准大的数调换位置
        5.继续从右往左以及从左往右调到对应的数，直到二边重合结束
        6.将基准的数与重合的数调换位置，这是基准左边都是小的数，右边都是大的数
        7.重复1,2,3,4对左右两边的数进行排序
    """
    # 列表长度大于1
    if len(arr) <= 1 or left > right:
        return
         # 定义基准
    temp = arr[left]
    # 定义从左边开始的数(基准的下一个数)
    i = left
    # 定义从右边开始的数（要判断的末尾）
    j = right
    # 一直循环到从左边开始的碰到从右边开始的
    while i < j:
        # 从右边开始的一直循环到第一个比基准小的数且没有碰头为止
        while arr[j] >= temp and i < j:
            j -= 1
        # 从左边开始的一直循环到第一个比基准大的数且没有碰头为止
        while arr[i] <= temp and i < j:
            i += 1
        # 当在两边找到符合条件且没有碰头的数据时，将数据调换位置
        if i < j:
            mTemp = arr[j]
            arr[j] = arr[i]
            arr[i] = mTemp
        # 继续往下循环找到所有的符合条件的并调换位置

    # 到这里当前基准循环完毕，将当前基准和结束循环的位置数调换，使得基准左边都是小于基准的数，右边都是大于基准的数
    arr[left] = arr[i]
    arr[i] = temp
    # 继续将基准两边的数进行以上操作
    quit_sort(arr, left, j-1)
    quit_sort(arr, j+1, right)
        

运行：

# 定义一个列表
arr = [2, 3, 1, 5, 10, 6, 3, 4, 8]
print(arr)
quit_sort(arr, 0, len(arr) - 1)
print(arr)

打印结果：

[2, 3, 1, 5, 10, 6, 3, 4, 8]
[1, 2, 3, 3, 4, 5, 6, 8, 10]

快速排序也是使用了分治思想的排序方法，但与归并排序不一样的是“分”的时候的依据。归并排序“分”的依据是对半分，不管大小，而快速排序则是选定数组中的一个值，以这个值为依据，将数组分为三个部分：小于这个值的部分，大于等于这个值的部分，这个值。这样就以选定的点将数组分为两部分（小于值的部分，大于等于值的部分），然后再通过迭代对这两个部分分别继续执行这样一个“分”的过程，直至最后只剩下1-2个元素，即无法再“分”时，此时数组也排序完成。
下面以图示的方法展示一下第一次“分”的过程。
首先给出要排序的数组$l=[2,8,7,1,3,5,6,4]$，$sta$和$end$分别为数组的首尾下标。利用$i$和$j$这两个数进行迭代。令$i=sta-1,j=sta$。








迭代过程中分成了这样几个部分：

$i$所在的位置是$<end$的最新的一个值，在“分”的最后，将返回$i+1$，即用来比较的值的位置，以供下次迭代。
具体的python代码实现如下。

#将数组分为两部分
def partition(l0,sta,end):
    i=sta-1
    for j in range(sta,end):
        if l0[j]<l0[end]:
            i=i+1
            #如果j所在的位置的值小于end，则i往前进一步，并与j的值交换，即将一个新的值加入到<end的区域
            x=l0[i]
            l0[i]=l0[j]
            l0[j]=x
    #一次“分”结束，将用于比较的值放在应该在的地方（两个区域的中间）
    i=i+1
    x=l0[i]
    l0[i]=l0[end]
    l0[end]=x
    return i
    
def quicksort(l0,sta,end):
    #当至少存在两个元素时，才进行接下来的分解
    if sta<end:
        mid=partition(l0,sta,end)
        #分成的sta—mid-1，mid+1—end两个区域接着进行分解、迭代
        quicksort(l0,sta,mid-1)
        quicksort(l0,mid+1,end)
    return l0

快速排序的最坏情况，即每次分解时都极其不平衡，分解为$n-1$个元素和$0$个元素，这样分解操作的时间复杂度为$\Theta (n)$,而对大小为$0$的数组进行迭代会直接返回，时间复杂度可以忽略。这样算法运行时间的递归式为
$T(n)=T(n-1)+\Theta (n)$
解为$T(n)=\Theta (n^2)$
而最好的情况则是每次都对半分，这样算出的时间复杂度为$\Theta (nlgn)$
而即使是每次的划分达到$9:1$这样一个很不平衡的状态，最终算出的时间复杂度也是$\Theta (nlgn)$，事实上，即使是$99:1$也是这样的时间复杂度。（结论和推导均来自《算法导论》）
所以快速排序法的期望时间复杂度为$\Theta (nlgn)$，是一个优秀的排序算法。