using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Sort { class InsertSorter { public static int[] Sort(int[] a) { InsertSort(a); return a; } private static void InsertSort(int[] myArray) { int i, j,temp; for (i = 1; i < myArray.Length; i++) { temp = myArray[i];//保留当前数据,当前数据即待插进去的数据 //将数组标号i及i之前的元素,排成递增序列 for (j = i - 1; j >= 0 && myArray[j] >temp; j--) { myArray[j + 1] = myArray[j]; } myArray[j + 1] = temp; } } } }
例一:
关键字序列T=(13,6,3,31,9,27,5,11) 请写出直接插进去排序的中心历程序列。
【13】, 6, 3, 31, 9, 27, 5, 11
【6, 13】, 3, 31, 9, 27, 5, 11
【3, 6, 13】, 31, 9, 27, 5, 11
【3, 6, 13,31】, 9, 27, 5, 11
【3, 6, 9, 13,31】, 27, 5, 11
【3, 6, 9, 13,27, 31】, 5, 11
【3, 5, 6, 9, 13,27, 31】, 11
【3, 5, 6, 9, 11,13,27, 31】
小注:每次小循环只分列数组0到i这些元素的递次(与冒泡相似)
例二:
例三:
在最坏情况下,数组完整逆序,插进去第2个元素时要考核前1个元素,插进去第3个元素时,要斟酌前2个元素,……,插进去第N个元素,要斟酌前 N - 1 个元素。因而,最坏情况下的比较次数是 1 + 2 + 3 + ... + (N - 1),等差数列乞降,效果为 N^2 / 2,所以最坏情况下的复杂度为 O(N^2)。
最好情况下,数组已经是有序的,每插进去一个元素,只需要考核前一个元素,因而最好情况下,插进去排序的时刻复杂度为O(N)。
插进去排序的空间复杂度是O(1),由于在插进去排序的时刻,只需要运用一个分外的空间,来存储这个“拿出来”的元素,所以插进去排序只需要分外的一个空间来做排序。
空间复杂度(Space Complexity)是对一个算法在运转历程当中暂时占用存储空间大小的量度。
由因而数组内部本身排序,把背面的部份按前后递次一点点的比较、挪动,能够坚持相对递次稳定,所以插进去排序是稳定的排序算法。
以上就是C# 插进去排序的内容,更多相关内容请关注ki4网(www.ki4.cn)!