排序总结

插入排序

间接插入排序折半排序希尔排序
过程遍历将元素插入后面的有序队列之中在直接插入的根底上改良：通过折半查找找出要插入的地位通过设定步长对步长内的数组进行排序，屡次重复使得数组根本有序，之后应用间接插入排序
空间复杂度O（1）O（1）O（1）
比拟一个元素工夫复杂度最好（根本有序）：O（1）
最坏（程序相同）：O（n）		均匀：O(nlog2n)
总体工夫复杂度O（n^2）O(n^2)最好：O(n^(1/3))
最坏：O(n^2)
稳定性稳固稳固不稳固
适用性顺序存储和链式存储顺序存储和链式存储仅顺序存储
特点根本有序时效率最高，最初一趟开始之前所有元素可能都不在最终地位上组内排序应用间接插入排序

替换排序

冒泡排序疾速排序
过程每次找出一个最值放到队头或者队尾一直地将待排序表进行划分，右边都比两头小，左边都比两头大直到待排序表根本有序为止
空间复杂度O(1)最好状况：O（log2n）
最坏状况：O（n）
均匀：O（log2n）
比拟次数n(n-1)/2
工夫复杂度O(n^2)O(n^2)
稳定性稳固不稳固
特点元素雷同时不会进行替换保障了稳定性是所有外部排序算法中均匀效率最高的算法

抉择排序

简略抉择排序堆排序
过程遍历待排序表将最小（大）的放到后面，重复该过程先建设堆（大顶堆或小顶堆），输入堆顶数据后将堆底的数据放到堆顶而后向下调整。对堆进行排序则是从堆的最初一个元素开始进行排序，向上调整之后向下调整。
空间复杂度O(1)O(1)
比拟次数n(n-1)/2理论状况理论剖析
工夫复杂度O（n^2）O(nlog2n)（插入元素与删除元素的工夫复杂度都是）
稳定性不稳固稳固
特点调整工夫与树高无关，树越高调整工夫越长，堆能够视为一颗齐全二叉树，采纳顺序存储的形式且对于大顶堆的次大值肯定能在根的下一层，取出堆顶元素之后用堆最初一个元素替换堆顶元素后向下调整，若只是对堆进行排序则应该从最初一个元素开始进行排序。