插入排序_C++

有一個已經有序的資料序列，要求在這個已經排好的資料序列中插入一個數，但要求插入後此資料序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是将一個資料插入到已經排好序的有序資料中，進而得到一個新的、個數加一的有序資料，算法适用于少量資料的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但将最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就隻包含這一個元素（即待插入元素）。在第一部分排序完成後，再将這個最後元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的檔案中适當位置上，直到全部插入完為止。