带你读《图解算法小抄》十四、排序(3)https://developer.aliyun.com/article/1348147?groupCode=tech_library
2)选择排序优化
这是基本的选择排序算法实现。接下来,我将介绍一种优化方法,称为“双向选择排序”。
双向选择排序是对传统选择排序的一种改进,它通过同时寻找未排序序列中的最大和最小元素,然后分别将它们放到已排序序列的两端,从而减少了一半的比较次数。
function bidirectionalSelectionSort(arr) { let left = 0; let right = arr.length - 1; while (left < right) { let minIndex = left; let maxIndex = right; for (let i = left; i <= right; i++) { if (arr[i] < arr[minIndex]) { minIndex = i; } if (arr[i] > arr[maxIndex]) { maxIndex = i; } } if (minIndex !== left) { [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]]; } if (maxIndex === left) { // 如果最大元素移到了最小元素的位置,更新最大元素的索引 maxIndex = minIndex; } if (maxIndex !== right) { [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]]; } left++; right--; } return arr; } // 示例用法:const array = [64, 25, 12, 22, 11];const sortedArray = bidirectionalSelectionSort(array); console.log(sortedArray); // 输出:[11, 12, 22, 25, 64]
双向选择排序的优化使得每一轮循环可以同时找到最大和最小元素,从而减少了比较次数。这样,在大型数据集上,它的性能优于传统的选择排序算法。
3)复杂度
名称 |
最佳情况 |
平均情况 |
最坏情况 |
内存 |
稳定性 |
备注 |
选择排序 |
n^2 |
n^2 |
n^2 |
1 |
否 |
|
4)参考资料
维基百科
带你读《图解算法小抄》十四、排序(5)https://developer.aliyun.com/article/1348145?groupCode=tech_library