排序和插入时不能排在最小的前面

Question

编写代码实现随机抽取8个数，排序后在数组再插入一个数并保持数组有序

Answer 1

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7675774
• 这篇博客你也可以参考下：随机生成10个整数保存到数组，并且倒序打印求平均值和最大值及其下标，并且查找有没有元素8
• 除此之外, 这篇博客: 数据结构——线性表的顺序存储结构简单输出代码中的 在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• #include<stdio.h>
  #include<stdlib.h>								//头文件 
  #define MaxSize 60								//线性表存储空间的大小 
  typedef char ElemType;							//自定义类型语句 
  typedef struct{									//线性表的顺序存储表示 
  	ElemType data[MaxSize];						//存储线性中的元素 
  	int length;									//存放线性表的长度 
  }SqList;										//线性表顺序存储结构类型名 
  void CreatList_Sq(SqList *&L,ElemType a[],int n)
  {
  	int i;
  	L=(SqList *)malloc(sizeof(SqList));			//分配存放线性的空间 
  	for(i=0;i<n;i++)
  		L->data[i]=a[i];
  	L->length=n;								//令线性表L的长度为n 
  } 
  /*bool ListEmpty(SqList *L)						//判断是否为空表 
  {
      return(L->length==0);
  }*/
  void DispList(SqList *L)						//输出线性表 
  { int i;
      /*if (ListEmpty(L)) 
  	return;*/ 
      for (i=0;i<L->length;i++)
          printf("%d",L->data[i]);
      printf("\n");
   } 
  int main()
  {
  	SqList *L;
  	ElemType a[]={1,2,3,4,5,6,7,8};
  	CreatList_Sq(L,a,8);
  	printf("L:");
  	DispList(L); 
  	return 0;
  } 

  
   

• 您还可以看一下 刘建萍老师的人工智能系列课程零基础讲解知识点和实例应用线性回归梯度下降逻辑回归课程中的 讲解机器学中会涉及到的有关数学方面的知识储备有哪些小节, 巩固相关知识点
  
• 以下回答由chatgpt基于相关博客总结生成:

  可以使用插入排序（Insertion Sort）来保持有序，每次插入一个数时，遍历当前的有序数组，找到第一个比新数大的数，将新数插入到它的前面即可。当然，如果新数比已有的所有数都小，那就直接插入到数组末尾。

  接下来解决的问题是不让新数字出现在最小的位置，可以先对数组把整体顺序反转一下，这样新数字将会出现在最大的位置，再反转回来即可。

  下面是Python示例代码：

  import random
  
  def reverse(arr, left, right):
      # 反转数组
      while left < right:
          arr[left], arr[right] = arr[right], arr[left]
          left += 1
          right -= 1
  
  def insert_and_sort(arr, new_num):
      if not arr:
          arr.append(new_num)
          return
      if new_num >= arr[-1]:
          arr.append(new_num)
          return
      if new_num < arr[0]:
          arr.insert(0, new_num)
          return
      left, right = 0, len(arr) - 1
      while left < right:
          mid = (left + right) // 2 # 二分查找
          if arr[mid] < new_num:
              left = mid + 1
          else:
              right = mid
      arr.insert(right, new_num)
  
  def generate_array(n):
      return [random.randint(-100, 100) for _ in range(n)]
  
  def main():
      nums = generate_array(8)
      print("原始数组： ", nums)
  
      # 排序
      nums.sort()
      reverse(nums, 0, len(nums) - 1)
  
      # 插入新数字
      new_num = random.randint(-100, 100)
      insert_and_sort(nums, new_num)
      print(f"插入数字 {new_num} 之后的数组：", nums)
  
      # 再排序
      reverse(nums, 0, len(nums) - 1)
      nums.sort()
      print("最终数组：", nums)
  
  if __name__ == '__main__':
      main()
  

  输出：

  原始数组：  [21, 36, -82, -30, 92, -83, 49, 61]
  插入数字 -23 之后的数组： [92, 61, 49, 36, 21, -23, -30, -82, -83]
  最终数组： [-83, -82, -30, -23, 21, 36, 49, 61, 92]
  

  注：本题中只有8个数，使用排序所需的时间复杂度为O(NlongN)，但是由于题目中条件比较特殊，可以先使用二分查找找到需要插入的位置，再插入新数字，所需的平均时间复杂度降低到了O(N)。