C++插入排序

发布时间:2023年12月19日

算法思想:

把一个待排序序列分为俩部分,有序部分和无序部分,把无序部分的第一个元素,按规定的次序插入到有序部分里面,这样无序部分就少了一个元素,循环次操作,知道序列中没有无序部分为止。

在刚开始的时候,无序部分为整个序列的第一个元素

算法实现:

法一:不带哨兵

#include <iostream>
?
using namespace std;
int nums[10005], n;
void InsertSort(int nums[], int n) {
    for (int i = 2; i <= n; i++) {//第一个元素只有它自己,肯定有序,所以从第二个元素开始寻找插入位置
        int t = nums[i];//t存储的是无序第一个元素
        int j;//j代表的是有序最后一个元素
        for (j = i-1; j >= 1 && nums[j] > t; j--) {//数组可能越界,所以要加j>=1去判断
            nums[j+1] = nums[j];//把j位置先空出来
            //但是它还要执行j--操作,所以真正要插入的位置不是j而是j+1
        }
        nums[j+1] = t;
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
    }
    InsertSort(nums, n);
    for (int i = 1; i <= n; i++) {
        cout << nums[i] << ' ';
    }
    return 0;
}

法二:带哨兵

又哨兵不用担心数组的越界问题

#include <iostream>
?
using namespace std;
int nums[10005], n;
void InsertSort(int nums[], int n) {
    for (int i = 2; i <= n; i++) {//第一个元素只有它自己,肯定有序,所以从第二个元素开始寻找插入位置
        nums[0] = nums[i];//把代插入元素放入哨兵位置
        int j;//j代表的是有序最后一个元素
        for (j = i-1;nums[j] > nums[0]; j--) {//数组可能越界,但是又哨兵看着,不用管越界情况了
            nums[j+1] = nums[j];//把j位置先空出来
            //但是它还要执行j--操作,所以真正要插入的位置不是j而是j+1
        }
        nums[j+1] = nums[0];
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
    }
    InsertSort(nums, n);
    for (int i = 1; i <= n; i++) {
        cout << nums[i] << ' ';
    }
    return 0;
}
文章来源:https://blog.csdn.net/m0_75178021/article/details/135066479
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。