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

  1. #!/usr/bin/env python
  4. def selectionSort(alist):
  5.     for i in xrange(len(alist)):
  6.         print(alist)
  7.         min_index = i
  8.         for j in xrange(i + 1, len(alist)):
  9.             if alist[j] < alist[min_index]:
  10.                 min_index = j
  11.         alist[min_index], alist[i] = alist[i], alist[min_index]
  12.     return alist
  14. unsorted_list = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
  15. print(selectionSort(unsorted_list))

Java

  1. public class Sort {
  2.     public static void main(String[] args) {
  3.         int unsortedArray[] = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
  4.         selectionSort(unsortedArray);
  5.         System.out.println("After sort: ");
  6.         for (int item : unsortedArray) {
  7.             System.out.print(item + " ");
  8.         }
  9.     }
  11.     public static void selectionSort(int[] array) {
  12.         int len = array.length;
  13.         for (int i = 0; i < len; i++) {
  14.             for (int item : array) {
  15.                 System.out.print(item + " ");
  16.             }
  17.             System.out.println();
  18.             int min_index = i;
  19.             for (int j = i + 1; j < len; j++) {
  20.                 if (array[j] < array[min_index]) {
  21.                     min_index = j;
  22.                 }
  23.             }
  24.             int temp = array[min_index];
  25.             array[min_index] = array[i];
  26.             array[i] = temp;
  27.         }
  28.     }
  29. }

Reference