Блог

Я создал алгоритм сортировки, используя ту же логику, что и алгоритм heapify. Однако я не верю, что это кучная сортировка. Логика этого заключается в том, что я сравниваю две части массива (изначально это должен был быть список с двойной связью, но java не позволила бы мне сделать это, не создав свой собственный класс) с соседним с ним. Если он больше, поменяйтесь местами. Очень похоже на пузырьки. Однако, когда обмен завершен, я затем выполняю обратную сортировку пузырьков для второго элемента, чтобы сохранить порядок массива.

Я не совсем уверен в наихудшей временной сложности этого случая, но я думаю, что это O (n ^ 2). Какова временная сложность этого, а также на какой алгоритм сортировки он больше всего похож?

 import java.util.Arrays;

/**
 * firstNum and secondNum trade places.
 * Whenever a swap is done, sink the secondNumber
 */
private static void swap(int[] A, int firstNum, int secondNum) {
    int temp = A[secondNum];

    A[secondNum] = A[firstNum];
    A[firstNum] = temp;

    sink(A, firstNum);
}

/**
 * Swap places upward until condition is false.
 */
private static void rise(int[] A, int currIndex) {

    int nextIndex = currIndex   1;

    if (nextIndex <= A.length - 1 amp;amp; A[currIndex] > A[nextIndex]) {

        swap(A, currIndex, nextIndex);
        rise(A, nextIndex);
    }
}

/**
 * Swap places downward until condition is not met.
 */
private static void sink(int[] A, int currIndex) {

    int prevIndex = currIndex - 1;

    if (currIndex > 0 amp;amp;  A[currIndex] < A[currIndex - 1]) {
        swap(A, prevIndex, currIndex);
    }
}

public static void main(String[] args) {

    int[] values = {4, 7, 2, 1, 3, 5, 100, 0};

    for (int i = 0; i < values.length - 1; i  ) {
        rise(values, i);
    }

    System.out.println(Arrays.toString(values));


}
 

}

Я бы сказал, что это скрытая сортировка вставки. Таким образом, он имеет наихудший случай и среднюю сложность O (n ^ 2).

Чтобы увидеть это, сначала осознайте, что рекурсивный вызов rise в rise методе является избыточным: вызываемый там элемент в любом случае будет достигнут более поздним вызовом rise из внешнего цикла в main методе. Что осталось, так это рекурсивные вызовы sink swap метода from для каждого элемента в списке. Что это делает, так это помещает каждый элемент в правильное положение в уже отсортированном начальном бите списка: по сути, это сортировка по вставке.