排序（冒泡、選擇、插入、希爾、歸并、快排）

• 冒泡排序（一輪遍歷沒有交換，則串列有序，排序終止） 交換排序

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]