首先分门别类介绍各种算法的实现，最后汇总比较一下

排序算法

1.插入排序

直接插入排序

A[1…n],从i=2开始，一个一个找，找到A[i]在A[1…i-1]已排序好的位置排序

所以排n-1趟最好O（n），一般是O（n²）

折半插入排序

区别在于，找位置的时候用了二分法，但是注意查找快了，放入数据后的移动次数没有改变

所以还是O（n²）

希尔排序

区别在于每次分组进行直接插入排序，直到只分为一组。

时间复杂度可以突破o（n²）

2.交换排序

冒泡排序

左右交换比较，每次至少可以确定一个位置

时间复杂度O（n²）

快速排序

每次找一个基准，利用双指针法左右移动，找到基准位置，基准左右 大小分明。

时间复杂度O（nlg（n））

3.选择排序

直接选择排序

选好了放位置，比如A[1…i-1]排好了就从A[i…k]选一个放在第i个位置。

时间复杂度固定O（n²）

堆排序

堆排序一般用数组实现（从下标1开始），利用了完全二叉树的性质。

主要算法就是向上调整（插入）和向下调整（删除，建堆）

时间复杂度O（nlog（n））稳定

4.归并排序

二分法的应用。

主要是二分＋归并，归并过程是双指针法的应用

o（nlog（n））

至于基数排序，不需要比较，只是分配收集，这里不想多说了