2路插入排序算法C#

2路插入排序算法，是在直接插入排序和折半插入排序算法上 再改进的。
主要目的是减少排序过程中的移动的记录次数。但是需要N个记录的辅助空间，

原理是：设置一个和原数组L 同类型，大小的是数组d，首先将L【0】赋值给D【0】。然后L【1】和D【0】比较，并且将D【0】看成是排好序中处于中间位置的记录，然后从L的第二个记录开始比较，依次插入到D【0】之前或者之后的有序序列中。
如果要排序的L【n】记录比D【0】 则插入到之前的序列中

重点是要把辅助数组看成是循环数组，设置first和final标识，来记录辅助数组的开头和结尾。first记录D的开头位置。final机制D的结尾位置，排好序以后，从first开始输出排序好的记录。。

c#代码


  public static void BinInsertSort(ref int[] array)
        {
            int[] tempArray = new int[array.Length];//辅助数组

            int first, final;//指示辅助数组的ffirst和final
            final = 0;
            first = array.Length ;
            tempArray[final] = array[0];//原数组的i第一个值给辅助数组的第一个位置

            for (int i = 1; i < array.Length; i++)
            {

                if (array[i] < tempArray[0])
                {
                    int m = 0;

                    if (first == array.Length)
                    {
                        tempArray[array.Length - 1] = array[i];
                        first = first - 1;
                    }
                    else
                    {

                        for (m = first; array[i] > tempArray[m] && m < array.Length - 1; ++m)
                        {
                            tempArray[m - 1] = tempArray[m];
                           
                        }

                        tempArray[m-1] = array[i];
                        first = first - 1;
                    }
                }
                else
                {
                    final = final +1;
                    int m = 0;
                    for (m = final; array[i] < tempArray[m - 1]; --m)
                    {
                        tempArray[m] = tempArray[m - 1];
                    }
                    tempArray[m] = array[i];
                }


              
            }
//排序好以后，根据first和final的位置输出，
            for (int n = first; n < array.Length; n++)
            {
                Console.WriteLine(array[n].ToString());
            }
            for (int n = 0; n <= final; n++)
            {
                Console.WriteLine(array[n].ToString());
            }
        }

本文使用Blog_Backup未注册版本导出，请到soft.pt42.com注册。