带Comparator比较器的选择排序运行后排序结果异常问题求助

问题根源 #

你的选择排序实现错误出在交换操作的放置位置，你把交换逻辑写在了寻找最小元素的内层循环内部，这不符合选择排序的执行逻辑。

选择排序的标准执行流程是：

• 遍历未排序区间，先找到整个区间内最小元素的下标
• 内层循环完全结束、确定最终的最小元素下标后，再将最小元素和未排序区间的第一个元素做一次交换

你现在的实现是每找到一个比当前记录值更小的元素，就立刻执行一次交换，这会导致已经定位到的较小元素被后续交换操作打乱位置，最终得到错误的排序结果。

修正后的代码 #

你的两个Comparator实现逻辑完全正确无需修改，仅需调整排序逻辑的交换位置即可：

class SelectionSort {
   public static void sort(
       ArrayList<Student> studentList,
       Comparator<Student> comparator
   ) {
       for (int i = 0; i < studentList.size()-1; ++i) {
           int currentMinIndex = i;
           // 内层循环仅用来查找未排序区间的最小元素下标
           for (int j = i + 1; j < studentList.size(); ++j) {
               if (comparator.compare(studentList.get(j), studentList.get(currentMinIndex)) < 0) {
                   currentMinIndex = j;
               }
           }
           // 内层循环结束后再执行交换操作
           if (currentMinIndex != i) {
               Collections.swap(studentList, i, currentMinIndex);
           }
       }
   }   
}

内容的提问来源于stack exchange，提问作者Stephen