首页 > 代码库 > c语言--直接插入算法

c语言--直接插入算法

2024-07-20 01:52:49   223人阅读

插入排序是排序算法的一种，它不改变原有的序列（数组），而是创建一个新的序列，在新序列上进行操作。

这里以从小到大排序为例进行讲解。

        插入排序的基本思想是，将元素逐个添加到已经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。
 
        在实际使用中，通常是排序整个无序数组，所以把这个无序数组分为两部分排序好的子数组和待插入的元素；
    第一轮时，将第一个元素作为排序好的子数组，插入第二个元素；
    第二轮，将前两个元素作为排序好的数组，插入第三个元素；
    以此类推，第i轮排序时，在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。

下面，以对 3  2  4  1 进行选择排序说明插入过程，使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。

第1轮
[ 3 ]  [ 2  4  1 ]  （最初状态，将第1个元素分为排序好的子数组，其余为待插入元素）
[ 3 ]  [ 2  4  1 ]  （由于3>2，所以待插入位置j=1）
[ 2  3 ]  [ 4  1 ]  （将2插入到位置j）

第2轮
[ 2  3 ]  [ 4  1 ] （第1轮排序结果）
[ 2  3 ]  [ 4  1 ] （由于2<4，所以先假定j=2）
[ 2  3 ]  [ 4  1 ] （由于3<4，所以j=3）
[ 2  3  4 ]  [ 1 ] （由于4刚好在位置3，无需插入）

第3轮
[ 2  3  4 ]  [ 1 ] （第2轮排序结果）
[ 2  3  4 ]  [ 1 ] （由于1<2，所以j=1）
[1  2  3  4 ]    （将1插入位置j，待排序元素为空，排序结束）

算法总结及实现

     选择排序对大小为N的无序数组R[N]进行排序，进行N-1轮选择过程。首先将第1个元素作为已经排序好的子数组，然后将剩余的N-1个元素，逐个插入到已经排序好子数组；。因此，在第 i轮排序时，前i个元素总是有序的，将第i+1个元素插入到正确的位置。
复制纯文本新窗口
  1. #include<stdio.h> 
  2. #include<stdlib.h> 
  3. #include<iostream>
  4. using namespace std;
  5. 

  6. void insert_sort(int a[]，int &n);  //使用C++中引用操作；
  7. 

  8. int main() 
  9. { 
  10. 

  11. int num[] = {89, 38, 11, 78, 96, 44, 19, 25}; 
  12. 

  13. //数据元素的个数：
  14. int N=sizeof(num)/sizeof(N[0]);  
  15. 

  16. insert_sort(num,N); 
  17. 

  18. for(int i=0; i<N; i++) 
  19. cout<<num[i]<<endl; 
  20. 

  21. system("pause"); 
  22. return 0; 
  23. 

  24. }


  1. //插入排序实现,这里按从小到大排序 
  2. void insert_sort(int a[],int &n)   //n为数组a的元素个数,这里采用c++中的引用操作； 
  3. { 
  4.  int t=0;
  5. for(int i=2-1; i<=n-1; i++) 
  6. { 
  7. 

  8.   if(a[i]<a[i-1])//首先找到元素a[i]需要插入的位置 
  9.    {
  10.      t=a[i];
  11.      for(int j=i-1;a[j]>t;j--)
  12.       a[j+1]=a[j];
  13.     //将元素插入到正确的位置 
  14.       a[j+1]=t;
  15.     }
  16.     }
  17. }
注意：插入排序是一种稳定的排序算法，不会改变原有序列中相同数字的顺序。

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

c语言--直接插入算法


联系
我们