插入排序C语言插入排序法

什么是插入排序？有什么特点

本人不擅长文字表达给你写个例子吧 10 6 12 7 9 2 14 31 插入排序从小到大 第一趟 6 10 12 7 9 2 14 31 第二趟 6 10 12 7 9 2 14 31 第三趟 6 7 10 12 9 2 14 31 第四趟 6 7 9 10 12 2 14 31 第五趟 2 6 7 9 10 12 14 31 第六趟 2 6 7 9 10 12 14 31 第七趟 2 6 7 9 10 12 14 31

直接插入排序 和插入排序有什么区别？？

直接插入排序 直接插入排序(straight insertion sort)的作法是： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。

直接插入排序是由两层嵌套循环组成的。

外层循环标识并决定待比较的数值。

内层循环为待比较数值确定其最终位置。

直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。

当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。

插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

插入排序 有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。

是稳定的排序方法。

插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。

在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。

插入法排序！！

就像打牌的时候把扑克牌排序一样 把a[i]插入到前i-1个已经排好序的序列当中 生成长度为i的序列 依次向后处理。

#include<iostream> using namespace std; int a[100],n; int main() { cin>>n; //读入 for (int i=1;i<=n;i++) cin>>a[i]; for (int i=2;i<=n;i++)//排序 从2开始（明白？） { int p=i; while (p>1&&a[p]<a[p-1]) {swap(a[p],a[p-1]);p--;}//向前找到合适的位置 } for (int i=1;i<n;i++) cout<<a[i]<<" ";//输出 cout<<a[n]<<endl; return 0; }

插入排序，快速排序哪个更快？

当数据量小于1000时相差很小。

当数据量大于10000时，数据量越大，差别越明显。

是快速排序速度快。

C语言插入排序法

for(i=1;i<4;i++) //外层 { t=a[i]; for( j=i-1 ; j>=0 && t>a[j] ; j-- ) //内层 a[j+1]=a[j]; a[j+1]=t; } 你要理解插入排序的原理，外层for从第二个数开始遍历（i从1开始），用t（即对应的a[i]）和其前面的所有值进行比较，如果t大，则该数后移一位，直到t小或者j小于0的时候退出内层for循环，这时候出现的格局就是所有在i位置之前比a[i]小的值全部后移了一位，退出循环时就会空出一个位置来。

举个例子：输入：1 3 2 4 第一次循环时，t=a[1]=3，t>a[0]，所以a[0]后移一位（即：a[j+1]=a[j] -> a[1]=a[0]），之后出现结果：1124，这时候实际上0位置是给此时的t预留的位置，内层for执行完毕后，执行：a[j+1]=t 正好弥补这个空缺。

结果：3124 第二次循环时，j=1，t=a[2]=2，t>a[1]，所以a[1]后移一位：a[2]=a[1]，之后结果：3114，在比较t和a[0]，t小，跳出内层for，跳出时j为0，执行：a[1]=t=2，结果：3214 下面就不讲了，从上面可以看出，你说的那一句，至关重要，外层for每循环一次就插入一位数据，而a[j+1]=t，就是完成插入的最后一步。

。