插入排序算法

在了解如何改進插入排序之前，我們先要了解插入排序的基本算法：

算法講解

插入排序對于少量元素的排序，是一個有效的算法 。

插入排序是一種簡單的排序方法，它是將一個數據插入到已經排好序的有序數組，從而形成一個新的有序數組。

插入排序的工作方式像許多人排序撲克牌：

我們每次從桌子上拿走一張牌并將其插入到手中正確的位置。

為了找到它的正確位置，我們從右到左將它與手中的每張牌進行比較。

因此，手上的牌總是有序。

數據模擬

原本要排序的數為 5 3 4 2 9 1，從小到大排序。

3 5 4 2 9 1        // 將3放到合適的位置（5前面）3 4 5 2 9 1        // 將4放到合適的位置（3、5中間）2 3 4 5 9 1        // 將2放到合適的位置（最前面）2 3 4 5 9 1        // 將9放到合適的位置（最后面）1 2 3 4 5 9        // 將1放到合適的位置（最前面）

排序結束！！！

代碼

#include <iostream>
using namespace std;
int n,a[2000];        //定義數據個數n，排序數組a
int main()
{cin >>n;        //輸入個數for (int i=1;i<=n;i++)cin >>a[i];            //輸入數據for (int i=2;i<=n;i++)    //第一個數本身只有一個元素，所有有序，因此不用參與排序{int j,k=a[i];        //記錄下當前元素for (j=i-1;j>0;j--){if (a[j]>k)        //若前面一個數大于當前元素a[j+1]=a[j];    //則將前面一個元素往后移動elsebreak;        //否則：說明當前元素已經找到了合適的位置，推出循環}a[j+1]=k;        //將當前元素放入數組的合適的位置/*                        輸出排序的過程for (int j=1;j<=n;j++)cout <<a[j] <<" ";cout <<endl;*/}for (int i=1;i<=n;i++)cout <<a[i] <<" ";        //輸出排序好的數組return 0;
}

優化思路

我們發現，插入排序的過程浪費在了查找合適的位置上，那么怎么優化呢？

我們知道，插入排序一直在維護 前$i$個數是有序的，那么如何快速在有序的數列中查找一個小于（或大于）自己的數呢？

一、二分查找

二分！！！！

那么這樣我們就講查找的時間從$O(n)$縮短為$O(nlog(n))$！！

忍不住激動！！

可是找到位置不夠，還要進行移動啊。移動的時間復雜度是$O(n)$那么這樣非但沒有優化，反而還增加了查找的時間。。。

希望瞬間破滅！！

但是我會向它屈服嗎？？？

會 嗎？

明顯不會！

二、copy函數

我們可以使用一個$STL$庫里面的一個函數：

copy(a,a+n,a+1);

$copy$函數！！

這個函數可以在$O(1)$的時間范圍內將數組的某一段移動到，
使用方法：
以上面的操作為例子，這表明：

• 以$a$數組的第$0$位為開頭
• 以$a$數組的第$n?1$位位結尾
• 將它移動到開頭位第$1$位的位置

那么，這就好辦了，只需要要講兩個結合起來，一個速度與歸并排序相當，代碼比歸并排序簡短許多的超級優化插入排序代碼誕生了：

優化后代碼

#include <bits/stdc++.h>
#define N 2000000
using namespace std;
int n,x,y,f,t[N],k[N];
int main() {scanf("%d",&n);for (int i=1; i<=n; i++) {scanf("%d",&x);f=upper_bound(t+1,t+i,x)-t;		//記錄二分的位置copy(t+f,t+i,t+f+1);	//copyt[f]=x;		//存入數組}for (int i=1; i<=n; i++) {printf("%d ",t[i]);}return 0;
}

輸入數據：

5
4 9 1021 54 3

輸出數據：

3 4 9 54 1021

也是對了好吧~~

算法的用途

這個算法可以快速的在有序數列里面進行操作，也是異常的方便快捷，代碼超級簡短！！
下面給一道可以用這個算法解決的問題：

題目：數星星（POJ2352 star）

天文學家經常觀察星象圖。星象圖中用平面上的點來表示一顆星星，每一顆星星都有一個笛卡爾坐標。設定星星的等級為其左下角星星的總數。天文學家們想知道星星等級的分布情況。

比如上圖，$5$號星星的等級為$3$（其左下角有編號為$1$、$2$、$4$星星共三顆）。$2$號星星和$4$號星星的等級為$1$。在上圖中只有一顆星星等級為$0$，兩顆星星等級為$1$，一顆星星等級為$2$，一顆星星等級為$3$。
給定一個星象圖，請你寫一個程序計算各個等級的星星數目。

輸入輸出格式

輸入格式：

輸入的第一行包含星星的總數$N(1<=N<=15000)$。接下來$N$行，描述星星的坐標$(X,Y)$（$X$和$Y$用空格分開，$0\le X,Y\le 32000$）。星象圖中的每個點處最多只有一顆星星。所有星星按$Y$坐標升序排列。$Y$坐標相等的星星按$X$坐標升序排列。

輸出格式

輸出包含$N$行，每行一個整數。第一行包含等級$0$的星星數目，第二行包含等級$1$的星星數目，依此類推，最后一行包含等級為$N?1$的星星數目。

輸入輸出樣例

輸入樣例

5
1 1
5 1
7 1
3 3
5 5

輸出樣例

1
2
1
1
0

題目講解

由于輸入數據有序，所以在第$i$顆星星左下角的星星一定在$i$前面！！原理自己想想就知道了~~

所以其實就是求在點$i$前面的點中，有多少個的$X$坐標是比$i$的$X$坐標要小的，因此直接考慮插入排序做法：

步驟如下

• 輸入星星的數量 $n$
• 循環從$1$到$n$

• 每次輸入當前點的$X$和$Y$
• 用二分查找當前點的$X$應當放在哪個位置
• 用變了量$f$記錄位置，$f?1$就是當前星星的等級
• 用$copy$將數據，從當前合適的位置開始，到$i?1$往后移動一位
• 將當前數據存入排序數組
• 用另一個數組標記這個等級的星星$++$

• 循環輸出每個級別的星星

AC 代碼

#include <bits/stdc++.h>
#define N 20000
using namespace std;
int n,x,y,f,t[N],k[N];
int main() {scanf("%d",&n);for (int i=1; i<=n; i++) {scanf("%d%d",&x,&y);f=upper_bound(t+1,t+i,x)-t;copy(t+f,t+i,t+f+1);t[f]=x;k[f-1]++;}for (int i=0; i<n; i++) {printf("%d\n",k[i]);}return 0;
}