当前位置: 首页> 健康> 美食 > 博购企业名录搜索软件_如何快速搭建个人网站_中国万网_百度极速版app下载安装

博购企业名录搜索软件_如何快速搭建个人网站_中国万网_百度极速版app下载安装

时间:2025/7/10 2:58:01来源:https://blog.csdn.net/kupe87826/article/details/146170424 浏览次数:1次
博购企业名录搜索软件_如何快速搭建个人网站_中国万网_百度极速版app下载安装

一  算法原理
       插入排序是稳定的原地排序算法,核心思想是逐步构建有序序列。对于未排序部分的每个元素,在已排序序列中从后向前扫描,找到合适位置插入。时间复杂度为:
1)最优:O(n)(已有序)
2)最差:O(n^2)(完全逆序)

3)平均:O(n^2)

 

二  排序过程

      以数组 [6 5 7 8 2] 为例的逐步过程。

1.  初始状态
  
   [6 | 5 7 8 2]  // 已排序区:6,未排序区:5 7 8 2
   

2. 插入5  
   5 < 6 → 交换  
   
   [5 6 | 7 8 2]  // 已排序区:5 6
   

3.  插入7
   7 > 6 → 不移动  
   
   [5 6 7 | 8 2]  // 已排序区:5 6 7
   

4. 插入8
   8 > 7 → 不移动  
 
   [5 6 7 8 | 2]  // 已排序区:5 6 7 8
   

5. 插入2
   2 < 8 → 后移8  
   2 < 7 → 后移7  
   2 < 6 → 后移6  
   2 < 5 → 后移5  
   插入到首位  
   
   [2 5 6 7 8]    // 排序完成
   

 

三   C++ 代码实现


#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {       // 从第二个元素开始遍历
        int temp = arr[i];              // 保存当前待插入元素
        int j = i - 1;                  // 已排序区的末尾索引
        
        // 从后向前扫描,寻找插入位置
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];        // 元素后移
            j--;
        }

        if(j!=(i-1))//j 已经变化,说明需要插入
        arr[j + 1] = temp;              // 插入到正确位置
    }
}

int main() {
    int arr[] = {6, 5, 7, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    insertionSort(arr, n);
    
    cout << "排序结果: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}
 

 

四 关键代码解析
1. 外层循环 (i 从1到n-1)  
   逐个处理未排序区的元素。

2. 内层循环(while (j >= 0 && arr[j] > temp))  
   通过后移操作腾出插入位置

3. 时间复杂度分析
   - 最优情况(已有序):仅需比较n-1次  O(n)
   - 最差情况(完全逆序):总比较次数n(n-1)/2    O(n^2)

 

五  总结
插入排序适合:
1)小规模数据(n  <1000);
2)数据基本有序的场景;
3)需要稳定排序的场景。

       通过逐步调整元素位置,以线性时间复杂度完成局部排序,最终达成全局有序。

 

关键字:博购企业名录搜索软件_如何快速搭建个人网站_中国万网_百度极速版app下载安装

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: