C++插入排序算法实例
插入排序是排序中比较常见的一种,下面小编为大家整理了C++插入排序算法实例,希望能帮到大家!
现在比如有以下数据需要进行排序:
10 3 8 0 6 9 2
当使用插入排序进行升序排序时,排序的步骤是这样的:
10 3 8 0 6 9 2 // 取元素3,去和10进行对比
3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置;再取8与前一个元素10进行对比
3 8 10 0 6 9 2 // 同理移动10;然后8再和3比,8大于3,所以不再移动;如此重复下去
……
0 2 3 6 8 9 10
也就是说,我们每一次取一个元素,都要将该元素与之前已经排序好的元素进行比较。
插入排序的`最差时间复杂度为O(n^2)。同时,该算法不需要开辟额外的空间,都是在原空间上进行移动操作。
代码实现
复制代码 代码如下:
#include
using namespace std;
void InsertSort(int arr[], int length)
{
int temp;
for (int i = 1; i < length; ++i) // 从数组中的第二个元素开始
{
temp = arr[i]; // 记录当前的元素
int j = i - 1;
while (j >= 0 && temp < arr[j]) // 将当前元素与之前的已经排序好的序列元素进行挨个比较
{A
arr[j + 1] = arr[j]; // 已经排序好的序列整体向后移动
--j;A}
arr[j + 1] = temp; // 插入当前的元素
}
}
int main()
{
int arr[10] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5};
InsertSort(arr, 10);
for (int i = 0; i < 10; ++i)
{
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
-
C语言的移位操作符使用方法
位移位运算符是将数据看成二进制数,对其进行向左或向右移动若干位的运算。位移位运算符分为左移和右移两种,均为双目运算符。第一运算对象是移位对象,第二个运算对象是所移的二进制位数。以下是小编为大家搜索整理的C语言的移位操作符使用方法,希望能给大家带来帮...
-
C语言考试机试经验三部曲
全国计算机等级考试的持续升温,至使全国计算机等级考试证书已成为国家公务员、国家企事业单位工作人员、公司员工等上岗、加薪、提拔的必备条件。以下是本站小编整理的C语言考试机试经验三部曲,希望可以为您的考试带来帮助!第一部:备考篇名将不打无准备之仗,复习备...
-
二级C语言考试复习五要点
综观近几年全国计算机等级二级基础部分和C语言程序设计的题目,笔试中大多数考题是与大纲要求的基本内容一致的,难度不高,但内容十分广泛,应牢固掌握。以下是小编为您带来的二级C语言考试复习五要点,感谢您的阅读!一、了解试卷,胸中有数综观近几年全国计算机等级二级...
-
关于C语言精选模拟练习题
C语言是一个有结构化程序设计、具有变量作用域(variablescope)以及递归功能的过程式语言。下面是小编为大家整理的关于C语言精选模拟练习题,欢迎参考~5:请编写一个函数fun,它的功能是:比较两个字符串的长度,(不得调用c语言提供的`求字符串长度的函数),函数返回较长...