泡沫排序算法.最坏情况下的时间复杂性是什么

Question

我使用与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 && 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 &&  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));

}

}

Answer 1

我认为这是变相的插入排序。因此它具有O(n^2(的最坏情况和平均复杂度。

要看到这一点，首先要意识到rise方法中对rise的递归调用是多余的：在main方法中，稍后从外循环对rise的调用无论如何都会到达在那里引发的元素。剩下的是对列表中的每个元素从swap方法递归调用sink。这样做的目的是将每个元素放在列表中已经排序的初始位的正确位置：这本质上是插入排序