30天挑战数据结构和算法之第2天选择排序

今天挑战的内容是选择排序，其实我之前分不太清楚什么是选择排序。看了一遍visualgo.net上的演示后才知道，它的本质思想是循环找到最小的数然后交换到第一个未排序的位置，以此类推。

下面是visualgo.net上的伪代码

repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

如果用javascript实现的话

function MySelectionSort() {
    this.sort = function(array) {
        for (var i = 0; i < array.length - 1; i++) {
            var min = i;
            for (var j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            if (i != min) {
                var temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
        return array;
	}
}

var sorter = new MySelectionSort();
var notSortedArr = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19];
var sortedArr = sorter.sort(notSortedArr);
console.log(sortedArr);

下面是ruby的实现

def my_selection_sort(array)
    0.upto(array.size - 1) do |i|
        min = i
        (i+1).upto(array.size - 1) do |j|
            min = j if array[j] < array[min]
        end
        array[i], array[min] = array[min], array[i] if i != min
    end
end

list = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19]
my_selection_sort(list)
print list, "\n"

最后是java的实现

import java.util.Arrays;

public class MySelectionSort {
    
    private static void sort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            int j = i + 1;
            for (; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            if (min != i) {
            	int temp = array[i];
            	array[i] = array[min];
            	array[min] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19};
        sort(arr);
        System.out.println(Arrays.toString(arr));	
    }
}

来计算一下时间复杂度。

外层循环：(n-1)+(n-2)+(n-3)+...+3+2+1=Sn

内层循环：1+2+3+...+(n-3)+(n-2)+(n-1)=Sn

两式相加2Sn=n+n+n+...+n+n+n，一共n-1个n，所以Sn=n(n-1)/2。Sn=n^2-n/2和n^2成正比，所以平均时间复杂度为O(N^2)。

和冒泡排序的最优时间复杂度O(N)不同的是，选择排序的最优时间复杂度为O(N^2)。

最差时间复杂度也是O(N^2)。

空间复杂度为O(1)。

以上就是第二天的挑战。说说和冒泡排序的不同之处，冒泡排序在内循环中执行交换，一次外循环最多可以执行N-1次交换。而选择排序在内循环外执行交换，一次外循环最多执行一次交换。所以，他们的最优时间复杂度是不一样的。还有就是选择排序在一次外循环中需要确定最小元素的索引，内循环结束后进行交换。这是选择排序的核心。