数据结构 --- 排序算法_数据结构排序算法

1.冒泡排序

        第 i 个数与第 i+1 个数比较，若 i>i+1 则交换两者位置，否则接着比较 i+1 与 i+2大小，循环此过程。

2.选择排序

        找出序列中除第一个数以外最小的数，将该数与第一个数作比较，若该数小于第一个数，则交换位置，然后比较第二个数和其他数中最小数的大小。循环此过程。

3.插入排序

        对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

4.希尔排序

        插入排序的一种。将待排序序列分为多个组，分组公式为n/2，n为序列个数。然后再对每个组进行插入排序。重复此过程。第二次分组为 (n/2)/2。

5.快速排序

        (1) 在序列中选取一个数字为基准数取出，通常选取序列中第一个数。(序列空出第一个位置)

        (2) 然后定义L下标和R下标。先将基准数与R下标指向位置的数作比较。R下标指向的数字小于基准数时，将R下标指向的数字移动到序列空出的第一个位置（基准数之前所在的位置），然后比较L下标指向的数与基准数的大小。若之前R下标指向的数字大于基准数，则将R下标向左移动一个位置，继续与基准数作比较。

        (3) 直至基准数和序列所有元素比较完大小（L下标与R下标相遇时），将基准数放入L下标与R下标相遇的位置中。

        (4) 然后将基准数两边的序列重复(1)(2)操作，直至将序列排为有序序列。

6.归并排序

        (1) 将序列两两分为一组，然后将每组数据进行从小到大排序。

        (2) 然后将(1)中排序完成的组再进行两两分组，将每组数据机型从小到大排序。

        (3) 直至所有组合并为一整个序列

7.堆排序

        从大到小排序：

        (1) 将一个堆转换成大顶堆，然后将堆顶元素取出。

        (2) 将末尾节点移动至堆顶元素的位置，然后进行将该堆转换为大顶堆，再将堆顶元素取出，重复此过程。

8.计数排序，计数排序是一种基于 统计 的排序算法

        将序列中的数出现几次进行计数，然后将其取出进行排序。

9.桶排序

        将序列按数字的第一位放入桶中，然后将桶中的序列用其他排序算法进行排序，然后依次取出桶中数据。

10.基数排序

        桶排序的扩展。

        (1) 按个位分配到桶中，然后依次取出，在一个桶中的数字遵循先进先出原则。

        (2) 按十位分配

        (3) 按百位分配

11. 排序算法的时间、空间复杂度

• 堆排序的时间复杂度是（O(n*log(n))），堆排序中建堆过程的时间复杂度是（O(n)）
• in-place占用常数字内存，不占用额外内存
• out-place占用额外内存

12. 已知一颗二叉树的前序遍历顺序和后序遍历顺序不能唯一确定这棵二叉树，确定一颗二叉树必须知道这一颗二叉树的中序遍历