什么网站可以做问卷,个人网站网址,网站平台建设需求的意见,临沂网站制作专业一、概述快速排序(quick sort)是一种分治排序算法。该算法首先 选取 一个划分元素(partition element#xff0c;有时又称为pivot)#xff1b;接着重排列表将其 划分 为三个部分#xff1a;left(小于划分元素pivot的部分)、划分元素pivot、right(大于划分元素pivot的部分)有时又称为pivot)接着重排列表将其 划分 为三个部分left(小于划分元素pivot的部分)、划分元素pivot、right(大于划分元素pivot的部分)此时划分元素pivot已经在列表的最终位置上然后分别对left和right两个部分进行 递归排序。其中划分元素的 选取 直接影响到快速排序算法的效率通常选择列表的第一个元素或者中间元素或者最后一个元素作为划分元素当然也有更复杂的选择方式划分 过程根据划分元素重排列表是快速排序算法的关键所在。二、Python实现1. 标准实现#!/usr/bin/env python# -*- coding: utf-8 -*-def stdQuicksort(L):qsort(L, 0, len(L) - 1)def qsort(L, first, last):if first last:split partition(L, first, last)qsort(L, first, split - 1)qsort(L, split 1, last)def partition(L, first, last):# 选取列表中的第一个元素作为划分元素pivot L[first]leftmark first 1rightmark lastwhile True:while L[leftmark] pivot:# 如果列表中存在与划分元素pivot相等的元素让它位于left部分# 以下检测用于划分元素pivot是列表中的最大元素时#防止leftmark越界if leftmark rightmark:breakleftmark 1while L[rightmark] pivot:# 这里不需要检测划分元素pivot是列表中的最小元素时# rightmark会自动停在first处rightmark - 1if leftmark rightmark:# 此时leftmark处的元素大于pivot#而rightmark处的元素小于等于pivot交换二者L[leftmark], L[rightmark] L[rightmark], L[leftmark]else:break# 交换first处的划分元素与rightmark处的元素L[first], L[rightmark] L[rightmark], L[first]# 返回划分元素pivot的最终位置return rightmark2. Pythonic实现#!/usr/bin/env python# -*- coding: utf-8 -*-def pycQuicksort(L):if len(L) 1: return Lreturn pycQuicksort([x for x in L if x L[0]]) \[x for x in L if x L[0]] \pycQuicksort([x for x in L if x L[0]])
