Selection Sort - 选择排序-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

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

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

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

代码示例：
Python
```asp
#!/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))
```
Java
```asp
public class Sort {
    public static void main(String[] args) {
        int unsortedArray[] = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
        selectionSort(unsortedArray);
        System.out.println("After sort: ");
        for (int item : unsortedArray) {
            System.out.print(item + " ");
        }
    }

public static void selectionSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {
            for (int item : array) {
                System.out.print(item + " ");
            }
            System.out.println();
            int min_index = i;
            for (int j = i + 1; j < len; j++) {
                if (array[j] < array[min_index]) {
                    min_index = j;
                }
            }
            int temp = array[min_index];
            array[min_index] = array[i];
            array[i] = temp;
        }
    }
}
```

该分类下的相关小册推荐：

业务开发实用算法精讲

数据结构与算法(下)

数据结构与算法之美

算法面试通关 50 讲

数据结构与算法(上)

编程之道-算法面试(上)

编程之道-算法面试(下)