phpcms v9网站建设入门,新闻博客软文自助推广,个人网站模板吧,网站建设在阿里云1.基本分类 2.插入排序
特点#xff1a;有实践意义#xff08;例如后期快排的优化#xff09;#xff0c;适应性强#xff0c;一般不会到时间复杂度最坏的情况。 将第一个元素视为已经排好序的序列。取出下一个元素#xff0c;在已经排好序的序列中从后往前比较#xf…1.基本分类 2.插入排序
特点有实践意义例如后期快排的优化适应性强一般不会到时间复杂度最坏的情况。 将第一个元素视为已经排好序的序列。取出下一个元素在已经排好序的序列中从后往前比较直到找到合适的位置插入。重复步骤2直到所有元素都插入到合适的位置。 //插入排序
#includestdio.h
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else {break;}}a[end 1] tmp;}
} 上图一种特殊情况此时不是break出来的而是一直进行--
所以不走else了,因此将最后一句放在外面无论是哪种情况都可以
单趟
排序先理解单趟然后加上循环
整清楚边界。因为是从0开始访问的所以只能访问到n-1;
因此在访问的时候只循环到n-2;,
i的最后一个值是n-2;所以是in-1; 计算插入排序的时间复杂度 时间复杂度计算最坏情况逆序就相当于一个等差数列O(N^2) N的平方。
最好顺序 O(N)只比一遍 介于两者中间。
3.冒泡排序回顾 特点没有实践意义一般只用于教学 在指针基础知识点合集2基础入门到深入理解中有用指针讲解过一遍。
如果不用今天再供一种不用指针的方法。
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int flag 0;for (int i 0; i n - j; i){//先排单趟if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);flag 1;}}if (flag 0){break;}}
}
计算插入排序的时间复杂度 时间复杂度计算最坏情况O(N^2) N的平方。
最好 O(N)直接就有序
和插入排序是一样的
