// 选择排序 // 原理:进行 n-1 趟 循环,每趟循环中遍历所有未排好序的数,第一趟循环,从第0个元素开始向后遍历,找到 最小的元素,与第1 一个元素进行交换,第二趟,从第 1 个元素开始向后遍历,找到最小值与第2个元素 进行交换,以此类推 // 从而得出规律,每次遍历元素开始位置为 i+1,并维护每轮循环的最小值的索引,一轮循环结束后,通过最小值的索引获取到最小值,与起始位置交换 // 稳定性:因为选择排序每次找到最小值,都会与起始位置交换,所以是不稳定的 function selectSort(arr) { let length = arr.length; if (length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 维护每趟循环中的未排序序列中的最小值,默认设为第一个值 let minIndex; let temp; for (let i = 0; i < length - 1; i++) { count++; // 每趟循环,将 minIndex 设为无序数列的起始索引 minIndex = i; for (let j = i + 1; j < length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; // 将最小数的索引保存 } // 交换最小中与未排序序列开始遍历的第一个值 temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.log(`执行了${count}趟循环`); return arr; } console.log("普通选择排序"); console.log(selectSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了9趟循环 console.log(selectSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 执行了9趟循环 // 优化选择排序,减少交换的次数及循环的趟数 function selectSort2(arr) { let length = arr.length; if (length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 维护每趟循环中的未排序序列中的最小值,默认设为第一个值 let minIndex; let temp; for (let i = 0; i < length - 1; i++) { count++; // 默认为有序 let hasSort = true; // 每趟循环,将 minIndex 设为无序数列的起始索引 minIndex = i; for (let j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { // 只要进行交换,则本次是无序 hasSort = false; minIndex = j; // 将最小数的索引保存 } } // 交换最小中与未排序序列开始遍历的第一个值 // 减少交换的次数 if (arr[i] !== arr[minIndex]) { temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } // 当是有序数列时,跳出外层循环,减少循环趟 if (hasSort) { break; } } console.log(`执行了${count}趟循环`); return arr; } console.log("普通选择排序"); console.log(selectSort2([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); // 执行了7趟循环 console.log(selectSort2([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 执行了1趟循环
参考链接 :https://blog.csdn.net/hcz666/article/details/126486057
原文链接:https://www.cnblogs.com/beileixinqing/p/16649344.html
转载请注明出处。
标签:minIndex,arr,js,length,循环,let,排序,优化 From: https://www.cnblogs.com/beileixinqing/p/16649344.html