c++ - 通过向右移动对值数组进行排序

Question

我必须创建一个方法来对值数组从最低值到最高值进行排序。这些函数的工作方式应该是它获取每个值，并尝试通过将每个较大的值向右移动来将它们按从左到右的升序排列。

我做了以下功能:

int findIndex(double *arr, double num, int length)
{

   for (int i = 0; i < length; i++)
   {
      if (arr[i] > num)
         return i;
     }
   return length - 1;
}

void placeOnIndex(double *arr, double num,int index, int length)
{

   if (length > 1 && arr[index] != num) 
   {
       for (int i = length - 1; i > 0; i--)
       {
            arr[i] = arr[i - 1];
       }

       arr[index] = num;
   }
}

void insertSort(double* arr, int length)
{
   for (int ix = 0; ix < length; ix++)
   {
       double num = arr[ix]; //Current value to put as far to the left as possible
       int index = findIndex(arr, num, ix+1);  //Locates index to put it
       placeOnIndex(arr, num, index, ix+1); //Uses the index to put in the right place
   }

}

void main()
{
   double arr[4] = {1,8,4,5};
   insertSort((arr), 4);
}

我的问题是这个数组的输出变成了: 1,1,5,8

显然它有时会覆盖我数组中的第二个元素。有时有效，有时无效。如果数组更长，则会覆盖更多值。

很抱歉，如果它看起来令人困惑，英语不是我的母语。

Answer 1

这一行

for (int i = length - 1; i > 0; i--)

使所有元素向右移动，而不仅仅是应该移动的元素。

你需要

for (int i = length - 1; i > index; i--)