一、插入排序
插入排序：从第二项开始，依次和离自己最近的项比较，若前面的一项比自己大则插入到前面当中，若比自己位置小则位置不变，直到前面的一项比自己小为止。
（*图片来源：排序算法：插入排序【图解+代码】_哔哩哔哩_bilibili*）
如上图红色的为排好的，蓝色为未进行排序的（前面跑完程序的项，是按照从小到大的顺序排列的）
代码演示：
#include
void print_array(int a[], int n) {/* 打印数组的函数*/
for (int i = 0; i < n; i++ ) {
printf("%d ", a[i]);
}
printf("\n");
}
void insertion_sort(int a[], int n) {/*插入排序函数*/
print_array(a, n);
for(int i = 1; i < n; i++){/*最外层为从第二项起开始进行插入排序的循环*/
int key = a[i];
int j = i - 1;
while(j >= 0 && a[j] > key) {
a[j+1] = a[j];
j--;/*进行完第一次比较后进行第二次比较，因为前面进行完的项都是排好的所以第一次都比不过就不用比第二次了*/
}
a[j+1] = key;/*相当于key进行了插入*/
print_array(a,n);
}
}
int main(void) {
int a[10] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3, };
insertion_sort(a, 10);
return 0;
}
时间复杂度计算：
最好的情况：
O（10-1） 也就是 O（n-1），1为常量所以时间复杂度可以看为O（n）
最坏的情况：
O（（9+0）*10/2）也就是O（（n-1）*n/2） -1可以抹去，n*n/2。1/2系数可以看为1。所以时间复杂度为O（n*n）
时间复杂度计算中为什么把常数看为1：时间复杂度的计算的主要目的是：1.从基础理论出发，来查看代码能不能跑；2.随着变量n数值的增加，运行时间的增长快慢；而不是对于代码运行时间的准确计算
二、快速排序
快速排序：
基本思路：
以最后一个项为基准，将前面的项一从左到右的形式和基准作比较，比基准小的放到基准的左边，比基准大的放到基准的右边，按照比较的先后顺序进行放置（如2比1先比较，所以2放在1的左边（前面）。）。
3基准有左右两组，左边以1为基准开始进行快速排序，右边以6为基准进行快速排序
由此以此类推直到所有项都成为基准准为止
代码思路：
核心思路是：把小的放到前面去（快速排序只需将小的和大的放到基准的左右，快速排序中将小的放到基准左边，大的自然就放在了右边）
将第一项标记为指针i和j，最后一项为指针pivot
指针j有第一项开始从左往右扫，扫到比基准小的，指针j对应的数值和i的进行对换，同时指针i向前移一位。
最后j扫到基准时，指针pivot的值和i进行对换
由此以此类推，最后把所有的项都当成基准快速排列完；
由于本人能力有限，用文字比较难讲大家看视频吧
排序算法：快速排序【图解+代码】_哔哩哔哩_bilibili
代码：
#include
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right) {
int i, j, t, temp;
if(left > right)
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while(i != j) { //顺序很重要，要先从右边开始找
while(a[j] >= temp && i < j)
j--;
while(a[i] <= temp && i < j)//再找右边的
i++;
if(i < j)//交换两个数在数组中的位置
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
int main() {
int i;
//读入数据
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
quicksort(1, n); //快速排序调用
//输出排序后的结果
for(i = 1; i < n; i++)
printf("%d ", a[i]);
printf("%d\n", a[n]);
return 0;
}
最优情况下的时间复杂度计算：
最优情况为：每组的基准正好平分数组， 此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
T[n] = 2T[n/2] + n —————-第一次递归，令：n = n
T[n] = 2 { 2 T[n/4] + (n/2) } + n —————-第二次递归，令：n = n/2
= = 2^2 T[ n/ (2^2) ] + 2n
T[n] = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n —————-第三次递归 令：n = n/(2^2)
= 2^3 T[ n/ (2^3) ] + 3n
T[n] = 2^m T[1] + mn —————-第m次递归(m次后结束)， 令：n = n/( 2^(m-1) )
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
T[n] = 2^m T[1] + mn ；其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数
又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；（为什么最后取nlogn，因为n+nlogn=n（logn+1）常数+1可以忽略不计）
综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )
时间复杂度的计算引用这篇文章：
(39条消息) 排序算法之快速排序及其时间复杂度的计算_Never-Giveup的博客-CSDN博客_快速排序的时间复杂度怎么算
补充：
时间复杂度：
时间复杂度的大O指的是是什么呢？
算法导论：大O用来表示的上界
如插入排序O（n^2），但如果按照算法导论的解释，快速排序理应也是O（n^2），
但它却是O( nlogn )。所以大O指的是时间的一般情况，而不是严格的上界。
参考：
关于时间复杂度，你不知道的都在这里！ | 代码随想录 (programmercarl.com)
好文阅读
发表评论