排序算法-选择排序

选择排序算法定义（Selection Sort）

选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：
每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序

第1趟，在待排序记录r[0]~r[n-1]中选出最小的记录，将它与r[0]交换；
第2趟，在待排序记录r[1]~r[n-1]中选出最小的记录，将它与r[1]交换；
以此类推，第i趟，在待排序记录r[i-1]~r[n-1]中选出最小的记录，将它与r[i-1]交换，
使有序序列不断增长直到全部排序完毕。

基本思想

选择排序的基本思想

每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序的基本思想

第1趟，在待排序记录r[0]~r[n-1]中选出最小的记录，将它与r[0]交换；
第2趟，在待排序记录r[1]~r[n-1]中选出最小的记录，将它与r[1]交换；以此类推，
第i趟，在待排序记录r[i-1]~r[n-1]中选出最小的记录，将它与r[i-1]交换，
使有序序列不断增长直到全部排序完毕。

简单选择排序的存储状态

初始序列：{49 27 65 97 76 12 38}
第1趟：12与49交换：12{27 65 97 76 49 38}
第2趟：27不动　：12 27{65 97 76 49 38}
第3趟：65与38交换：12 27 38{97 76 49 65}
第4趟：97与49交换：12 27 38 49{76 97 65}
第5趟：76与65交换：12 27 38 49 65{97 76}
第6趟：97与76交换：12 27 38 49 65 76 97 完成

PS：其中大括号内为无序区，大括号外为有序序列

简单选择排序的算法分析

在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，
则不需要移动记录。最坏情况下，需要移动记录的次数最多为3（n-1）（此情况中待排序记录并非完全逆序，
给完全逆序记录排序的移动次数应为(n/2)*3，其中n/2向下取整）。
简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。
当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，
共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。

算法描述

function selectionSort(array) {
	let arr = array.slice(), // 深拷贝一份原数组
		len = arr.length,
		minIndex,
		temp;
	for (var i = 0; i < len - 1; i++) {
		minIndex = i;
		for (var j = i + 1; j < len; j++) {
			if (arr[j] < arr[minIndex]) {     //寻找最小的数
				minIndex = j;                 //将最小数的索引保存
			}
		}
		temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
	return arr;
}

var arr = [5, 4, 3, 2, 1];
var demo = selectionSort(arr);
console.log(arr); // [5, 4, 3, 2, 1]
console.log(demo); // [1, 2, 3, 4, 5]

PS：建议使用不可变对象的思想进行编程。

动态展示

图片来源，在此表示感谢！

参考文档：
选择排序（Selection Sort）
选择排序法