### 直接插入排序算法 #### 定义与原理 直接插入排序(Insertion Sort)是一种简单的排序算法,其工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上通常采用in-place排序(即只需用到O(1)的额外空间),因而在从部分排序的数组出发逐步排序时,效率较高。 #### 算法步骤 1. **初始化**:将数组中的第一个元素视为已排序。 2. **遍历**:从第二个元素开始遍历整个数组。 3. **比较与插入**:对于每个元素,将其与前面已排序的元素进行比较,如果当前元素小于前一个元素,则将前一个元素向后移动一位,直到找到合适的位置插入当前元素。 4. **重复**:重复上述过程,直到所有元素都被正确插入到已排序序列中。 #### 示例代码解析 ```cpp void insert_sort(int nArray[], int nLong) { int j; // 循环遍历数组中的每个元素 for (int i = 1; i < nLong; i++) { int k = nArray[i]; // 当前需要插入的元素 // 将当前元素与已排序的元素比较 for (j = i - 1; j >= 0 && k < nArray[j]; j--) { nArray[j + 1] = nArray[j]; // 若当前元素较小,则将较大的元素后移 } nArray[j + 1] = k; // 在正确的位置插入当前元素 } // 输出排序后的数组 for (int i = 0; i < nLong; i++) { cout << nArray[i] << " "; } } ``` ### 选择排序算法 #### 定义与原理 选择排序(Selection Sort)也是一种简单的排序算法。它的基本思想是在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 #### 算法步骤 1. **初始化**:假设数组中的第一个元素是最小的。 2. **遍历**:从数组的第二个元素开始,遍历整个数组。 3. **查找最小值**:对于每个元素,如果发现比当前假设的最小值还要小,则更新最小值的位置。 4. **交换**:完成一轮遍历后,将找到的最小值与数组的起始位置的元素进行交换。 5. **重复**:重复上述过程,直到所有元素都排序完毕。 #### 示例代码解析 ```cpp void select_sort(int nArray[], int nLong) { // 遍历数组中的每个元素 for (int i = 0; i < nLong - 1; i++) { int k = i; // 当前假设的最小值的位置 // 查找最小值 for (int j = i + 1; j < nLong; j++) { if (nArray[k] > nArray[j]) { k = j; } } // 如果找到了更小的值,则进行交换 if (k != i) { int temp; temp = nArray[i]; nArray[i] = nArray[k]; nArray[k] = temp; } } // 输出排序后的数组 for (int i = 0; i < nLong; i++) { cout << nArray[i]; } } ``` #### 时间复杂度分析 - **直接插入排序**的时间复杂度为O(n^2),其中n是数组的长度。在最坏的情况下,每插入一个元素都需要比较并移动n-i次,因此总的时间复杂度为O(n^2)。 - **选择排序**的时间复杂度同样为O(n^2)。尽管每次只交换一次,但仍然需要遍历整个数组来找到最小值,因此时间复杂度也为O(n^2)。 #### 空间复杂度分析 - **直接插入排序**和**选择排序**都是原地排序算法,它们的空间复杂度均为O(1)。 这两种排序算法虽然简单易懂,但在处理大数据量时效率较低,适用于数据规模较小或者部分已排序的情况。
//排序练习
// array[]={5,2,1,6,8,9,3,4};
#include <iostream>
using namespace std;
//int sort_leng(int a[])
//{
// int n=sizeof(a)/sizeof(a[0]);
// return n;
//}
void select_sort(int nArray[],int nLong)
{
for(int i=0;i<nLong-1;i++)
{
int k = i;//用来记录指针下标
for(int j=i+1;j<nLong;j++)
{
if(nArray[k]>nArray[j])
{
k=j;
}
}
if(k!=i)
{
int temp;
temp = nArray[i];
nArray[i] = nArray[k];
nArray[k] = temp;
}
- 粉丝: 26
- 资源: 39
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于python和协同过滤算法的电影推荐系统
- 国际象棋棋子检测3-YOLO(v5至v9)、COCO、CreateML、Darknet、Paligemma、TFRecord数据集合集.rar
- Python毕业设计基于知识图谱的电影推荐系统源码(完整项目代码)
- 基于C++的简易图书管理系统(含exe可执行文件)
- 使用python爬取数据并采用Django搭建系统的前后台,使用Spark进行数据处理并进行电影推荐项目源码
- 商城蛋糕数据库sql源码
- 基于Spark的电影推荐系统源码(毕设)
- NET综合解决工具,windows平台必备
- ZZU 面向对象Java实验报告
- 2024年秋学季-C#课程的信息系统大作业winform