首页 > 代码库 > 排序算法之直接插入排序

排序算法之直接插入排序

直接插入排序定义:
  每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。
class Program{    static void Main(string[] args)    {        int[] array = new[] { 234, 632, 23, 643, 2, 6, -2, 423, 2342,43 };        Console.WriteLine("排序前:");        Console.WriteLine(string.Join(",", array));        InsertSort(array);        Console.WriteLine("排序后:");        Console.WriteLine(string.Join(",", array));        Console.ReadKey();    }    /// <summary>    /// 直接插入排序    /// </summary>    /// <param name="sources">目标数组</param>    private static void InsertSort(int[] sources)    {        // 从索引1开始,假设sources[0]已经有序        for (int i = 1, len = sources.Length - 1; i <= len; i++)        {            // 准备要插入的数据            int insertValue =http://www.mamicode.com/ sources[i],            // 假设要插入的索引            insertIndex = i - 1;            // 遍历查找插入的索引位置            while (insertIndex >= 0 && insertValue < sources[insertIndex])            {                // 当前数据后移一位                sources[insertIndex + 1] = sources[insertIndex];                insertIndex--;            }                        // 不满足以上条件,说明找到位置,插入数据            sources[insertIndex + 1] = insertValue;        }    }        /// <summary>    /// 直接插入排序 for实现    /// </summary>    /// <param name="sources">目标数组</param>    private static void InsertSort1(int[] sources)    {        for (int i = 1, len = sources.Length - 1; i <= len; i++)        {            for (int j = i; j > 0; j--)            {                if (sources[j] > sources[j - 1]) // > 降序, < 升序                {                    int temp = sources[j];                    sources[j] = sources[j - 1];                    sources[j - 1] = temp;                }            }        }    }}

 

 
 

排序算法之直接插入排序