快速排序

综述

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序.

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists).具体算法描述如下:
1.从数列中挑出一个元素,称为"基准"(pivot);
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作;
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.

示意图

快速排序动态示意图 快速排序静态示意图

性质

排序类别:交换排序
是否是稳定排序:不稳定
是否是原地排序:
时间复杂度:O(n*lg(n))
空间复杂度:O(n)

---

解释

快速排序(quick sort)的采用了分治的策略.
分治策略指的是:将原问题分解为若干个规模更小但结构与原问题相似的子问题.递归地解这些子问题,然后将这些子问题的解组合为原问题的解.
快排的基本思想是:在序列中找一个划分值,通过一趟排序将未排序的序列排序成 独立的两个部分,其中左边部分序列都比划分值小,右边部分的序列比划分值大,此时划分值的位置已确认,然后再对这两个序列按照同样的方法进行排序,从而达到整个序列都有序的目的.

介绍

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序.
值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动.
一趟快速排序的算法是:
1.设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2.以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3.从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]的值交换;
4.从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]的值交换;
5.重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止.找到符合条件的值,进行交换的时候i, j指针位置不变.另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束).

特点

• 稳定性:快排是一种不稳定排序,比如基准值的前后都存在与基准值相同的元素,那么相同值就会被放在一边,这样就打乱了之前的相对顺序
• 比较性:因为排序时元素之间需要比较,所以是比较排序
• 时间复杂度:快排的时间复杂度为O(nlogn)
• 空间复杂度:排序时需要另外申请空间,并且随着数列规模增大而增大,其复杂度为:O(nlogn)
• 归并排序与快排 :归并排序与快排两种排序思想都是分而治之,但是它们分解和合并的策略不一样:归并是从中间直接将数列分成两个,而快排是比较后将小的放左边大的放右边,所以在合并的时候归并排序还是需要将两个数列重新再次排序,而快排则是直接合并不再需要排序,所以快排比归并排序更高效一些,可以从示意图中比较二者之间的区别.
• 快速排序有一个缺点就是对于小规模的数据集性能不是很好.

优化方式

• 等值聚集:在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割
• 分组基准:对于上面的代码,分组基准的选取只是取列表的第一个值,太过于随便,可以使用随机值作为基准;当取到序列的中间值时,快排效率是最高的,第一个值未必是列表的中间值.为了解决这个问题,我们可以选取列表中的几个值进行简单的比较,然后取这几个值的中间值作为分组基准.比如使用三数取中法,用来解决解决数据基本有序的(就是找到数组中最小下标,最大下标,中间下标的数字,进行比较,把中间大的数放在最左边)
• 若序列长度过于小(比如只有几个元素),快排效率就不如插入排序了.我们可以设置一个列表元素大小的临界值,若小于这个值,就用插入排序,大于这个值用快排.
• 使用尾递归优化

优化方式的各种名称

随机化快排

快速排序的最坏情况基于每次划分对主元的选择.基本的快速排序选取第一个元素作为主元.这样在数组已经有序的情况下,每次划分将得到最坏的结果.一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元.这种情况下虽然最坏情况仍然是O(n^{2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳.实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2}n).所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度.一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求.”
随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱.对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2).解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置.

平衡快排

每次尽可能地选择一个能够代表中值的元素作为关键数据,然后遵循普通快排的原则进行比较、替换和递归.通常来说,选择这个数据的方法是取开头、结尾、中间3个数据,通过比较选出其中的中值.取这3个值的好处是在实际问题中,出现近似顺序数据或逆序数据的概率较大,此时中间数据必然成为中值,而也是事实上的近似中值.万一遇到正好中间大两边小(或反之)的数据,取的值都接近最值,那么由于至少能将两部分分开,实际效率也会有2倍左右的增加,而且利于将数据略微打乱,破坏退化的结构.

外部快排

