Selection Sort 與 Insertion Sort

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Selection sort

未排序數列的示意圖。指標指向第一個元素。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第一個元素。第一個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第二個元素。第一個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第二個元素。第二個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第三個元素。第二個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第四個元素。第二個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第四個元素。第四個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。指標指向第五個元素。第四個元素以橘色標示。

找出最小值

Selection sort

未排序數列的示意圖。第四個元素以橘色標示。兩個箭頭表示第一個與第四個元素將交換。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一個元素以橘色標示。第一與第四個元素已交換。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一個元素為藍色，第二個為橘色。指標指向第二個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一個元素為藍色，第二個為橘色。指標指向第三個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一個元素為藍色，第二個為橘色。指標指向第四個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一個元素為藍色，第二個為橘色。指標指向第五個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色。指標指向第三個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色，第三個為橘色。指標指向第三個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色，第三個為橘色。指標指向第四個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色，第四個為橘色。指標指向第四個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色，第四個為橘色。指標指向第五個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色，第四個為橘色。兩個箭頭表示第三與第四個項目將交換。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一與第二個元素為藍色，第三個為橘色。第三與第四個項目已交換。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。指標指向第四個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三個元素為藍色，第四個為橘色。指標指向第四個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三個元素為藍色，第四個為橘色。指標指向第五個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三個元素為藍色，第五個為橘色。指標指向第五個元素。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三個元素為藍色，第五個為橘色。兩個箭頭表示第四與第五個元素將交換。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三個元素為藍色，第四個為橘色。第四與第五個元素已交換。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。第一、第二、第三、第四個元素為藍色。

找出最小值
將最小值與第一個未排序元素交換

Selection sort

未排序數列的示意圖。所有元素為藍色。

找出最小值
將最小值與第一個未排序元素交換

Selection sort - 實作

def selection_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length - 1):

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

Selection sort - 複雜度

最差情況：$O(n^2)$
平均情況：$\Theta(n^2)$
最佳情況：$\Omega(n^2)$

Insertion sort

未排序數列的示意圖。

Insertion sort

未排序數列的示意圖。第一個元素為藍色，第二個元素被抬起。

Insertion sort

未排序數列的示意圖。第一個元素為藍色，第二個元素被抬起。第一個元素已右移。

Insertion sort

未排序數列的示意圖。第二個元素為藍色。被抬起的元素現在在第一個位置。

Insertion sort

未排序數列的示意圖。第一與第二個元素為藍色。

Insertion sort

未排序數列的示意圖。第一與第二個元素為藍色。第三個元素被抬起。

Insertion sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。

Insertion sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。第三個元素被抬起。

Insertion sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。第三個元素被抬起並已右移。

Insertion sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。第三個元素被抬起。第三與第二個元素已右移。

Insertion sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。第三個元素被抬起。第三、第二與第三個元素已右移。

Insertion sort

未排序數列的示意圖。第一、第二、第三個元素為藍色。第三個元素被抬起。第三、第二與第三個元素已右移。被抬起的元素現在在第一個位置。

Insertion sort

未排序數列的示意圖。第一、第二、第三、第四個元素為藍色。

Insertion sort

未排序數列的示意圖。第一、第二、第三、第四個元素為藍色。第五個元素被抬起。

Insertion sort

未排序數列的示意圖。第一、第二、第三、第四個元素為藍色。第五個元素被抬起。第四個元素已右移。

Insertion sort

未排序數列的示意圖。第一、第二、第三、第四個元素為藍色。第五個元素被抬起。被抬起的元素現在在第四個位置。

Insertion sort - 實作

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

Insertion sort - 複雜度

最差情況：$O(n^2)$
平均情況：$\Theta(n^2)$
最佳情況：$\Omega(n)$

一起來練習吧！

Data Structures and Algorithms in Python