Поменять местами минимум и максимум в массиве

Радикально разных алгоритмов поиска мин. и макс. элементов, имеющих адекватную вычислительную мощность, я не нашел. Можно, конечно, предварительно отсортировать массив, дабы взять первый и последний элементы, но это уже даже не O(n).

Первый алгоритм заключается в прохождении по массиву и сравнивании каждого элемента с минимумом и максимумом, в качестве которых в начале выбран первый вариант. Этот тот алгоритм, который реализовывали вы.

Второй алгоритм действует по похожей схеме, однако элементы предварительно разбиваются на пары и сортируются в рамках пары по возрастанию. После чего происходит прохождение по изменённому массиву в поиске минимума и максимума, однако рассматривается сразу пара элементов, и с минимумом сравнивается только первый элемент пары, а с максимумом - второй.

public static void main(String[] args)
{
    System.out.println("Введите кол-во элементов");
    Scanner in = new Scanner(System.in);
    int elementsCount = in.nextInt();
    int[] elements = new int[elementsCount];
    for (int i = 0; i < elementsCount; i++)
    {
        System.out.println("Введите элемент массива под номером " + i);
        elements[i] = in.nextInt();
    }
    for (int i = 0; i < elementsCount; i++)
    {
        int firstElement = elements[i];
        for (int j = i + 1; j < elementsCount; j++)
        {
            int secondElement = elements[j];
            if (firstElement == secondElement)
            {
                System.out.println("Все элементы должны быть разными");
                return;
            }
        }
    }
    printArray(elements);
    firstAlgorithm(elements);
    secondAlgorithm(elements);
}
private static void firstAlgorithm(int[] data)
{
    int[] elements = new int[data.length];
    System.arraycopy(data, 0, elements, 0, data.length);
    int minIndex = 0;
    int min = elements[minIndex];
    int maxIndex = 0;
    int max = elements[maxIndex];
    for (int i = 1; i < elements.length; i++)
    {
        if (elements[i] < min)
        {
            min = elements[i];
            minIndex = i;
        }
        else if (elements[i] > max)
        {
            max = elements[i];
            maxIndex = i;
        }
    }
    System.out.println("Первый способ:");
    System.out.println("Максимальный элемент массива = " + max);
    System.out.println("Минимальный элемент массива = " + min);
    swapElements(elements, minIndex, maxIndex);
    printArray(elements);
}
private static void secondAlgorithm(int[] data)
{
    int[] elements = new int[data.length];
    System.arraycopy(data, 0, elements, 0, data.length);
    int[] elementsPairs = new int[data.length];
    System.arraycopy(data, 0, elementsPairs, 0, data.length);
    if (data.length == 1)
    {
        System.out.println("Второй способ: в массиве всего один элемент");
        return;
    }
    HashMap<Integer, Integer> swappedPlaceToRealPlace = new HashMap<>();
    for (int i = 0; i < elementsPairs.length; i += 2)
    {
        if (i + 1 < elementsPairs.length && elementsPairs[i] > elementsPairs[i + 1])
        {
            swapElements(elementsPairs, i, i + 1);
            swappedPlaceToRealPlace.put(i, i + 1);
            swappedPlaceToRealPlace.put(i + 1, i);
        }
    }
    int minIndex = 0;
    int min = elementsPairs[minIndex];
    int maxIndex = 1;
    int max = elementsPairs[maxIndex];
    for (int i = 2; i < elementsPairs.length; i += 2)
    {
        int firstIndex = i;
        int secondIndex = i + 1;
        if (secondIndex == elementsPairs.length)
        {
            secondIndex = i;
        }
        if (elementsPairs[firstIndex] < min)
        {
            min = elementsPairs[firstIndex];
            minIndex = i;
        }
        else if (elementsPairs[secondIndex] > max)
        {
            max = elementsPairs[secondIndex];
            maxIndex = secondIndex;
        }
    }
    if (swappedPlaceToRealPlace.containsKey(minIndex))
    {
        minIndex = swappedPlaceToRealPlace.get(minIndex);
    }
    if (swappedPlaceToRealPlace.containsKey(maxIndex))
    {
        maxIndex = swappedPlaceToRealPlace.get(maxIndex);
    }
    System.out.println("Второй способ:");
    System.out.println("Максимальный элемент массива = " + max);
    System.out.println("Минимальный элемент массива = " + min);
    swapElements(elements, minIndex, maxIndex);
    printArray(elements);
}
private static void swapElements(int[] array, int i, int j)
{
    int swap = array[i];
    array[i] = array[j];
    array[j] = swap;
}
private static void printArray(int[] array)
{
    for (int i = 0; i < array.length; i++)
    {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

Получилось достаточно много кода. Если бы элементы не нужно было переставлять местами, то его было бы ощутимо меньше.

В первом алгоритме (метод firstAlgorithm), думаю, всё понятно. Во втором (метод secondAlgorithm) elementPairs содержит изменённый массив, в котором произведена сортировка в рамках пар. swappedPlaceToRealPlace используется для восстановления индексов мин. и макс. элементов в исходном (elements) массиве после их нахождения в изменённом (elementsPairs) массиве. Это нужно опять-таки только для перестановки элементов местами.

С точки зрения теории оба алгоритма работают за линейное время O(n), однако предполагается, что на практике второй должен работать несколько быстрее из-за меньшего количества операций. Вполне возможно, что из-за доп. затрат, связанных с созданием доп. копии массива и сохранением индексов в оригинальном массиве, работать он быстрее не будет.

Второй алгоритм взят отсюда.

Не очень понял зачем вы ищете минимум и максимум в двух разных циклах:

        for (i = 0; i < b; i++) {
            if (a[i] < min) {
                min = a[i];
                l = l + 1;
            }   
        }
        for (i = 0; i < b; i++) {
            if (a[i] > max) { 
                max = a[i];
                k = k + 1;
            } 
        }

Можно найти и минимум и максимум в одном цикле - разве не так? Это можно и выдать за второй способ :)

Update

Например так:

min=Integer.MAX_VALUE;
max=Integer.MIN_VALUE;
for (i = 0; i < b; i++) {
    if (a[i] < min) 
        min = a[i];
    if(a[i] > max)
        max = a[i];
}