【插入排序】Insert_Sort

一、直接插入排序  void InsertSort(int *arr, int n) { int i, j, temp; for (i = 1; i < n; ++i) { if (arr[i] < arr[i - 1]) { temp = arr[i]; for (j = i - 1; j >= 0 && arr[j] > temp; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; } } }

注意：第一个元素是有序的，从第二个元素开始，首先要判断这个元素要不要插入，如果这个元素比前面的有序序列中的元素都大，就不需要插入。

二、直接插入排序（哨兵） void InsertSort(int *arr, int n) { int i, j; for (i = 2; i < n; ++i) { if (arr[i] < arr[i - 1]) { arr[0] = arr[i]; for (j = i - 1; j >= 0 && arr[j] > arr[0]; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = arr[0]; } } } 三、折半插入排序 void BinsertSort(int *arr, int n) { for (int i = 1; i < n; ++i) { int low = 0, high = i - 1, temp = arr[i]; while (low <= high) { int mid = (low + high) / 2; if (temp < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } for (int j = i - 1; j >= high + 1; j--) { arr[j + 1] = arr[j]; } arr[high + 1] = temp; } } 四、希尔排序 void ShellSort(int *arr, int n) { for (int d = n / 2; d >= 1; d /= 2) { for (int i = d; i < n; i++) { if (arr[i] < arr[i - d]) { int temp = arr[i]; int j; for (j = i - d; j >= 0 && arr[j] > temp; j -= d) { arr[j + d] = arr[j]; } arr[j + d] = temp; } } } }