这是否将定义为HeapSort的一种形式？

Question

所以我在弄乱排序的实现，并且发现尝试使用ArrayLists和简单的Binary Search这样的基本实现不会有什么坏处：

public static ArrayList<Integer> binarySort(ArrayList<Integer> list) {
    ArrayList<Integer> sortedList = new ArrayList<>();
    for(Integer value : list) {
        int index = binarySearchPosition(sortedList, value);
        sortedList.add(index, value);
    }
    return sortedList;
}

public static int binarySearchPosition(ArrayList<Integer> list, Integer value) {
    int min = 0;
    int max = list.size();

    while(max - min > 1) {
        int mid = (int) Math.floor((max + min) / 2);
        if(list.get(mid) < value) {
            min = mid;
        } else {
            max = mid;
        }
    }

    if(max == 0) {
        return 0;
    }
    if(list.get(min) < value) {
        return max;
    } else {
        return min;
    }
}

它的行为本质上与HeapSort相同，但实际上不会从数据中创建堆。这样的东西会被定义为HeapSort还是其他形式？

Answer 1

您正在执行O（log2（n））N次。那将是O（nlog2（n））。但是，list.add(index, value)本身是O（n）运算。从统计上讲，人们希望它移动N个元素的1/2，big-O表示法将丢弃1/2个元素。]

所以最后您要进行的操作是O（n ^ 2 * log2（n）），它比O（n ^ 2）慢。

由于没有数学依据，因此大致可分为：

N个元素一次添加一个O（n）。

移动N个元素O（n）的1/2。

二进制搜索以找到插入索引O（log2（n））。

请注意，如果您知道已经达到O（n ^ 2），可以通过一种非常简单的算法避免寻找索引的额外工作：

Create a new array one element bigger.
for each element in the original array {
  if the element is smaller than the added item, copy it at the same index.
  if the element is same / larger than the added item, copy in the added item, and copy the rest of the elements from index to index+1.
}

1. 如您所见，它是整个数组的一个完整循环，必须重复N次或O（n ^ 2）。
2. 您的数据结构实际上不是堆，而是排序列表。使用二进制搜索来搜索排序列表是一个很好的优化。只是不会减少在插入排序上遍历大量列表的需要；因为您将要复制1/2项（如果数组足够大以容纳新项）或复制整个列表（如果数组的大小与输入匹配）。这两种情况都意味着无论您如何找到插入索引，这种插入支持方法都将是O（n ^ 2）。
3. 现在，如果您有一个链表，则插入将变为O（1）。但是，要找到索引就成为从根节点开始的步，根节点本身就是O（n）（同样，平均会通过1/2个节点）。

现在堆是另一回事了；但是，您知道这是因为它们不会产生排序列表。