十种经典排序算法

Posted on | Edited on | In | Comments:

1. 冒泡排序（Bubble Sort）

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs and swaps) them if they are in the wrong order.

物理模拟的理论源头.

1.1 Pseudocodes Implementation

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
30
#basics 
procedure bubbleSort(A : list of sortable items )
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap( A[i-1], A[i] )
                swapped = true
            end if
        end for
    until not swapped
end procedure

#improved 
procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end procedure

1.2 动图演示
img

1.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# compare to get the small and swap 
# repeat
def bubble_sort1(arr):
    for _ in range(len(arr)): #cumbersome loop
        # core logic 
        for i in range(1, len(arr)):
            if arr[i] < arr[i-1]:
                temp = arr[i-1] #目标位置.
                arr[i-1] = arr[i]
                arr[i] = temp #swap的逻辑可以先写后面的两行。

def bubble_sort2(arr):
    #上浮和下沉
    while True:
        swap_counter = 0
        for i in range(1, len(arr)):
            if arr[i] < arr[i-1]: #move smaller up 
                arr[i-1], arr[i] = arr[i], arr[i-1]
                swap_counter += 1
        if swap_counter == 0:
            return

2. 插入排序 Insertion Sort，　

关键点是将第一项作为sorted sequence的分析方法.

2.1 Psedocodes

1
2
3
4
5
6
7
8
9
i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

2.2 动态演示

Sorted Make room
Insertion sort.gif

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#psudocodes 
Move the pivot entry to a temporary location leaving a hole in List
while (there is a name above the hole and
that name is greater than the pivot):
move the name above the hole down into the hole
leaving a hole above the name
Move the pivot entry into the hole in List.

#解决方案只保留一项, 越少越好. 
#in-place的实现
def insertion_sort(arr):#这个思路是最清晰的.
    for i in range(1, len(arr)):
        #将当前的pivot拿出 
        pivot = arr[i] #Move the pivot to a temporay location,
        hole = i # and leave a hole
        #找到比当前值大的,然后下沉. hole>0是因为第一项已经排好了.
        while hole > 0 and arr[hole-1] > pivot:
            #当上面有更大的,下沉, 因为是排序好的，所以想象lock整体下沉。
            #
            arr[hole] = arr[hole-1] #下沉填充hole
            hole  = hole- 1 #leave the hole,两步操作.
        arr[hole] = pivot #insert sort就是这么来的.
    return arr

3. 选择排序 Selection Sort

Psuedocodes: 从剩下的序列中选择最小值， 逐个浮上来。

3.1 算法描述

There are many different ways to sort the cards. Here’s a simple one, called selection sort, possibly similar to how you sorted the cards above:

  1. Find the smallest card. Swap it with the first card.
  2. Find the second-smallest card. Swap it with the second card.
  3. Find the third-smallest card. Swap it with the third card.
  4. Repeat finding the next-smallest card, and swapping it into the correct position until the array is sorted.

3.2 动图演示

Effects Demonstration
Selection sort animation.gif

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#要输出的是new_arr
def selection_sort3(arr):　＃基本思路．
    arr = list(arr)
    new_arr = []
    while arr:
        minimum = min(arr)
        new_arr.append(arr.pop(minimum))
    return new_arr

def selection_sortA(nums): #selection排序的核心是从subarray中找打最小值.
    for i in range(len(nums)-1): #从subarray的第一项开始
        min_idx = i #设置min_idx的初始值．
        for j in range(i+1, len(nums)):#从subarray中选出最小值
            if nums[j] < nums[min_idx]: #不断更新
                min_idx = j #找到最小值的index,只进行index操作.
        #循环终止后, i是当前值, 
        #swap the current value and the minial value
        temp = nums[i]
        nums[i] = nums[min_idx]
        nums[min_idx] = temp

3.4 希尔排序(Shell Sort)

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现。

等闲来无事再来了解．

4. 归并排序 (Merge Sort)

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumannin 1945.[2] A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and von Neumann as early as 1948.[3]

4.1 Pseudocodes

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#Top-down implementation 
function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

#Bottom-up Implementation 
function merge_sort(node head)
    // return if empty list
    if (head == nil)
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result = head
    // merge nodes into array
    while (result != nil)
         next = result.next;
         result.next = nil
         for(i = 0; (i < 32) && (array[i] != nil); i += 1)
              result = merge(array[i], result)
              array[i] = nil
         // do not go past end of array
         if (i == 32)
               i -= 1
         array[i] = result
         result = next
    // merge array into single list
    result = nil
    for (i = 0; i < 32; i += 1)
         result = merge(array[i], result)
    return result

4.2 动图演示

File:Merge sort animation2.gif
enter image description here

4.3 Implementation

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#psuedocodes方案
from heapq import merge
def merge_sort1(m): #Postoder
    #LRN遍历, 
    if len(m) <= 1:
        return m
    mid = len(m) // 2
    left = merge_sort1(m[:mid])
    right = merge_sort1(m[mid:])
    result = list(merge(left, right))
    return result

#step by step soluthon 
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
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result
def mergeSort(L):
    if len(L) < 2:
        return L[:]
    else:
        left = mergeSort(L[:mid])
        right = mergeSort(L[mid:])
        return merge(left, right)
    #我的时间管理可能应该是tree的结构.

 #in-place merge sort
def merge_inplace(A, start, mid, end) -> "None":
    left = A[start:mid]
    i = 0
    j = 0
    
    for c in range(start, end): #c for cur
        if j >= len(right) or (i < len(left) and left[i] < right[j]): #注意shortcuit的问题.
            A[c] = left[i]
            i = i + 1
        else:
            A[c] = right[j]
            j = j + 1

def mergeSort_inplace(A, lo, hi) -> "None":
    if lo < hi - 1:
        mid = (lo + hi) // 2
        mergeSort_inplace(A,lo,mid)
        mergeSort_inplace(A,mid,hi)
        merge_inplace(A, lo, mid, hi)

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

归并算法的代价就是需要额外的存储空间.

5. 快速排序（Quick Sort）

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of a random access file or an array in order. Developed by British computer scientist Tony Hoarein 1959[1] and published in 1961,[2] it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.[3][contradictory]

5.1 算法描述

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively) apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

5.2 动图演示

Effects Demonstration
Selection sort animation.gif

5.3 Implementation

1
2
3
4
5
6
7
8
def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)