import { swap } from '../util/index.mjs';

/**
 *
 * @param {number[]} arr - 需要排序的数组
 * @description 普通的选择排序
 */
export function selectSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) { // 找到本轮最小的值
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex); // 交换最小值和选择值的下标
  }
}

/**
 *
 * @param {number[]} arr
 * @description 两端同时排序，类似鸡尾酒排序
 */
export function selectSort2(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;
      }
    }

    // 将最小值交换到左边
    [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
    // 如果最大值的索引是左边的索引，由于上一步交换，所以更新为最小值的索引
    if (maxIndex === left) {
      maxIndex = minIndex;
    }
    // 将最大值交换到右边
    [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];

    // 更新左右指针
    left++;
    right--;
  }
}

// 实际比较下来优化后的选择排序也没太大作用（实际开发不应使用这种排序，主要学习其解决思路）

export default selectSort;


let arr = [3,4,2,3,2,6,4,3]
selectSort2(arr)
console.log(arr);