一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

代码实现：

#include <iostream>
using namespace std;
int main() {
    int a[1000] = {0};
    int i = 0,n;
    cin>>n;
    do {
        cin >> a[i];
        i++;
    } while (i <n);
        for (int k = 0; k <n-1 ; ++k) {
            for (int j = k+1; j >0; --j) {
                if(a[j]<a[j-1])swap(a[j],a[j-1]);
                else break;
            }    
        }    
            
    for (int l = 0; l <n ; ++l) {
        cout<<a[l]<<" ";
    }
}

Previous Quiz

Back to Lesson

Next Topic