插入排序(直接插入排序)

例子： 5 2 1 6 4 7 9 0 8 3

思路：类似于扑克牌的整理手牌的过程。 当前元素依次和前面的数比较，如果比前面的数大，就交换这两个数的位置。 如果比前面的数要大或者相等，说明找到了自己的合适位置，插入即可。

时间复杂度：O(n^2) n个数需要插入，每次插入需要比较n次

空间复杂度：O(1)

稳定性：稳定。

void InsertSort(int arr[], int size) { for (int i = 1; i < size; i++) { int key = arr[i]; //从下标1开始(下标为0的元素肯定是有序的)，一共有size-1个数需要排序 for (int j = i - 1; j >= 0; j--) { if (arr[i] >= arr[j]) { break; } else { int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; i = j; } } } }

---

希尔排序

例子：5 2 1 6 4 7 9 0 8 3

思路： 1.先将待排序序列分成若干个子序列，间隔长度一样的放在同一个序列中 2.将每个子序列进行直接插入排序 3.将增量减1，重复上述过程 4.最终直到增量为1时停止

时间复杂度：O(n^1.2 ~ n^1.3)

空间复杂度：O(1)

稳定性：不稳定

void _ShellSort(int arr[], int size, int gap) { //直接插入排序的过程，需要对每个区间内的元素进行排序 for (int i = gap; i < size; i++) { //gap是在同一个区间下，两个元素的间隔 for (int j = i - gap; j >= 0; j -= gap) { if (arr[i] > arr[j]) break; else { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i = j; } } } } void ShellSort(int arr[], int size) { int gap = size; while (1) { gap = gap / 3 + 1; _ShellSort(arr, size, gap); if (gap == 1) break; } }

gap = gap / 3 + 1; 间隔值的选择是由大量数据统计而来的，满足这个公式是能趋近最优值。