在选择排序中每次通过时查找数组中的最小值和最大值

Question

我正在研究基于 Java 的数组排序技术，偶然发现了 Selection Sort

中的增强功能

选择排序的documented approach讲的是在每一遍中寻找最大或最小的对象

The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

我想知道是否可以通过同时检查两个条件在一次通过中找到最大和最小的对象

public static void mySort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length - i; j++) {
            //This will make sure smallest element will come first
            if (arr[i] > arr[j]) {
                swap(arr, i, j);
            }
            // This will make sure largest element will come last
            if (arr[j] > arr[arr.length - 1 - i]) {
                swap(arr, arr.length - 1 - i, j);
             // This will ensure that if a smaller element existed at the ending position and got swapped , we are making sure that it doesn't get mixed
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }
}

基本上我们在这里做的是从两端排序。与传统的选择排序相比，这将节省一些时间，您能否提供对该方法的反馈，如果已经存在类似的东西

更多详情@my blog post

Answer 1

通常重要的是比较的次数，通过的次数较少但比较相同。此外，选择排序通常用于小型集合，因为它 简单性 ，对于较大的集合，将使用时间复杂度较低的排序。

当您可以使用 O(N log N) 排序时，您什么时候会使用优化的 O(N^2) 排序？只有当 N 很小时，并且你想要一些简单的东西来覆盖它。例如当我想比较 至多两个 元素时，我使用选择排序。

在选择排序中每次通过时查找数组中的最小值和最大值

Finding both the minimum and maximum in a array with each pass in Selection Sort

java

sorting

selection-sort