直接插入算法:
有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序算法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外,而第二部分就只包含这一个元素。在第一部分排序后,再把这个最后元素插入到此刻已是有序的第一部分里的位置。
实现:
//插入排序算法 for循环实现,i的值会一直循环到0,不好得到i的中间的值,比如应该插入到第二个,这个值不好取,所以可以用交换来做,内循环有冒泡的部分,由于i 1、第一个为最小,第二个和第一个比,如果小,那么把第一个向右移,第二个放在第一个的位置,依次循环,第三个,先和第二个比,如果小,移动,然后再和第一个比。
for (int j = 0; j < array.Length; j++ )
{
int temp = array[j]; int i;
//用for实现
for ( i =j; i > 0; i--)
{
if (temp < array[i - 1])
{
array[i] = array[i - 1];
array[i-1] = temp;//和while的区别,在此while是条件不符合能够直接跳出去如当i= 3;时跳出,将temp赋值给array[3],但是for必须交换,因为i会一直循环到0;
}
}
//
//用while实现,把前面大的依次往后移动,然后把值插进去。
int i = j;
while(i>0 && temp < array[i-1])
{
array[i] = array[i - 1];
i--;
}
array[i] = temp;
}