// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Program.cs" company="Chimomo's Company">
//
// Respect the work.
//
// </copyright>
// <summary>
//
// The insertion sort.
//
// 直接插入排序(straight insertion sort)的做法是:
// 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
// 第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
// 直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。
// 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值插入其后一位置,结束该次循环。
// 值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,我们要将待比较数值插入比它小的数值的后一位。插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插入到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。
//
// </summary>
// --------------------------------------------------------------------------------------------------------------------
namespace CSharpLearning
{
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("\r\n\r\nIn Insertion Sort:");
InsertionSort(a);
Console.WriteLine("\r\nAfter Insertion Sort:");
foreach (int i in a)
{
Console.Write(i + " ");
}
Console.WriteLine(string.Empty);
}
/// <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
*/
分享到:
相关推荐
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
C#算法 -- (三)希尔排序 朋友们,我最近加紧写C#的一些算法。选择排序,插入算法是我已经推出的。现推出希尔排序....希尔排序是将组分段,进行插入排序. 对想提高C#语言编程能力的朋友,我们可以互相探讨一下。
C# 常用经典算法,选择排序 冒泡排序 快速排序 插入排序 希尔排序
C# 排序算法大全参考资料,比较清淅的一个版本。集中介绍了C#中的冒泡算法、选择排序、插入排序、希尔排序等常用算法,并包含示例代码和注意事项等。
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序、选择排序、插入排序和希尔排序
C#四种排序算法 冒泡排序 插入排序 选择排序 希尔排序 希尔排序是将组分段,进行插入排序.
C#排序算法总结:交换排序:最基础的冒泡排序,冒泡排序的优化版选择排序和快速排序,插入排序:直接插入排序和折半插入排序。
将数字排序,升序和降序 小方法,大作用,大家可以学习。
程序模拟实验所用到的所有源码,包括冒泡排序,插入排序,代码运行时长统计等。
链表:单链表,双向链表,循环链表 栈,队列 二叉树应用-表达式求值 树的操作 图 二分查找 排序算法:插入排序,选择排序,冒泡排序 -全是C#,附上Viso图和一些解释
C#实现的排序算法:1、选择排序 2、冒泡排序 3、快速排序 4、插入排序 5、希尔排序
C#常用排序算法:冒泡,选择,插入,希尔
文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp; bool done=...
C#排序算法大全 冒泡排序、选择排序、插入排序、希尔排序
博客地址:https://blog.csdn.net/qq_30259857/article/details/81071081 冒泡排序,选择排序,插入排序,归并排序,快速排序的 Unity Demo
C#实现冒泡排序法、选择排序法、快速排序法以及插入排序法。
用c#语言重写的基本排序算法,里面包含冒泡排序,鸡尾酒排序(双向冒泡),选择排序,插入排序,希尔排序,堆排序,归并排序这几个排序算法。程序可以直接运行。
本文实例讲述了C#折半插入排序算法实现方法。分享给大家供大家参考。具体实现方法如下: public static void BinarySort (int[] list) { for (int i = 1; i < list.Length; i+ +) { int low = 0; int high =...