与普通快排不同的是,关键数据是一段buffer,首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序,然后从被排序数组的开头(或者结尾)读入下一个元素,假如这个元素小于buffer中最小的元素,把它写到最开头的空位上;假如这个元素大于buffer中最大的元素,则写到最后的空位上;否则把buffer中最大或者最小的元素写入数组,并把这个元素放在buffer里.保持最大值低于这些关键数据,最小值高于这些关键数据,从而避免对已经有序的中间的数据进行重排.完成后,数组的中间空位必然空出,把这个buffer写入数组中间空位.然后递归地对外部更小的部分,循环地对其他部分进行排序.

三路基数快排

(Three-way Radix Quicksort,也称作Multikey Quicksort、Multi-key Quicksort):结合了基数排序(radix sort,如一般的字符串比较排序就是基数排序)和快排的特点,是字符串排序中比较高效的算法.该算法被排序数组的元素具有一个特点,即multikey,如一个字符串,每个字母可以看作是一个key.算法每次在被排序数组中任意选择一个元素作为关键数据,首先仅考虑这个元素的第一个key(字母),然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分.然后递归地基于这一个key位置对“小于”和“大于”部分进行排序,基于下一个key对“等于”部分进行排序.

Python实现及优化

def quick_sort1(array, left, right):
    if left < right:
        equal_pos = partition1(array, left, right)
        quick_sort1(array, left, equal_pos - 1)
        quick_sort1(array, equal_pos + 1, right)
        # print('equal_pos:', equal_pos, ',array:', array)
    return array


def partition1(array, left, right):
    temp = array[right]
    index = left - 1
    for pos in range(left, right):
        if array[pos] <= temp:
            index += 1
            array[index], array[pos] = array[pos], array[index]
    array[index + 1], array[right] = array[right], array[index + 1]
    print(array)
    return index + 1

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = quick_sort1(dest, 0, len(dest) - 1)
print('最后的结果是:', result)

