本文共 3187 字，大约阅读时间需要 10 分钟。
1.快速排序的思想
（1）分解：先从数列中取出一个元素作为基准元素，以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列位于左侧，使大于基准元素的子序列位于右侧。 （2）治理：对两个子序列分别递归调用快速排序。 （3）合并：将拍好序的两个子序列合并在一起，得到原问题的解。 上一篇的合并排序又叫归并排序，它每次从中间位置把问题一分为二，一直划分到不能再分为止，然后执行合并操作。合并排序的划分简单，但是合并操作复杂。快速排序刚好相反，分解困难，合并简单。 2.步骤分析 假设待排序的序列为R[low:high],low<=high。 （1）首先取列表中的第一个元素作为基准元素pivot=R[low]。i=low,j=high。 （2）从右向左扫描，找小于等于pivot的数，如果找到，R[i]和R[j]交换，i加1。 （3）从左向右扫描，找大于pivot的数，如果找到，R[i]和R[j]交换，j减1。 （4）重复步骤2~3，直到i==j,返回该位置mid=i,该位置的数正好是pivot元素。 这样就完成了一趟排序也叫一次划分。以mid为界，将原数据分为两个子序列，左侧子序列元素都比pivot小，右侧子序列都比pivot大，然后再分别对这两个子序列进行快速排序。 3.代码实现 3.1根据2.步骤分析可编写如下代码：def Partition(r,low,high): '''划分函数''' i = low j = high pivot = r[low] #基准元素 while(i < j): while i < j and r[j] > pivot: #向左扫描 j -= 1 if i < j: r[i],r[j] = r[j],r[i] #r[i],r[j]交换位置 i += 1 #i右移一位 while(i < j and r[i] <= pivot): #向右扫描 i += 1 if i < j: r[i], r[j] = r[j], r[i] #r[i],r[j]交换位置 j -= 1 #j左移一位 return i #返回最终划分完成后基准元素所在的位置def QuickSort(R,low,high): '''快速排序递归算法''' if low < high: mid = Partition(R,low,high) #返回基准元素位置 QuickSort(R,low,mid-1) #左区间递归快速排序 QuickSort(R,mid+1,high) #右区间递归快速排序if __name__ == '__main__': a = [] n = int(input('请先输入要排序的数据个数n：')) for i in range(n): a.append(int(input('请依次输入要排序的数据：'))) print('要排序的序列为：') print(a) QuickSort(a,0,n-1) print('排好序后的序列为：') for i in range(n): print(a[i],'\t',end='') 运行结果：
请先输入要排序的数据个数n：9请依次输入要排序的数据：26请依次输入要排序的数据：30请依次输入要排序的数据：9请依次输入要排序的数据：60请依次输入要排序的数据：18请依次输入要排序的数据：36请依次输入要排序的数据：7请依次输入要排序的数据：50请依次输入要排序的数据：33要排序的序列为：[26, 30, 9, 60, 18, 36, 7, 50, 33]排好序后的序列为：7 9 18 26 30 33 36 50 60
3.2优化
优化思想：上述过程我们发现每次交换都是在和基准元素进行交换，所以考虑可以从右向左扫描，找小于等于pivot的数R[j],然后从左向右扫描，找大于pivot的数R[i]，让R[i]和R[j]交换，一直交替进行，直到i==j为止，这时再将基准元素与R[i]交换即可。从而完成一次划分，但是交换元素的个数少了很多。 代码实现：def Partition2(r,low,high): '''划分函数''' i = low j = high pivot = r[low] #基准元素 while(i < j): while i < j and r[j] > pivot: #向左扫描 j -= 1 while i < j and r[i] <= pivot: #向右扫描 i += 1 if i < j: r[i],r[j] = r[j],r[i] #r[i]和r[j]交换，交换后i加1，j加1 i += 1 j -= 1 if r[i] > pivot: r[i-1],r[low] = r[low],r[i-1] #r[i-1]和r[low]交换 return i-1 ##返回最终划分完成后基准元素所在的位置 r[i],r[low] = r[low],r[i] #r[i]和r[low]交换 return i #返回最终划分完成后基准元素所在的位置def QuickSort(R,low,high): '''快速排序递归算法''' if low < high: mid = Partition2(R,low,high) #返回基准元素位置 QuickSort(R,low,mid-1) #左区间递归快速排序 QuickSort(R,mid+1,high) #右区间递归快速排序if __name__ == '__main__': a = [] n = int(input('请先输入要排序的数据个数n：')) for i in range(n): a.append(int(input('请依次输入要排序的数据：'))) print('要排序的序列为：') print(a) QuickSort(a,0,n-1) print('排好序后的序列为：') for i in range(n): print(a[i],'\t',end='') 运行结果：
请先输入要排序的数据个数n：9请依次输入要排序的数据：31请依次输入要排序的数据：27请依次输入要排序的数据：96请依次输入要排序的数据：8请依次输入要排序的数据：72请依次输入要排序的数据：56请依次输入要排序的数据：22请依次输入要排序的数据：68请依次输入要排序的数据：12要排序的序列为：[31, 27, 96, 8, 72, 56, 22, 68, 12]排好序后的序列为：8 12 22 27 31 56 68 72 96
转载地址：http://encii.baihongyu.com/