排序相关算法--1.插入排序+冒泡排序回顾

1.基本分类

2.插入排序

特点：有实践意义（例如后期快排的优化），适应性强，一般不会到时间复杂度最坏的情况。

1. 将第一个元素视为已经排好序的序列。
2. 取出下一个元素，在已经排好序的序列中从后往前比较，直到找到合适的位置插入。
3. 重复步骤2，直到所有元素都插入到合适的位置。

1. //插入排序
   #include<stdio.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;所以是i<n-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)（直接就有序）

（和插入排序是一样的）