- 冒泡排序（一轮遍历没有交换，则列表有序，排序终止） 交换排序
def BubbleSort(alist):
exchange=True
lenth=len(alist)
while lenth>0 and exchange==True:
exchange=False
for i in range(lenth-1):
if alist[i]>alist[i+1]:
alist[i],alist[i+1]=alist[i+1],alist[i]
exchange=True
lenth-=1- 选择排序（每次遍历列表只做一次交换；每次遍历找最值）交换排序
def selectionSort(alist):
lenth=len(alist)
while (lenth-1) >0:
maxPosition=0
for i in range(1,lenth):
if alist[maxPosition]<alist[i]:
maxPosition=i
alist[lenth-1],alist[maxPosition]=alist[maxPosition],alist[lenth-1]
lenth-=1- 插入排序（将新元素插入有序的子列表）移动排序
def insertSort(alist):
lenth=len(alist)
for i in range(1,lenth):
value=alist[i]
index=i-1
while index>=0 and value<alist[index]:
alist[index+1]=alist[index]
index-=1
alist[index+1]=value- ?希尔排序（“递减增量排序”；插入排序改进版，对每个子列表插入排序）
关键：如何切分列表?
def shellSort(alist):
gap=len(alist)//2
while gap>0: # 对每个子列表插入排序
for start in range(gap): # 遍历每个子列表的第一个元素
insertSort(alist,start,gap) # 对每个子列表插入排序
gap=gap//2
def insertSort(alist,start,gap): # start:给个子列表的开始位置，gap：每个子列表相邻元素在原列表的位置关系
lenth=len(alist)
for i in range(start+gap,lenth,gap): # 开始对每个子列表插入排序
index=i
value=alist[i] # 当前元素
while index>=gap and alist[index-gap]>value:
alist[index]=alist[index-gap]
index-=gap
alist[index]=value- 归并排序（分治策略、递归算法）
def mergeSort(alist): # 归并排序
#print('Splitting:',alist)
len_alist=len(alist)
if len_alist>1: # 列表元素个数<=1时，无需排序
mid=len_alist//2
left_alist=alist[:mid]
right_list=alist[mid:]
mergeSort(left_alist)
mergeSort(right_list)
# 排序+归并
i,j,k=0,0,0
len_left,len_right = len(left_alist),len(right_list)
while(i<len_left and j<len_right):
if left_alist[i]<=right_list[j]:
alist[k]=left_alist[i]
i+=1
else:
alist[k]=right_list[j]
j+=1
k+=1
if i<len_left:
alist[k:]=left_alist[i:]
if j<len_right:
alist[k:]=right_list[j:]
#print('Mering:',alist)例. 对列表进行排序
class Solution(object):
def sortList(self, head):
if head==None:
return head
tail1=head
tail2=tail1.next
tail1.next=None
list_node=[tail1]
while(tail2):
tail1=tail2
tail2=tail2.next
tail1.next=None
list_node.append(tail1)
self.mergeSort(list_node)
head=list_node[0]
tail=head
lenth=len(list_node)
for i in range(1,lenth):
tail.next=list_node[i]
tail=tail.next
return head
def mergeSort(self,list_node):
lenth_list=len(list_node)
if lenth_list>1:
mid=lenth_list//2
left=list_node[:mid]
right=list_node[mid:]
self.mergeSort(left)
self.mergeSort(right)
i,j,k=0,0,0
len_left,len_right=len(left),len(right)
while i<len_left and j<len_right:
if left[i].val<=right[j].val:
list_node[k]=left[i]
i+=1
else:
list_node[k]=right[j]
j+=1
k+=1
if i<len_left:
list_node[k:]=left[i:]
if j<len_right:
list_node[k:]=right[j:]?
- 快速排序（求解列表中最大、最小的几个数）
def QuickSort(alist,start,end):
if start>=end:
return
i=start
j=end
pivot=alist[start] # 基准值
while i<j:
if i<j and alist[j]>=pivot: # 比它小的值放在左边
j-=1
alist[i]=alist[j]
if i<j and alist[i]<pivot: # 比它大的值放在右边
i+=1
alist[j]=alist[i]
alist[i]=pivot
QuickSort(alist,start,i-1) # 一次排序后再对基准值左边序列做同样的排序
QuickSort(alist,i+1,end) # 对基准值右边的序列排序1.1??寻找列表中第k大的数
class Solution(object):
def QuickSort(self,nums,start,end,k): #倒序
i=start
j=end
pivot=nums[start]
while(i<j):
while i<j and nums[j]<=pivot:
j-=1
nums[i]=nums[j]
while i<j and nums[i]>pivot:
i+=1
nums[j]=nums[i]
nums[i]=pivot
if i+1==k: # 基准值在第k个位置
return
if i+1>k: # 目标值在基准值的左边 （比基准值大）
self.QuickSort(nums,start,i-1,k)
else:
self.QuickSort(nums,i+1,end,k) # 目标值在基准值的右边（比基准值小）
def findKthLargest(self, nums, k):
self.QuickSort(nums,0,len(nums)-1,k)
return nums[k-1]