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

冒泡排序(Bubble Sort)

  • 核心思想:按从小到大的排序,前面一个数和后面一个数比较,大的永远靠后,每次可以确定一个最大的数排到了最后,然后下次比较就可以忽略这个排好的数。
  • 伪代码
    
    do
      swapped = false
      for i = 1 to indexOfLastUnsortedElement
          if leftElement > rightElement
              swap(leftElement, rightElement)
              swap = true
    while swapped
    
    
  • GIF process
  • Python code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    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))

References