分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net
/* * 直接插入排序（straight insertion sort）的做法是： * 每次从无序表中取出第一个元素，把它插入到有序表的合适位置使有序表仍然有序，直至无序表中所有元素插入完为止。 * 第一趟扫描前两个数，然后把第二个数按大小顺序插入到有序表中； * 第二趟把第三个数与前两个数从前向后扫描，把第三个数按大小插入到有序表中； * 依次进行下去，进行了（n-1）趟扫描以后就完成了整个排序过程。 * * 直接插入排序属于稳定的排序，最坏时间复杂度为O（n^2），空间复杂度为O（1）。 * * 直接插入排序是由两层嵌套循环组成的。 * 外层循环标识并决定待比较的数值，内层循环为待比较数值确定其最终位置。 * 直接插入排序是将待比较的数值与它的前一数值进行比较，所以外层循环是从第二个数值开始的。 * 当前一数值比待比较数值大的情况下后移该数值并继续循环比较， * 直到找到比待比较数值小的并将待比较数值插入其后一位置，结束该次循环。 * 值得注意的是，我们必需用一个存储空间来保存当前待比较的数值， * 因为当一趟比较完成时，我们要将待比较数值插入比它小的数值的后一位置。 * 插入排序类似于玩纸牌时整理手中纸牌的过程。 */ namespace InsertionSort { using System; /// /// The program. /// public static class Program { /// /// The main. /// public static void Main() { int[] a = {1, 4, 6, 2, 8, 7, 9, 3, 5, 10}; Console.WriteLine("Before Insertion Sort:"); foreach (int i in a) { Console.Write(i + " "); } Console.WriteLine("\r\n\r\nIn Insertion Sort:"); InsertionSort(a); Console.WriteLine("\r\nAfter Insertion Sort:"); foreach (int i in a) { Console.Write(i + " "); } } /// /// The insertion sort. /// /// /// The a. /// public static void InsertionSort(int[] a) { // 从第二个元素开始迭代。 for (int i = 1; i < a.Length; i++) { // 存储待插入的元素。 int tmp = a[i]; int j = i - 1; // 从当前元素右边寻找插入点。 while (a[j] > tmp) { // 后移。 a[j + 1] = a[j]; j--; if (j == -1) { break; } } // 该后移的元素已经后移了，会留下一个空位置，这个位置就是待插入元素的插入点。 a[j + 1] = tmp; // 打印数组。 foreach (int k in a) { Console.Write(k + " "); } Console.WriteLine(string.Empty); } } } } // Output: /* Before Insertion Sort: 1 4 6 2 8 7 9 3 5 10 In Insertion Sort: 1 4 6 2 8 7 9 3 5 10 1 4 6 2 8 7 9 3 5 10 1 2 4 6 8 7 9 3 5 10 1 2 4 6 8 7 9 3 5 10 1 2 4 6 7 8 9 3 5 10 1 2 4 6 7 8 9 3 5 10 1 2 3 4 6 7 8 9 5 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 After Insertion Sort: 1 2 3 4 5 6 7 8 9 10 */
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/218990.html原文链接：https://javaforall.net
