赞
踩
目录
将元素直接对已经有序序列(默认数组第一个元素为初始有序序列)进行遍历比较,直接插入到相应位置,插入位置之后的元素顺序后移一位,经过n-1趟插入完成排序。
例:
根据直接插入排序算法的实现原理可知,算法的时间主要耗费在了寻找元素待插入位置上,如果能够将这部分的时间降下来,那么就可以有效的提高算法速度。
而直接插入排序的主要应用场景就是在序列本身基本有序的情况下,算法在查找待插入位置时进行的比较和元素搬移操作较少。所以我们就可以通过一些方法来将序列调到基本有序的情况,即可提高算法的效率,由此前辈大佬设计出了希尔排序,具体实现可参照后续博文。
- #include<stdio.h>
-
- void InsertSort(int* array, int size);//直接插入排序
- void Print_Array(int* array, int size);//打印数组
-
- int main() {
- int array[] = { 3,1,5,8,4,0,2,7,6,1 };
- int length = sizeof(array) / sizeof(array[0]);
- printf("排序前:");
- Print_Array(array, length);
- InsertSort(array, length);
- printf("\n排序后:");
- Print_Array(array, length);
- return 0;
- }
-
- void InsertSort(int* array, int size) {//直接插入排序
- for (int i = 1; i < size; i++) {//从1开始循环,默认数组内第一个元素为有序序列
- int end = i - 1;//标记已排序序列最后位置下标
- int key = array[i];//依次拿取数组内元素
- while (end >= 0 && key < array[end]) {//key从前往后比较:小于当前元素,继续往前走
- array[end + 1] = array[end];//将当前元素往后移一个位置
- end--;
- }
- array[end + 1] = key;//key大于等于当前元素,插入到当前位置之后
- }
- }
-
- void Print_Array(int* array, int size) {//打印数组
- for (int i = 0; i < size; i++) {
- printf("%d ", array[i]);
- }
- }
1.元素集合越接近有序,直接插入排序算法的时间效率越高。
2.时间复杂度:
3.空间复杂度:O(1)
4.稳定性:稳定
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。