黑马程序员技术交流社区

标题: C#排序算法 直接插入排序 [打印本页]

---

作者: 胡元江    时间: 2013-2-13 18:54
标题: C#排序算法 直接插入排序


直接插入排序
思路：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

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

整个排序过程。

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

　　直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是

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



效率分析：

速度慢，空间效率高，稳定。



代码：

private static void InsertSort(int[] data)  
        {  
            for (int i = 1; i < data.Length; i++)  
            {  
                //备份data的值   
                int temp = data;  
  
                if (data < data[i - 1])  
                {  
                    int j = i - 1;  
  
                    //通过比较找出要插入的位置，同时将大的数值向右移动   
                    for (; j >= 0 && data[j] > temp; j--)  
                    {  
                        data[j + 1] = data[j];  
                    }  
  
                    //将temp插入合适的位置   
                    data[j + 1] = temp;  
                }  
            }  
        }  

---

作者: 许庭洲    时间: 2013-2-17 14:37
值得学习ing!

---

作者: 邓明    时间: 2013-2-20 15:23
提个菜鸟问题（我本人就是菜鸟啊，见谅）
1.temp是插入到data[j]还是data[j+1]？我个人觉得是插入到data[j]位置
2.将无序表中的元素加入有序表，表的容量是如何处理的？
举例来说，请楼主尝试一下，将{4,2}插入{1,3,5,6,7,9}后的结果是怎样的？
在楼主给的这段代码中，我没有看到将表的容量增大的部分，这个例子最后得到的结果会是{1,2,3,4,5,6}吗？

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2