Pyhton快速排序

有几下几种 Pyhton快速排序方法

<pre class="brush:python;toolbar:false">def quick_sort(num_list,repeat=False):
 if len(num_list) < 2:
 return num_list
 else:
 basenum = num_list[0]
 if repeat:
 left = [x for x in num_list[1:] if x <= basenum]
 else:
 left = [x for x in num_list[1:] if x < basenum]
 right = [x for x in num_list[1:] if x > basenum]
 return quick_sort(left,repeat) + [basenum] + quick_sort(right,repeat)

sql = [5, 3, 4, 1, 4, -2, 8, 7, 5, 9]
#去重
print(quick_sort(sql))
#[-2, 1, 3, 4, 5, 7, 8, 9]

#不去重
print(quick_sort(sql,True))
#[-2, 1, 3, 4, 4, 5, 5, 7, 8, 9]</pre>

 

<pre class="brush:python;toolbar:false">def quick_sort(array, start, end):
 if start >= end:
 return
 mid_data, left, right = array[start], start, end
 while left < right:
 while array[right] >= mid_data and left < right:
 right -= 1
 array[left] = array[right]
 while array[left] < mid_data and left < right:
 left += 1
 array[right] = array[left]
 array[left] = mid_data
 quick_sort(array, start, left-1)
 quick_sort(array, left+1, end)
 
 
if __name__ == '__main__':
 array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
 quick_sort(array, 0, len(array)-1)
 print(array)
 #[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]</pre>

 其它从网上摘的

<pre class="brush:python;toolbar:false">def quick_sort(array, l, r):
 if l < r:
 q = partition(array, l, r)
 quick_sort(array, l, q - 1)
 quick_sort(array, q + 1, r)
 
def partition(array, l, r):
 x = array[r]
 i = l - 1
 for j in range(l, r):
 if array[j] <= x:
 i += 1
 array[i], array[j] = array[j], array[i]
 array[i + 1], array[r] = array[r], array[i+1]
 return i + 1</pre>
<pre class="brush:python;toolbar:false">def quick_sort(lists,i,j):
 if i >= j:
 return list
 pivot = lists[i]
 low = i
 high = j
 while i < j:
 while i < j and lists[j] >= pivot:
 j -= 1
 lists[i]=lists[j]
 while i < j and lists[i] <=pivot:
 i += 1
 lists[j]=lists[i]
 lists[j] = pivot
 quick_sort(lists,low,i-1)
 quick_sort(lists,i+1,high)
 return lists
 
if __name__=="__main__":
 lists=[30,24,5,58,18,36,12,42,39]
 print("排序前的序列为：")
 for i in lists:
 print(i,end =" ")
 print("\n排序后的序列为：")
 for i in quick_sort(lists,0,len(lists)-1):
 print(i,end=" ")>>>排序前的序列为：30 24 5 58 18 36 12 42 39排序后的序列为：5 12 18 24 30 36 39 42 58</pre>

 

<pre class="brush:python;toolbar:false">def quick_sort(num_list):
 #4.主函数调用，
 q_sort(num_list,0,len(num_list)-1)
 #5.调用q_sort()函数，实参 n_list列表，首项序列，最后元素序列传入

def q_sort(num_list,first,last):
 #6.传入实参给形参
 if first < last:
 #7.条件判断，
 split = partition(num_list,first,last)
 #8.调用函数partition(),传入n_list，首项序列，末项序列实参
 q_sort(num_list,first,split - 1)
 #递推，判断划分元素
 q_sort(num_list,split + 1,last)
 #递推

def partition(num_list,first,last):
 #9.传入实参给形参
 pivot = num_list[first]
 #10.选取列表中的第一个元素作为划分元素
 left_mark = first + 1
 #11.左坐标向右移动一格
 right_mark = last
 #右坐标为末项序列
 while True:
 while num_list[left_mark] <=pivot:
 #当左坐标元素小于等于划分元素时，左坐标自增1(从左到右序列+1)}|若列表中|
 if left_mark == right_mark:
 #如果左坐标等于右坐标时退出当前while循环
 break
 left_mark +=1
 while num_list[right_mark] > pivot:
 #当右坐标元素大于划分元素时，右坐标自减1，(从右到左序列-1)
 right_mark -= 1
 if left_mark < right_mark:
 #如果左坐标所在元素大于划分元素，右坐标元素小于划分元素，交换两个坐标所指的元素
 num_list[left_mark],num_list[right_mark] = num_list[right_mark],num_list[left_mark]
 else:
 break
 #左坐标超过了右坐标，退出当前循环
 num_list[first],num_list[right_mark] = num_list[right_mark], num_list[first] #交换first处的划分元素和右坐标处的元素
 return right_mark

n_list = [1,5,567,9,1,7] #1.生成列表
print(f'before:{n_list}')#2.打印当前序列
quick_sort(n_list)#3.调用quick_sort()函数，传入n_list实参
print(f'After:{n_list}')
print(f'use function sorted:{sorted(n_list)}')

before:[1, 5, 567, 9, 1, 7]
After:[1, 9, 567, 1, 5, 7]
use function sorted:[1, 1, 5, 7, 9, 567]</pre>