排序之一：选择排序

• 介绍
  选择排序法第一次扫描会找出最大或者最小值，放到正确的位置；第二次扫描会在剩余数据找出最大或者最小值，放到正确位置；以此类推，直到扫描完成；
• 演示
  代码如下：

private static void selectSort() {
    int data[] = {6, 4, 8, 1, 3, 7, 2, 9, 5};
    int i, j, tmp;
    for (i = 0; i < data.length - 1; i++) {
        for (j = i + 1; j < data.length; j++) {
            if (data[i] > data[j]) {
                tmp = data[j];
                data[j] = data[i];
                data[i] = tmp;
            }
        }
    }
}

打印结果：

选择排序打印结果.png

• 分析

1. 无论是最坏情况、最佳情况还是平均情况都需要找到最大值（或最小值），因此其比较次数为n(n-1)/2次；时间复杂度为O(n²);
2. 由于选择排序是以最大或最小值直接与最前方未排序的键值交换，数据排序顺序很有可能被改变，所以不是稳定排序法；
3. 只需要一个额外的控件，所以空间复杂度为最佳；
4. 此排序法适用于数据量小或者有部分数据已经排序过的情况。

其他排序：插入排序、冒泡排序、希尔排序、快速排序、基数排序