java简单排序-插入排序

淩亂°似流年 2024-02-17 17:40 22阅读 0赞

接下来我们看一下插入排序,插入排序呢其实就是选择一个数字找到合适的位置把他插入进去就OK,其实也是很简单的,基本思想就是我们选择默认的元素的,我们默认在他之前的元素都是有序的,那么我们就把我们选择的这个元素插入到合适的位置就OK.

比如有下边的数组:int a\[\] = \{ 6, 3, 1, 2, 3  \};我们如果采用插入排序该怎么做呢:

第一步:我们规定一个mark就是我们的需要插入的元素位置,我们默认选择mark就是1,也就是我们的第一个3元素,我们还需要定义一个compire来进行比较的控制,每一次的初识值就是我们的mark值也就是compire=1;

第二步:我们采用while循环,当我们的compire大于0,并且a\[compire-1\]位置的元素,也就是6,大于a\[mark\]=3位置的元素,那么就把a\[compire-1\]位置的元素6赋值给a\[compire\]位置,我们的compire减一操作,也就是为0,跳出while循环,然后把我们的a\[mark\]位置的元素赋值给a\[compire\],因为我们compire是进行过减一操作的,所以他的值就是a\[0\],比较完赋值之后我们的数组是a\{3,6,1,2,3\}

第二次循环:

第一步:mark=2,指向的元素是1,compire=2,a\[compire - 1\]=6,大于1,那么把3赋值给1的位置,compire--,即compire=1,代表的元素是3,大于1,把3赋值给a\[1\]的位置,compire--,跳出while循环,得到的数组是 a\[\]=\{1,3,6\}

我们发现我们执行完比较赋值之后每次选择的数子,左边都是有序的哎.

第三次循环:mark=3,compire=3;2和6,比较,和3比较,和1比较,共比较三次,得到的结果是a\[\]=\{1,2,3,6,3\}

第四次循环:mark=4,compire=4,第二个3和6比较和3比较,共比较两次得到的结果是:a\[\]=\{1,2,3,3,6\}

我们来看一下代码:

/**
     * Created by luyangli on 16-7-3.
     */
    public class InsertSort {
        public static void main(String[] args) {
            int a[] = { 6, 3, 1, 2, 3 };
            int mark, compire;
            for (mark = 1; mark < a.length; mark++) {
                int temp = a[mark];
                compire = mark;
                while (compire > 0 && a[compire - 1] > temp) {
                    a[compire] = a[compire - 1];
                    compire--;
                }
                a[compire] = temp;
            }
            System.out.println(Arrays.toString(a));
        }
    }

这个就是按照我们的思路来的,我们看下效果:

\[1, 2, 3, 3, 6\]

也是Ok的,插入排序呢就是选择要插入的元素,然后把他插入到合适的位置.......