C++ 插入排序不适用于大型数组

Question

我的 insertionSort 函数适用于小型数组，但不适用于具有 50,000 个随机值的数组。我花了几个小时试图解决这个问题，但我很困惑。这是代码：

void insertionSort(int array[], int length) {
  int swapHolder, counter, index;
  for (counter = 1; counter < length; counter++) {
        index = counter;
        while (counter > 0 && array[index - 1] > array[index]) {
              swapHolder = array[index];
              array[index] = array[index - 1];
              array[index - 1] = swapHolder;
              index--;
        }
    }
}

我的另一个排序函数 (bubbleSort) 适用于大型数组，但我被这个问题挂断了。

Answer 1

行

while (counter > 0 && array[index - 1] > array[index]) {

应该是

while (index > 0 && array[index - 1] > array[index]) {

更深入地讲，插入排序的平均复杂度是 O(n^2)，因此它最适合小型数组。也就是说，它不是对 50,000 个值进行排序的正确算法。

C++ 插入排序不适用于大型数组

C++ insertion sort not working for large arrays

c++

sorting

insertion-sort