选择排序

基本思路

前面视为排序完成的数组，后面未排序 每一趟找到未排序数组中最小的那个放到排序数组的后面

一般实现

function selectionSort(nums){
    let len=nums.length;
    for (let i=0 ;i<len;i++){
        let minIndex=i;
        for(let j=i+1;j<len;j++){
            if(nums[j]<nums[minIndex]){
                minIndex=j;
            }
        }
        //把每一趟最小的那个与未排序数组的第一交换，排序数组的个数加一
        if (minIndex !== i) {
            let temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }
    return nums
}

递归实现

起始索引从0开始，直到最后一个结束

function recursiveSelectionSort(nums,startIndex){
   	startIndex = startIndex === undefined ? 0 : startIndex;
   	//递归终止条件：起始索引到最后一个
   	if(startIndex>=nums.length-1){
   		return nums;
   	}
   	let minIndex=startIndex;
   	for(let i=startIndex+1;i<nums.length;i++){
   		if(nums[i]<nums[minIndex]) minIndex=i;
   	}
   	//交换
   	if (minIndex !== startIndex) {
           let temp = nums[minIndex];
           nums[minIndex] = nums[startIndex];
           nums[startIndex] = temp;
    }
   	// 递归排序剩余的数组部分
    return recursiveSelectionSort(nums, startIndex + 1);
   	
   }
const result=recursiveSelectionSort(nums);
console.log(result)

时间，空间复杂度

• 时间复杂度：O(n²)（所有情况）
• 空间复杂度：O(1)
• 稳定性：不稳定（交换可能破坏顺序）

reference

排序经典算法