快速排序详解（C语言/python）

快速排序详解

介绍：

       快速排序于C. A. R. Hoare在1960年提出，是针对冒泡排序的一种改进。它每一次将需要排序的部分划分为俩个独立的部分，其中一个部分的数比的数都小。然后再按照这个方法对这俩个独立的部分分别进行快速排序，整个排序递归进行，从而使得整个数据变成有序序列。下面以一个8元素的乱序数组为例按照快速排序的思想，将这个数组一步一步的进行排序，再分别以C语言和python编写快速排序源码。本文全篇介绍从小到大排序，反序换符号就好

快排思想：

1.该数组的初始状态如下，一个8元素的乱序数组。接下来我们按照快排的思想来进行操作。

2.选择第一个元素为基准，将比它小的元素放在一起，大的元素放一起，划分之后的数组将会变成下图一般。

3.开始递归，将划分之后的俩个独立部分进行划分，如果独立部分只有一个元素了，就可以结束递归了。比如第一次划分之后的大元素部分，将其再次进行划分之后的结果如下图，以第一个元素65为基准进行划分，划分之后的部分都只有一个元素，因此可以结束递归，那接下来再看一下小元素的划分。

4.小元素划分，将小元素部分再次进行划分，以第一个元素38为基准进行划分，划分之后的大元素部分只有一个元素48，结束递归。而小元素部分还有俩个元素，需要进一步递归。

5.现在第一次划分之后的大小元素部分都完成了一层的递归，我们看一下数组当前的状态。红色框为大元素部分，经过一次划分之后，已经完成了排序。

6.小元素二次递归，以38为基准进行划分之后，比38小的还有俩个元素，需要继续进行划分，以24为基准进行划分，这里比24小的不存在，比24大的只有1个元素31，划分之后可以结束递归，到此所有的递归都已经结束了。再看一下现在的状态。

7.结束，从上图可以看到，递归结束之后，快排就已经完成了，一个乱序的数组现在变成了一个从小到大的有序数组。

树型图：

具体实现：

       还是以上面的乱序数组为例来介绍快速排序是如何来进行划分的，这里介绍一种挺好理解的实现方法。

1.初始状态

2.以49为基准，right从后向前寻找比49小的。（从小到大排序，大的在后面不用管），找到31比49小。left从前向后面找比49大的，找到65，将65与31交换位置。当前状态如下：

3.继续right从后向前寻找比49小的，找到24。当前状态如下：

4.left继续寻找比49大的，找到right与left重合还是找不到就可以结束寻找了。

5.这时候再将49与left所在的交换位置。

6.这就是完成了一次划分，之后按照这个方法，递归划分即可。

编码实现C语言：

#include <stdio.h>
#include <stdlib.h>
//将arr数组中下标为i的与下标为j的交换位置
void Swap(int arr[], int i, int j)
{
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
//将arr数组进行划分
int Partition(int arr[], int left, int right)
{
    //保存起始下标
    int index = left;
    //获取基准的值
    int tmp = arr[left];
    //循环查找  当left与right重合之后结束
    while(left < right)
    {
        while(left < right && arr[right] >= tmp)
        {
            right --;
        }
        //right从后面开始找  找到比tmp小的
        while(left < right && arr[left] <= tmp)
        {
            left ++;
        }
        //left从前面开始找  找到比tmp大的
        Swap(arr, left, right);
        //将找出来的俩个交换位置
    }
    Swap(arr,index,left);
    //将基准值换到left的位置上面，完成划分
    return left;
}

void Qsort(int arr[], int left, int right)
{
    int index;
    if(left < right)
    {
        //划分arr数组  下标left到right部分
        index = Partition(arr, left, right);
        //划分完成之后递归对俩个独立分区进行快排
        Qsort(arr, left, index - 1);
        Qsort(arr, index + 1, right);
    }
}
int main()
{
    int arr[10]= {49,38,65,48,24,31,62,79};
    int  i;
    Qsort(arr, 0, 7);
    for(i=0; i<8; ++i)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

编码实现python：

# coding=utf8
import uuid
import random
import string

def partition(alist, start, end):
    index = start
    tmp = alist[start]
    while start < end:
        while (start < end and alist[end] >= tmp):
            end -= 1
        while (start < end and alist[start] <= tmp):
            start += 1
        alist[start],alist[end] = alist[end],alist[start]
    alist[index], alist[end] = alist[end], alist[index]
    return end

def quick_sort(alist, start, end):
    if start >= end:
        return
    left = partition(alist, start, end)
    # 对左边部分执行快速排序
    quick_sort(alist, start, left - 1)
    # 对右边部分执行快速排序
    quick_sort(alist, left + 1, end)

qlist = [49,38,65,48,24,31,62,79]
#qlist = [1, 12, 22, 34, 21, 4, 6, 8, 11, 54, 36, 7, 3, 0, 60, 62, 63]
quick_sort(qlist, 0, len(qlist) - 1)
print(qlist)

python一条语句解决快排源码：

quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) +[array[0]] + quick_sort([item for item in array[1:] if item >array[0]])