插入排序就這么簡(jiǎn)單

從上面已經(jīng)講解了冒泡和選擇排序了，本章主要講解的是插入排序谅辣，希望大家看完能夠理解并手寫(xiě)出插入排序的代碼沧竟，然后就通過(guò)面試了！如果我寫(xiě)得有錯(cuò)誤的地方也請(qǐng)大家在評(píng)論下指出带污。

插入排序介紹

來(lái)源百度百科：

插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的香到、個(gè)數(shù)加一的有序數(shù)據(jù)鱼冀，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)悠就。是穩(wěn)定的排序方法千绪。

將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中

• 將要排序的是一個(gè)亂的數(shù)組int[] arrays = {3, 2, 1, 3, 3};
• 在未知道數(shù)組元素的情況下，我們只能把數(shù)組的第一個(gè)元素作為已經(jīng)排好序的有序數(shù)據(jù)梗脾，也就是說(shuō)荸型，把{3}看成是已經(jīng)排好序的有序數(shù)據(jù)

一、第一趟排序

用數(shù)組的第二個(gè)數(shù)與第一個(gè)數(shù)(看成是已有序的數(shù)據(jù))比較

• 如果比第一個(gè)數(shù)大炸茧，那就不管他
• 如果比第一個(gè)數(shù)小瑞妇，將第一個(gè)數(shù)往后退一步鹉究，將第二個(gè)數(shù)插入第一個(gè)數(shù)去

    int temp;
    if (arrays[1] > arrays[0]) {
        //如果第二個(gè)數(shù)比第一個(gè)數(shù)大，直接跟上

    } else {
        //如果第二個(gè)數(shù)比第一個(gè)數(shù)小踪宠，將第一個(gè)數(shù)后退一個(gè)位置(將第二個(gè)數(shù)插進(jìn)去)
        temp = arrays[1];
        arrays[1] = arrays[0];
        arrays[0] = temp;

    }

    System.out.println("公眾號(hào)Java3y" + arrays);

image

二、第二趟排序

用數(shù)組的第三個(gè)數(shù)與已是有序的數(shù)據(jù){2,3}(剛才在第一趟排的)比較

• 如果比2大妈嘹，那就不管它
• 如果比2小柳琢，那就將2退一個(gè)位置，讓第三個(gè)數(shù)和1比較
  • 如果第三個(gè)數(shù)比1大润脸，那么將第三個(gè)數(shù)插入到2的位置上
  • 如果第三個(gè)數(shù)比1小柬脸，那么將1后退一步，將第三個(gè)數(shù)插入到1的位置上

    //第二趟排序--------------------

    if (arrays[2] > arrays[1]) {
        //如果第三個(gè)數(shù)比第二個(gè)數(shù)大毙驯，直接跟上

    } else {
        //如果第三個(gè)數(shù)比第二個(gè)數(shù)小倒堕，將第二個(gè)數(shù)往后退一個(gè)位置，讓第三個(gè)數(shù)跟第一個(gè)數(shù)比
        temp = arrays[2];
        arrays[2] = arrays[1];

        //如果第三個(gè)數(shù)比第一個(gè)大爆价，那就插入到第二個(gè)數(shù)中
        if (temp > arrays[0]) {
            arrays[1] = temp;
        } else {

            //如果第三個(gè)數(shù)比第一個(gè)小垦巴，將第三個(gè)數(shù)插入到第一個(gè)數(shù)前面
            int swapTemp = arrays[0];
            arrays[0] = temp;
            arrays[1] = swapTemp;

        }

    }
    System.out.println("公眾號(hào)Java3y" + arrays);

image

....

三、簡(jiǎn)化代碼

從前兩趟排序我們可以摸出的規(guī)律：

• 首先將已排序的數(shù)據(jù)看成一個(gè)整體
• 一個(gè)數(shù)組是需要n-1趟排序的铭段，總是用后一位跟已排序的數(shù)據(jù)比較(第一趟：第二位跟已排序的數(shù)據(jù)比骤宣，第二趟：第三位跟已排序的數(shù)據(jù)比）
• 用第三位和已排序的數(shù)據(jù)比，實(shí)際上就是讓第三位數(shù)跟兩個(gè)數(shù)比較序愚，只不過(guò)這兩個(gè)數(shù)是已經(jīng)排好序的而已憔披。而正是因?yàn)樗藕眯虻模覀兛梢?strong>使用一個(gè)循環(huán)就可以將我們比較的數(shù)據(jù)插入進(jìn)去

    //臨時(shí)變量
    int temp;

    //外層循環(huán)控制需要排序的趟數(shù)(從1開(kāi)始因?yàn)閷⒌?位看成了有序數(shù)據(jù))
    for (int i = 1; i < arrays.length; i++) {

        temp = arrays[i];

        //如果前一位(已排序的數(shù)據(jù))比當(dāng)前數(shù)據(jù)要大爸吮，那么就進(jìn)入循環(huán)比較[參考第二趟排序]
        while (arrays[i - 1] > temp) {

            //往后退一個(gè)位置芬膝，讓當(dāng)前數(shù)據(jù)與之前前位進(jìn)行比較
            arrays[i] = arrays[i - 1];

            //不斷往前，直到退出循環(huán)
            i--;

        }

        //退出了循環(huán)說(shuō)明找到了合適的位置了形娇，將當(dāng)前數(shù)據(jù)插入合適的位置中
        arrays[i] = temp;

    }

