快速排序c++和python对比分析

C++的快速排序基本思想就是,任意取出一位作为对比位x,分别从序列两端开始探测,先从右边到左找到一个比x大的数,在从左边到右找到一个比x小的数,然后交换他们,一直循环到i=j。这一次交换完毕之后,将x换到中间位置,因为左边都比它小,右边都比它大,所以它在中间。在函数最后,有一个递归函数,分别在对左边和右边进行刚才的排序,直到将元素分解到1个的时候停止,,循环结束。

void quicksort(int left,int right){int i,j,t,temp;if(left>right)return;temp = a[left];i = left;j = right;while(i!=j){while(a[j]>=temp && i<j)j–;while(a[i]<=temp && i<j)i++;if(i<j){t = a[i];a[i] = a[j];a[j] = t;}}a[left] = a[i];a[i] = temp;quicksort(left,i-1);quicksort(i+1,right);}

python中的快速排序实现思想类似,但是代码会简单一点,开始的时候创建两个列表元素,从队列中取出一个元素x,将整个队列循环遍历一遍,将小于取出x的元素放在less中,将大于x的元素放在greater里。最后返回一个递归的表达式。

def quicksort(array):less = []greater = []if len(array) <= 1:return arraypivot = array.pop()for x in array:if x <= pivot: less.append(x)else: greater.append(x)return quicksort(less) + [pivot] + quicksort(greater)

若不给自己设限,则人生中就没有限制你发挥的藩篱。

快速排序c++和python对比分析

相关文章:

你感兴趣的文章:

标签云: