首页 > 代码库 > 插入排序（insertion-sort）

插入排序（insertion-sort）

2024-07-10 18:47:59   218人阅读

      作为排序算法的一种，插入排序是稳定排序。它的时间复杂度：O（n*n），空间复杂度为：O(1)。最好的时间复杂度为：O(n)，最坏和平均则为：O(n*n)。

      算法的思想：给定一组无序的数组，我们从它的第二个数开始，并将它赋值给mark变量，让mark和它前面的一个数作大小比较，若小于前面的那个数，则将前面那个数移动到它的位置。然后继续让它和它前面的数作大小比较，若小于则交换位置，若大于则将mark赋值给合适的位置，然后跳出循环，则又从下一个数开始重复如此步骤。

 

贴出相关代码：

#include <stdio.h>int main(){     int num,mark;            //num是要输入的数组大小，mark则是标记     int i, j;                        //i，j都是要用到的变量     int arry[100];             //数组     scanf("%d", &num);  //输入操作      for(int i=0; i<num; i++)          scanf("%d", &arry[i]);     for(i=1; i<num; i++)    //进行排序操作     {          mark = arry[i];         //先将值赋给标记变量            j = i-1;          while(j>=0 && mark < arry[j])     //若比前面的数小，则进行交换，再想前移          {               arry[j+1] = arry[j];               j--;          }          arry[j+1] = mark;              //交换完成，将标记值赋给合适的位置     }     for(int i=0; i<num; i++)        //输出操作          printf("%d  ", arry[i]);     printf("\n");     return 0;}

 


联系
我们