软件设计师-排序算法

冒泡排序

• 每一趟冒泡排序，从第0个元素开始，和后面的元素比较，如果大于就交换，否则不变，每次冒泡可以把最大的元素放到最后一个，第一次冒泡的终点是n-1,第二趟的是n-2,直到最后剩下一个元素。
• 时间复杂度O(n^2)，稳定的排序算法

插入排序

• 在插入第i个元素是，前i-1个元素已经排序好，将第i个元素和i-1,i-2依次比较，找到插入的位置，并把插入位置及以后的依次后移
• 时间复杂度O(n^2)，稳定的排序算法

归并排序

• 两路归并排序的核心是将一维数组中前后相邻的两个有序序列归并为一个有序的序列
• 分治思想，把数组分成两个部分，对前后两个部分作归并排序，排序完合并，使用了递归，最后只有一个元素的时候递归返回
• 时间复杂度O(nlogn)，空间复杂度O(n)

堆排序

• 升序排序先构建大顶堆，然后每次把堆顶元素放到后面，再重新构建堆
• 时间复杂度O(nlogn)

希尔排序

• 取Gap作为增量，把相隔Gap的数字作直接插入排序，减少Gap直到1，数组有序
• 不稳定的排序算法，时间复杂度O(nlogn)，空间复杂度O(1)

快速排序

• 使用分治思想，选择一个锚点，一次排序后比锚点小的都在左边，大的都在右边，根据锚点的位置，递归调用快速排序
• 稳定，时间复杂度O(nlogn)，空间复杂度O(logn)