上面的代碼還缺少了一個(gè)條件：如果當(dāng)前比較的數(shù)據(jù)比已排序的數(shù)據(jù)都要小锰霜，那么while中的arrays[i - 1]會(huì)比0還要小，這會(huì)報(bào)錯(cuò)的桐早。

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at Main.main(Main.java:61)

我們應(yīng)該加上一個(gè)條件：i>=1時(shí)才可以锈遥，如果i=1了下次再進(jìn)去的時(shí)候就退出循環(huán)，讓當(dāng)前數(shù)據(jù)插入到[0]的位置上

所以完整的代碼是這樣的：

     //臨時(shí)變量
        int temp;

        //外層循環(huán)控制需要排序的趟數(shù)(從1開(kāi)始因?yàn)閷⒌?位看成了有序數(shù)據(jù))
        for (int i = 1; i < arrays.length; i++) {

            temp = arrays[i];

            //如果前一位(已排序的數(shù)據(jù))比當(dāng)前數(shù)據(jù)要大勘畔，那么就進(jìn)入循環(huán)比較[參考第二趟排序]
            while (i >= 1 && arrays[i - 1] > temp) {

                //往后退一個(gè)位置所灸，讓當(dāng)前數(shù)據(jù)與之前前位進(jìn)行比較
                arrays[i] = arrays[i - 1];

                //不斷往前，直到退出循環(huán)
                i--;

            }

            //退出了循環(huán)說(shuō)明找到了合適的位置了炫七，將當(dāng)前數(shù)據(jù)插入合適的位置中
            arrays[i] = temp;

        }
        System.out.println("公眾號(hào)Java3y" + arrays);

image

四爬立、插入排序優(yōu)化

二分查找插入排序的原理：是直接插入排序的一個(gè)變種，區(qū)別是：在有序區(qū)中查找新元素插入位置時(shí)万哪，為了減少元素比較次數(shù)提高效率侠驯，采用二分查找算法進(jìn)行插入位置的確定抡秆。

參考資料：http://www.cnblogs.com/heyuquan/p/insert-sort.html

五、擴(kuò)展閱讀

C語(yǔ)言實(shí)現(xiàn)第一種方式:

        void InsertSortArray ( int arr[], int n)
        {

            //int arr[]={2,99,3,1,22,88,7,77,54};
            for (int i = 1; i < n; i++)// 循環(huán)從第二個(gè)數(shù)組元素開(kāi)始
            {
                int temp = arr[i];//temp標(biāo)記為未排序的第一個(gè)元素
                while (i >= 0 && arr[i - 1] > temp) //將temp與已排序元素從大到小比較吟策，尋找temp應(yīng)插入的元素
                {
                    arr[i] = arr[i - 1];
                    i--;
                }
                arr[i] = temp;
            }

        }

C語(yǔ)言實(shí)現(xiàn)第二種方式:

        void insert ( int arr[], int n)
        {
            int key = arr[n];
            int i = n;
            while (arr[i - 1] > key) {
                arr[i] = arr[i - 1];
                i--;
                if (i == 0)
                    break;
            }
            arr[i] = key;
        }

        void insertionSort ( int arr[], int n)
        {
            int i;
            for (i = 1; i < n; i++) {
                insert(arr, i);
            }
        }

測(cè)試代碼:

  main()
        {
            int arr[] = {99, 2, 3, 1, 22, 88, 7, 77, 54};
            int i;
            insertionSort(arr, 9);
            for (int i = 0; i < 9; i++)
                cout << arr[i] << endl;
            return 0;
        }

參考資料:

• https://www.cnblogs.com/xiaoming0601/p/5862793.html
• http://blog.csdn.net/jianyuerensheng/article/details/51254415

如果文章有錯(cuò)的地方歡迎指正儒士，大家互相交流。習(xí)慣在微信看技術(shù)文章檩坚，想要獲取更多的Java資源的同學(xué)着撩，可以關(guān)注微信公眾號(hào):Java3y