Java数据结构与算法之数组排序——插入

心已赠人 2022-08-09 01:55 186阅读 0赞

1）算法的大概执行时间：
        A，对于随机顺序的数据进行插入排序需要O(N2)的时间
        B，当数据有序的时候，算法运行需要O(N)时间
        C，当数据基本有序的时候，算法几乎只需要O(N)时间
    2）不变性
        比outer变量下标号小的数据项都是局部有序的。
    3）思路
        A）设置一个outer标签，用于表示其左边的元素已经排好，初始位置为1。每经过一次循环，outer加1直到数组的最右端即末尾。
        B）设置一个临时变量temp，用来存储待插入的数据，即outer指向的数据。
        C）设置一个in标签，主要是用来确定具体插入outer左边哪一个位置。其判断的思路是，当in>0且它前一个值大于或等于临时变量temp时，就将该位置及以后的元素向右边移动，空出来的位置插入该元素。

源码示例

/** * 排序数组，用于对数组进行排序 * 采用插入排序 */
        public void insertSort()
        {
            //算法思想1st，设置一个外循环变量用以标记已经排好的数据
            for(int out = 1;out<elementPos;out++)
            {
                //算法思想2nd，设置一个临时变量用以标记待插入的数据
                int temp = randomArray[out];
                //算法思想3rd，设置内循环标志，用以标记排序过程中的移位即最终插入位置
                int in = out;
                while((in>0)&&(randomArray[in-1]>=temp))
                {
                    randomArray[in] = randomArray[in-1];//移动元素
                    --in;
                }
                randomArray[in] = temp;
            }
        }

其余代码见如下传送门  
[传送门][Link 1]

[Link 1]: http://blog.csdn.net/a80c51/article/details/48813903