python实现快速排序

快速排序定义：

在这里插入图片描述

过程分析：

我们还是用为例子，__[54,26,93,17,77,31,44,55,20]__为例子：

依据：根据快速排序原理知道，先找到一个元素，然后划分

成左边比规定元素小，右边比规定元素大的目的

首先low指向第一个元素，high指向最后一个元素，我们先以54（alist[0]）为划分元素

（1）首先我们判断high指针指向的元素，20比54要小所以需要将20赋值到low上面，此时54已经被覆盖

（2）此时再看low指针指向元素20比54小，所以将low向右移动，直到找到元素比54大停止增加low指针，此时low停在了

93的位置，然后我们把93放在后面，也就是让alist【high】=93

（3）再看high指向，93比54大，所以指针移动，知道找到比54小的元素，停止移动。此时high指向44.把44移动到前面，即进行alist【low】=44

（4）再看low指向的元素44比54小，继续移动low，直到找到比54大的元素77，此时把77放在后面，alist【high】=77

（5）再看high指向元素77比54大，移动high，high移动到31比54小，所以把31放在前面，alist【low】=31

（6）再看low指向元素31比54小所以移动low，而再次移动low以后，highlow了，就划分完毕了，此时我们就要把规定元素放在这个highlow的地方了。这样第一次划分就完毕了！

然后就需要通过递归算法，将左边，右边的列表在一次进行快速排序，最后递归终止条件就是first>=last

这里说明一下为啥要用到参数first和last，因为我们想要通过递归来完成划分好的序列而我们不可以用alist【low-+1：】和【：low-1】因为这样就变成了两个不同序列，就不再操作原来的alist序列了，为了让我们操作原来的alist序列就必须来设置参数来操作在alist划分好的两个序列了。

图形理解：

在这里插入图片描述

这里的图片与上面分析的无关如果想要深刻理解这一过程建议读者通过word里面的图形来自己模拟上面分析的过程，

附加图word分析：

代码实现：

def quick_sort(alist,first,last):    """快速排序"""    if first>=last:        return    mid_value=alist[first]    low=first    high=last    while low
   
    =mid_value:            high-=1        alist[low]=alist[high]        #low右移        while low

时间复杂度：

在这里插入图片描述

c语言实现

#include
   
    int a[101],n;void quicksort(int left,int right){
   int i,j,temp,t;if(left>right)    return;temp=a[left];//基准数i=left;j=right;while(i!=j){
       while(a[j]>=temp&&i

转载地址：http://nrgzi.baihongyu.com/

你可能感兴趣的文章