数据结构----八大排序

一、时间复杂度+空间复杂度

口诀： “插冒归”,它很稳 "插冒归"喜欢选冒插，插完就方了（平均情况O（n^2))

二、八大排序

直接插入排序

一种最简单的排序方法，依次将每个元素插入到一个有序的序列中。

1.采用顺序查找法查找插入位置

代码实现：

2.直接插入排序，使用“哨兵”法

折半插入排序

代码实现：

希尔排序

对每一个子表进行直接插入排序
eg.38和13是子表，连续存储空间（逻辑关系，不是真的连续存储），依旧是顺序表，13插入38之前，38往后移一位，即交换位置

步长 d=n/2;
d=d/2;

代码实现：

希尔排序的速度通常要比直接插入排序块，它是一种不稳定的排序算法。

冒泡排序

代码实现：

从后两两对比，更小的往前放。

快速排序

口诀解析：选择第一个元素将它移至临时变量temp中作为基准元素，且离开这个位置，用low指针指向空位，最右边的第一个元素用high指针指向它，与temp比较大小，若大于等于它元素不动，high指针往前指一个继续比较，若小于temp则放入low的空位中，并且现在换成low指针去指向下一个数据，继续与temp比较大小，若小于等于则low指针往后移，若大于temp放在右边high处的空位，又改成high指针指向的元素与temp比较大小…当low和high指向同一位置是，将基准元素放入那个位置。
总之这是一个low++,high–的过程，元素移动则换针比较。1

代码实现：

简单选择排序

该算法在n个元素中通过n-1次比较找出最小元素

堆排序

归并排序

基数排序

1.看个位
2.看十位
不需要进行关键字的比较
它是链式存储，在排序中是队列的数据结构，非常稳定.

最后，码字不易，如果觉得对你有帮助的话请点个赞吧，关注我，一起学习，一起进步！