概述
分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net
/*
* 直接插入排序(straight insertion sort)的做法是:
* 每次从无序表中取出第一个元素,把它插入到有序表的合适位置使有序表仍然有序,直至无序表中所有元素插入完为止。
* 第一趟扫描前两个数,然后把第二个数按大小顺序插入到有序表中;
* 第二趟把第三个数与前两个数从前向后扫描,把第三个数按大小插入到有序表中;
* 依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
*
* 直接插入排序属于稳定的排序,最坏时间复杂度为O(n^2),空间复杂度为O(1)。
*
* 直接插入排序是由两层嵌套循环组成的。
* 外层循环标识并决定待比较的数值,内层循环为待比较数值确定其最终位置。
* 直接插入排序是将待比较的数值与它的前一数值进行比较,所以外层循环是从第二个数值开始的。
* 当前一数值比待比较数值大的情况下后移该数值并继续循环比较,
* 直到找到比待比较数值小的并将待比较数值插入其后一位置,结束该次循环。
* 值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,
* 因为当一趟比较完成时,我们要将待比较数值插入比它小的数值的后一位置。
* 插入排序类似于玩纸牌时整理手中纸牌的过程。
*/
namespace InsertionSort
{
using System;
/// <summary>
/// The program.
/// </summary>
public static class Program
{
/// <summary>
/// The main.
/// </summary>
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("rnrnIn Insertion Sort:");
InsertionSort(a);
Console.WriteLine("rnAfter Insertion Sort:");
foreach (int i in a)
{
Console.Write(i + " ");
}
}
/// <summary>
/// The insertion sort.
/// </summary>
/// <param name="a">
/// The a.
/// </param>
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
*/
最后
以上就是激情母鸡为你收集整理的算法 - 插入排序(C#)的全部内容,希望文章能够帮你解决算法 - 插入排序(C#)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复