【028-毕业总结】

[Jerrydreamaker]

名称	原理	复杂度	稳定性
0 1 排序	使用 i 指向第一个 1，j 指向 i 后的第一个 0，swap(i++,j++)	O(n)	是
插入排序	对于元素索引i（i>=1），从头开始，若能找到比 a[i] 大对元素 a[j]，则记录 a[i] 的值，将索引 j~i-1 的元素向后移动一位，使用 a[i] 替换 a[j]。优化思路：针对数组可以采用二分查找找到当前元素的插入位置，链表不需要位移操作。	O(n^2/2)	是
选择排序	从当前元素开始遍历，记录最小值的索引，根据索引交换当前值的最小值，选择排序每次选出最小的元素和当前元素交换。选择排序基于链表实现，使用指针记录最小元素。选择排序最多只需进行 n 次赋值操作。	O(n^2/2)	是
堆排序	首先将队列中元素全部入堆，再将其依次出堆。堆，堆顶元素为堆中的最大（小）值的完全二叉树,完全二叉树,把元素顺序排成树的形状。Sift UP 原理：只有战胜底层子节点，才能向上。Sift Down 原理：临时小弟被打败。第 K 大元素（Top N）,使用 K 小顶堆。	O(n*log(2,n))
冒泡排序	从头到尾，发现前一位大于后一位，互换位置，第一排序保证数值最大的元素排到最后，尾部减 1。头尾相等时停止。冒泡排序交换次数多。	O(n^2/2)
快速排序	使用 parttion 函数，将数组中的第一个元素置于正确的顺序位置（左边元素比他小，右边大于等于），对基点左右的队列递归进行快速排序。快排的终止条件，左右界相等，则返回左界或右界。partition 函数：x 为第一个元素，小于 x 左边，大于等于 x 右边，左边初始数组 [-1,0)，右边初始数组[0,0], i 从位置 1 开始遍历,若小于 x，和右边数组的第一位置换，左右边数组向后移动一位。	O(n*log(2,n))
归并排序	对左边进行归并排序，得到数组 left，对右边进行归并排序，得到结果 right，合并 left 和 right，结束条件，进行归并排序到数组长度为 1 时，返回原数组，归并是一种外部排序。	O(n*log(2,n))