数据结构——排序知识点_c++数据结构中什么是全局有序

1. 定义：
   按关键字进行递增（或递减）的有序排列

2.内排序和外排序
排序过程中不涉及数据的内外，交换称为内排序，反之，称为外排序
3.内排序的分类：
1.基于比较的排序：
1.插入排序：直接插入排序，折半插入排序，希尔排序
2.交换排序：冒泡排序，快速排序
3.选择排序：简单选择排序（直接选择排序），堆排序（利用二叉树进行排序）
4.归并排序（利用数组原理进行划分的排序）
2.不基于比较的排序：
基数排序
4.排序算法的稳定性：
经过排序后这些相同关键字的记录之间的相对位置次序保持不变的排序方法是稳定的，反之不稳定
5.排序的性能比较：主要是基于时间和空间复杂度，时间复杂度又是基于比较次数和移动次数。

10.2插入排序（基本思想为从无序区将关键字一个一个插入到有序区）：
主要方法：直接插入排序，折半插入排序，希尔排序
1.直接插入排序 最好时间O(n),最坏和平均时间O(n^2),空间O(1),稳定
基本思想：排序过程中，将待排序列划分为两个子区间，前面一个为有序区间，后面一个为无序区间，每次比较将无序区间第一个元素和有序区间进行比较。
2.折半插入排序 最坏时间和平均时间O(n^2)，空间复杂度O(1)，稳定。
3.希尔排序： 平均时间O(n^1.3) ，空间O(1