René's URL Explorer Experiment

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