c++ - 插入排序变体

Question

#include <iostream>
using namespace std;


void print_array(int array[], int size)
{
    cout<< "insertion sort steps: ";
    int j;
    for (j=0; j<size;j++)
        cout <<" "<< array[j];
    cout << endl;
}

void insertion_sort(int a[], int n)
{

    int i;
       for(int j = 1; j < n; j++) {
          i = 0;
          while ((a[j] > a[i])) {
            i = i+1;
          }
          int m = a[j];
          for(int k = 0; k <= (j-i-1); k++) {
            a[j-k] = a[j-k-1];

          }
          a[i] = m;
          print_array(a,n);
       }
}

int main() {
    int array[6]= {3,2,4,5,1,6};
    insertion_sort(array,6);
    return 0;
}

我正在尝试修改它的插入排序，它使用线性搜索技术将第 j 个元素插入到正确的位置，首先将其与第 (j - 1) 个元素进行比较，然后在必要时将第 (j - 2) 个元素进行比较， 等等。

所以它说它i = 0;现在应该在哪里i = j-1;

我的尝试：

void insertion_sort(int a[], int n)
{

    int i;
       for(int j = 1; j < n; j++) {
          i = j-1;
          while ((a[j] > a[i]) && (i > 0)) {
            i = i-1;
          }
          int m = a[j];
          for(int k = (j-i-1); k >= 0; k--) {
            a[j-k] = a[j-k-1];

          }
          a[i] = m;
          print_array(a,n);
       }
}

这是输出

insertion sort steps:  2 3 4 5 1 6
insertion sort steps:  4 2 2 5 1 6
insertion sort steps:  5 4 4 4 1 6
insertion sort steps:  5 4 4 1 4 6
insertion sort steps:  6 5 5 5 5 5

第一步是正确的，第二步是当一切开始失败时。

Answer 1

这

          while ((a[j] > a[i]) && (i > 0)) {
            i = i-1;
          }

是错误的，因为如果不移动它会导致a[j]在索引处插入。将其更改为0a[j]

          while (0 <= i && a[j] < a[i]) --i;
          ++i;

此外，换档循环是错误且复杂的 - 将其更改为

          int m = a[j];
          for (int k = j; k > i; k--) a[k] = a[k-1];
          a[i] = m;