3插入排序

发布时间: 2024-06-23 00:38:24

插入排序思想

回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。

例如:设n=8，数组a中8个元素是: 36,25,48,12,65,43,20,58，执行插入排序程序后，其数据变动情况：

第0步:[36] 25 48 12 65 43 20 58
第1步:[25 36] 48 12 65 43 20 58
第2步:[25 36 48] 12 65 43 20 58
第3步:[12 25 36 48] 65 43 20 58
第4步:[12 25 36 48 65] 43 20 58
第5步:[12 25 36 43 48 65] 20 58
第6步:[12 20 25 36 43 48 65] 58
第7步:[12 20 25 36 43 48 58 65]

#include <iostream>
using namespace std;
const int MAXN = 10001;
int main() {
    int n, i, j, k;
    float temp, a[MAXN];
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> a[i];  // 输入n个数

    for (i = 1; i < n; i++) {
        for (j = 0; j < i; j++) {//找前面所有数第一个大于等于自己的数，
            if (a[i] <= a[j]) {
                int temp = a[i];//把自己赋值存到temp 
                for (int k = i - 1; k >= j; k--) {找的一个大于等于自己的数起一直到自己前面的一个，整体相后移动
                    a[k + 1] = a[k];
                }
                a[j] = temp;//把自己查入到移动队列前头。
                break;
            }
        }
    }

    for (i = 0; i < n; i++)
        cout << a[i] << " ";  // 输出排序的结果
    return 0;
}

3插入排序

插入排序思想 ​

插入排序思想