【028-毕业总结】 #291
Description
Jerrydreamaker
Issue body actions
| 名称 | 原理 | 复杂度 | 稳定性 |
|---|---|---|---|
| 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)) |
Reactions are currently unavailable