排序算法总结 | In Web3

排序算法是一个非常重要而且在日常生活中最常用的一种算法之一。面试官往往也是会常考的题目。所以，以下对排序算法做一下总结，而且排序顺序都是由小到大。

冒泡排序(Bubble Sort)

核心思想：按从小到大的排序，前面一个数和后面一个数比较，大的永远靠后，每次可以确定一个最大的数排到了最后，然后下次比较就可以忽略这个排好的数。

伪代码


do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement
      if leftElement > rightElement
          swap(leftElement, rightElement)
          swap = true

while swapped

GIF process

Python code

def bubbleSort(alist):  
    for passnum in range(len(alist)-1,0,-1):  
        #print alist,passnum  
        for i in range(passnum):  
            if alist[i]>alist[i+1]:  
                temp = alist[i]  
                alist[i] = alist[i+1]  
                alist[i+1] = temp  
    return alist

alist = [54,26,93,17,77,31,44,55,20]  
print(bubbleSort(alist))

选择排序(Select Sort)

核心思想：从左往右，设还没排序的数中的第一个数为最小的数(minimum)，并且记住最小数(minimum)的下标(index)，然后和它后面的所有数进行比较，如果发现有更小的数，就更新下标，比完一轮之后，如果下标有改变，就把下标位置上的数和第一个数进行交换，那么这个数就是已排序的了，往下移一个位置继续以上的动作，直到最后要给数为止。

伪代码


repeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
  if element < currentMinimum
    set element as new minimum
swap minimum with first unsorted position

GIF proce

Python code

def selectionSort(alist):  
    for i in range(len(alist)-1):  
        minimun = i
        for j in range(i, len(alist)):
            if alist[j]<alist[minimun]:  
                minimun = j  
        temp = alist[i]   
        alist[i] = alist[minimun]  
        alist[minimun] = temp   
    return alist

alist = [54,26,93,17,77,31,44,55,20]  
print(selectionSort(alist))

快速排序(Quick sort)

核心思想：
- 选定一个基准值(pivot)
- 将比基准值(pivot)小的数移到它的左边，形成左子序列
- 将比基准值(pivot)大的数移到它的右边，形成右子序列
- 分别对左子序列、右子序列作上述三个步骤,直到左子序列和右子序列都只剩一个数为止==》递归(Recursive)

伪代码：


for each (unsorted) partition
set first element as pivot
storeIndex = pivotIndex + 1
for i = pivotIndex + 1 to rightmostIndex
  if element[i] < element[pivot]
    swap(i, storeIndex); storeIndex++
swap(pivot, storeIndex - 1)

GIF process

Python code

def quickSort(arr, left, right):
    # 只有left < right 排序
    if left < right:
        pivot_index = partition(arr, left, right)
        quickSort(arr, left, pivot_index - 1)
        quickSort(arr, pivot_index + 1, right)


def partition(arr, left, right):
    """找到基准位置, 并返回"""
    pivot_index = left
    pivot = arr[left]

    for i in range(left + 1, right + 1):
        if arr[i] < pivot:
            # 如果此处索引的值小于基准值, 基准值的位置后移一位
            # 并将后移一位的值和这个值交换, 让基准位置及之前的始终小于基准值
            pivot_index += 1
            if pivot_index != i:
                arr[pivot_index], arr[i] = arr[i], arr[pivot_index]

    # 将基准值移动到正确的位置
    arr[left], arr[pivot_index] = arr[pivot_index], arr[left]

    return pivot_index

alist = [54,26,93,17,77,31,44,55,20] 
quickSort(alist, 0, len(alist)-1) 
print(alist)

插入排序(Insert sort)

核心思想：在已排序的数中插入一个未排序的数。

伪代码


mark first element as sorted
for each unsorted element
'extract' the element
for i = lastSortedIndex to 0
  if currentSortedElement > extractedElement
    move sorted element to the right by 1
  else: insert extracted element

GIF process

Python code

def insertSort(a):  
    for i in range(len(a)-1):  
        #print a,i    
        for j in range(i+1,len(a)):  
            if a[i]>a[j]:  
                temp = a[i]  
                a[i] = a[j]  
                a[j] = temp  
    return a
alist = [54,26,93,17,77,31,44,55,20]  
print(insertSort(alist))

归并排序

核心思想：把原始数组分成若干子数组,对每一个子数组进行排序,
继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组

伪代码：


split each element into partitions of size 1
recursively merge adjancent partitions
  for i = leftPartStartIndex to rightPartLastIndex
  inclusive
      if leftPartHeadValue <= rightPartHeadValue
          copy leftPartHeadValue
      else: copy rightPartHeadValue

copy elements back to original array

GIF process

Python code

def mergesort(seq):  
    if len(seq)<=1:  
        return seq  
    mid=int(len(seq)/2)  
    left=mergesort(seq[:mid])  
    right=mergesort(seq[mid:])  
    return merge(left,right)  
  
def merge(left,right):  
    result=[]  
    i,j=0,0  
    while i<len(left) and j<len(right):  
        if left[i]<=right[j]:  
            result.append(left[i])  
            i+=1  
        else:  
            result.append(right[j])  
            j+=1  
    result+=left[i:]  
    result+=right[j:]  
    return result     

alist = [54,26,93,17,77,31,44,55,20] 
print(mergesort(alist))

冒泡排序(Bubble Sort)

选择排序(Select Sort)

快速排序(Quick sort)

插入排序(Insert sort)

归并排序

References