'''
[2, 1, 3, 4, 8, 5, 6, 7]
[1, 2, 3, 4, 8, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

"""
优化方式一：等值聚集
等值聚集在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割

三路快排优化
虽然三数取中可以优化数组基本排序好的情况，但是对于出现很多相同数据的数列，还是无法优化，譬如一个数列全是由1组成的，对这个数列进行排序时时间复杂度就是n的平方，因为原始的快排对于大量重复的数据束手无策，这时就需要进行三路快排，在遍历的过程中把与pivot相同的数收集在数组的两侧，在pivot放置到正确的位置后再将数组两侧收集好的这些相同的数放在pivot的两边，再对除了pivot及相同数据以外的数组进行分治快排。当然在进行三路快排的同时还可以继续使用三数取中，同时优化。

具体过程：在处理过程中，会有两个步骤
第一步，在划分过程中，把与key相等元素放入数组的两端
第二步，划分结束后，把与key相等的元素移到枢轴周围
"""


def quick_sort2(array):
    if len(array) < 2:  # 基线条件（停止递归的条件）
        return array
    else:  # 递归条件
        baseValue = array[0]  # 选择基准值
        # 由所有小于基准值的元素组成的子数组
        less = [m for m in array[1:] if m < baseValue]
        # 包括基准在内的同时和基准相等的元素，在上一个版本的百科当中，并没有考虑相等元素
        equal = [w for w in array if w == baseValue]
        # 由所有大于基准值的元素组成的子数组
        greater = [n for n in array[1:] if n > baseValue]
        print('本次进行排序的结果是:', less, equal, greater)
    return quick_sort2(less) + equal + quick_sort2(greater)

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = quick_sort2(dest)
print('最后的结果是:', result)

'''
本次进行排序的结果是: [2, 4, 1, 3] [5] [7, 8, 6]
本次进行排序的结果是: [1] [2] [4, 3]
本次进行排序的结果是: [3] [4] []
本次进行排序的结果是: [6] [7] [8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''


"""
优化方式二
随机选取基准
引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴
思想：取待排序列中任意一个元素作为基准
"""
import random

def quick_sort3(array):
    if len(array) < 2:  # 基线条件（停止递归的条件）
        return array
    else:
        # 递归条件
        # 随机选择基准值
        random_index = random.randint(0, len(array)-1)
        baseValue = array[random_index]
        # 由所有小于基准值的元素组成的子数组
        less = [m for m in array[:random_index] + array[random_index+1:] if m < baseValue]
        # 包括基准在内的同时和基准相等的元素，在上一个版本的百科当中，并没有考虑相等元素
        equal = [w for w in array if w == baseValue]
        # 由所有大于基准值的元素组成的子数组
        greater = [n for n in array[:random_index] + array[random_index+1:] if n > baseValue]
        print('本次随机使用index为{}作为基准值进行排序的结果是:'.format(str(random_index)), less, equal, greater)
    return quick_sort3(less) + equal + quick_sort3(greater)

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = quick_sort3(dest)
print('最后的结果是:', result)

'''
本次随机使用index为3作为基准值进行排序的结果是: [2, 1, 3] [4] [5, 7, 8, 6]
本次随机使用index为1作为基准值进行排序的结果是: [] [1] [2, 3]
本次随机使用index为0作为基准值进行排序的结果是: [] [2] [3]
本次随机使用index为1作为基准值进行排序的结果是: [5, 6] [7] [8]
本次随机使用index为1作为基准值进行排序的结果是: [5] [6] []
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

"""
优化方式三：
分组基准：对于上面的代码，分组基准的选取只是取列表的第一个值，太过于随便，当取到序列的中间值时，快排效率是最高的，第一个值未必是列表的中间值。
为了解决这个问题，我们可以选取列表中的几个值进行简单的比较，然后取这几个值的中间值作为分组基准。 
比如使用三数取中法，用来解决解决数据基本有序的（就是找到数组中最小下标，最大下标，中间下标的数字，进行比较，把中间大的数放在最左边）
"""

def quick_sort4(array):
    if len(array) < 2:  # 基线条件（停止递归的条件）
        return array
    else:
        # 递归条件
        # 三数取中法
        mid = len(array) // 2
        if array[0] > array[-1]:    # 最左大于最右的时候,交换左右
            array[0], array[-1] = array[-1], array[0]
        if array[mid] > array[-1]:  # 如果中间的>最右的,交换
            array[mid], array[-1] = array[-1], array[mid]
        if array[mid] > array[0]:   # 如果中间的>最左的,交换
            array[mid], array[0] = array[0], array[mid]
        # 把中间大的数放在最左边并且作为基准值
        baseValue = array[0]
        # 由所有小于基准值的元素组成的子数组
        less = [m for m in array[1:] if m < baseValue]
        # 包括基准在内的同时和基准相等的元素，在上一个版本的百科当中，并没有考虑相等元素
        equal = [w for w in array if w == baseValue]
        # 由所有大于基准值的元素组成的子数组
        greater = [n for n in array[1:] if n > baseValue]
        print('本次使用{}作为基准值进行排序的结果是:'.format(str(baseValue)), less, equal, greater)
    return quick_sort4(less) + equal + quick_sort4(greater)

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = quick_sort4(dest)
print('最后的结果是:', result)

'''
本次使用5作为基准值进行排序的结果是: [2, 4, 3, 1] [5] [7, 6, 8]
本次使用2作为基准值进行排序的结果是: [1] [2] [4, 3]
本次使用4作为基准值进行排序的结果是: [3] [4] []
本次使用7作为基准值进行排序的结果是: [6] [7] [8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''


"""
优化方式四：
优化小数组的交换，就是为了解决大才小用问题
原因：对于很小和部分有序的数组，快排不如插排好。
当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排

当快排达到一定深度后，划分的区间很小时，再使用快排的效率不高。当待排序列的长度达到一定数值后，可以使用插入排序。
由《数据结构与算法分析》(Mark Allen Weiness所著)可知，当待排序列长度为5~20之间，此时使用插入排序能避免一些有害的退化情形。
"""

"""
优化方式五：
尾递归优化
快排算法和大多数分治排序算法一样，都有两次递归调用。但是快排与归并排序不同，归并的递归则在函数一开始， 快排的递归在函数尾部，这就使得快排代码可以实施尾递归优化。使用尾递归优化后，可以缩减堆栈的深度，由原来的O(n)缩减为O(logn)。

尾递归概念：
如果一个函数中所有递归形式的调用都出现在函数的末尾，当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

尾递归原理：
当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。


该方式有待考究，不知道是否正确
"""


def quick_sort5(array):
    if len(array) < 2:  # 基线条件（停止递归的条件）
        return array
    else:
        # 递归条件
        baseValue = array[0]  # 选择基准值
        # 由所有小于基准值的元素组成的子数组
        less = [m for m in array[1:] if m < baseValue]
        # 包括基准在内的同时和基准相等的元素，在上一个版本的百科当中，并没有考虑相等元素
        equal = [w for w in array if w == baseValue]
        # 由所有大于基准值的元素组成的子数组
        greater = [n for n in array[1:] if n > baseValue]
        print('less:', less, ', greater:', greater)
        temp = quick_sort5(less) + equal + quick_sort5(greater)
        print('本次进行排序的结果是:', temp)
    return temp

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = quick_sort5(dest)
print('最后的结果是:', result)

'''
less: [2, 4, 1, 3] , greater: [7, 8, 6]
less: [1] , greater: [4, 3]
less: [3] , greater: []
本次进行排序的结果是: [3, 4]
本次进行排序的结果是: [1, 2, 3, 4]
less: [6] , greater: [8]
本次进行排序的结果是: [6, 7, 8]
本次进行排序的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''


"""
最终版本
一行实现快速排序
"""


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]])

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = quick_sort(dest)
print('最后的结果是:', result)

'''
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

C语言实现及优化

#include<stdio.h>
#include<stdlib.h>


int Partion(int *arr,int low,int high)       //一次找基准过程
{
    int temp = arr[low];
    while(low < high)        //当low = high时退出循环,此时的位置为基准位置
    {
        while(low < high && arr[high] > temp)
           high--;
        if(low >= high)
            break;
        else
            arr[low] = arr[high];

        while(low < high && arr[low] < temp)
            low++;
        if(low >= high)
           break;
        else
           arr[high] = arr[low];
    }
    arr[low] = temp;
    return low;
}


///*
// * 递归实现
// *
// */
void Quick(int *arr,int start,int end)
{
    int par = Partion(arr,start,end);      //一次找基准
    if(par > start+1)
        Quick(arr,start,par - 1);
    if(par < end - 1)
        Quick(arr,par+1,end);
    return;
}
//
//
void Quick_Sort1(int *arr,int  len)      //len为数组的长度
{
    Quick(arr,0,len-1);
    return;
}
//
//
///*
// * 非递归实现
// *
// */
//void Quick_Sort2(int *arr,int len)
//{
//    int tmpSize = (int)log((double)len)/log((double)2);
//    int *stack = (int *)malloc(sizeof(int)*tmpSize*2);     //malloc开辟动态空间
//    int top = 0;                         //数组的下标
//    int low = 0;
//    int high = len - 1;
//    int par = Partion(arr,low,high);        //第一次找基准
//    if(par > low + 1)
//    {
//        stack[top++] = low;
//        stack[top++] = par - 1;
//    }
//    if(par < high-1)
//    {
//        stack[top++] = par + 1;
//        stack[top++] = high;
//    }
//    while(top > 0)   //栈不为空
//    {
//        high = stack[--top];
//        low = stack[--top];
//        par = Partion(arr,low,high);
//        if(par > low+1)
//        {
//            stack[top++] = low;
//            stack[top++] = par - 1;
//        }
//        if(par < high-1)
//        {
//            stack[top++] = par + 1;
//            stack[top++] = high;
//        }
//    }
//    free(stack);      //释放空间
//    stack = NULL;
//}





void print_array(int *arr, int len)
{
    for(int i=0;i<len;i++)
        printf("%d ", arr[i]);
    printf("\n");
}


int main()
{
    int a[8] = {5, 2, 7, 4, 8, 1, 6, 3};
    Quick_Sort1(a, 8);
//    Quick_Sort2(a, 8);


    print_array(a, 8);


    return 0;
}