Selection Sort - 选择排序

核心：不断地选择剩余元素中的最小者。

  1. 找到数组中最小元素并将其和数组第一个元素交换位置。
  2. 在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序。

性质：

  • 比较次数=(N-1)+(N-2)+(N-3)+...+2+1~N^2/2
  • 交换次数=N
  • 运行时间与输入无关
  • 数据移动最少

下图来源为 File:Selection-Sort-Animation.gif - IB Computer Science

Selection Sort

Implementation

Python

#!/usr/bin/env python


def selectionSort(alist):
    for i in xrange(len(alist)):
        print(alist)
        min_index = i
        for j in xrange(i + 1, len(alist)):
            if alist[j] < alist[min_index]:
                min_index = j
        alist[min_index], alist[i] = alist[i], alist[min_index]
    return alist

unsorted_list = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
print(selectionSort(unsorted_list))

[8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
[0, 5, 2, 6, 9, 3, 1, 4, 8, 7]
[0, 1, 2, 6, 9, 3, 5, 4, 8, 7]
[0, 1, 2, 6, 9, 3, 5, 4, 8, 7]
[0, 1, 2, 3, 9, 6, 5, 4, 8, 7]
[0, 1, 2, 3, 4, 6, 5, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Reference

results matching ""

    No results matching ""