Sorting Algorithm(I)

因为之前没有系统学data structure and algorithm,暑假亡羊补牢一下(🤦‍♀️ 把这些常规的都用python给实现一遍。先从sorting开始,sorting可以分为internal sorting和external sorting。external 指的是 all data cannot be placed in-memory at a time, 常见的external sorting algorithm有merge-sort。不过any sorting algorithm can be used to sort the data that has been loaded into memory。

下面举的例子都假设array是按照升序进行排列的。😆此外 Running time is an important thing to consider when selecting a sorting algorithm since efficiency is often though of in terms of speed。所以都尝试分析一下best time complexity和worst time complexity。

  1. Bubble Sort (internal sorting)

    Bubble Sort 是本科接触的第一个☝️排序算法, Bubble sort steps through the list and compares adjacent pairs of elements. The elements are swapped if there are in the wrong order. 但是也正是因为冒泡法从头到尾的遍历过程中需要两两相比较,如果比较的很顺利,也就是整个array其实已经是排序好了的,这时候的time complexity 就是$o(n)$,如果整个array是乱七八糟的,这时候也就是worst time complexity $o(n^2)$

    1
    2
    3
    4
    5
    6
    7
    8
    def bubbleSort(arr):
    n = len(arr)
    # traverse through all array elements
    for i in range(n):
    for j in range(0, n - i - 1):
    # traverse the array from 0 to n-i-1
    if arr[j] > arr[j + 1]:
    arr[j], arr[j + 1] = arr[j + 1], arr[j]
  2. Insertion Sort (internal sort)

    On each loop iteration, insertion sort removes one element from the array. It then finds the location where that element belongs within another sorted array and inserts it there. 我们先来看一下插入排序的pesudo code。

    Loop from i = 1 to n-1

    pick element arr[i], and insert it into the sorted sequence arr[0...i-1]

    然后再举个例子来理解,

    arr[] = 11 13 10 20

    1st loop: 11 13 10 20 (since 11< 13)

    2nd loop: 10 11 13 20 (since 10 < 11)

    3rd loop: 10 11 13 20 (since 20 > 13)

    现在我们来看一下time complexity。好的情况就是没有swap的过程,和上面bubble一样,整个array其实已经是排序好了的,所以best time complexity $o(n)$ 。坏的情况就是我们需要的是升序的,但一开始的array是降序排列的, # opertaion = n(n-1) 所以worst time complexity $o(n^2)​$

    1
    2
    3
    4
    5
    6
    7
    8
    def insertion_sort(arr):
    for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
    arr[j], arr[j + 1] = arr[j + 1], arr[j]
    j = j - 1
    return arr
  3. Selection Sort (internal sort)

    The algorithm maintains two subarrays in a given array. 1)The subarray which is already sorted 2) Remaining subarray which is unsorted。也就是我们把一个数组分为已经排列整齐的 和 乱七八糟的两类。在乱七八糟的那一部分找到一个最小的元素,把它放到已经排列好的那一部分的数组中正确的位置中去。

    用上面同样的例子来理解一下

    arr[] = 11 13 10 20

    10 // find the minimum element in arr[0…3] put at the beginning

    10// sorted 11 13 20// unsorted

    11 // find the minimum element in arr[1…3] put at the second place

    10 11 //sorted 13 20 // unsorted

    13 // find the minimum element in arr[2..3] put at the third place

    then we get 10 11 13 20

    1
    2
    3
    4
    5
    6
    7
    8
    def selection_sort(arr):
    for i in range(len(arr)):
    minimal = i
    for j in range(i + 1, len(arr)):
    if arr[j] < arr[minimal]:
    minimal = j
    arr[minimal], arr[i] = arr[i], arr[minimal]
    return arr
---------------------- 本文结束----------------------