// 时间复杂度 O(N^2)voidInsertSort(int* arr, int n) {
for (int i = 0; i < n; ++i) {
int tmp = arr[i];
int end = i - 1;
while (end >= 0) {
if (arr[end] > tmp) {
arr[end + 1] = arr[end];
--end;
} else {
break;
}
}
arr[end + 1] = tmp;
}
}
若 end >= 0,说明应该继续比较当前 end 所处位置的关键码值与待排序关键码值的大小关系。若 end 位置的关键码值大,就将 end 位置的关键码值往后移一步,继续 --end,重复上述步骤,直到 end 位置的关键码值小于等于待排序的关键码值,跳出循环。此时 end+1 的位置就是待排序关键码值应该插入的位置。
void _MergeSort(int* arr, int left, int right, int* tmp) {
if (left >= right) {
return;
}
int mid = ((right - left) >> 1) + left;
// 划分左右区间// 左区间 [left,mid]// 右区间 [mid + 1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
// 进行合并int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] > arr[begin2]) {
tmp[index++] = arr[begin2++];
} else {
tmp[index++] = arr[begin1++];
}
}
// 若某子数组有剩余元素,则将该数组剩余元素依次填充while (begin1 <= end1) {
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2) {
tmp[index++] = arr[begin2++];
}
for (int i = left; i <= right; ++i) {
arr[i] = tmp[i];
}
}
// 归并排序voidMergeSort(int* arr, int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
对一个序列不断地进行划分左右区间,直到不能划分为止,再对子区间依次进行排序,合并即可。
6. 计数排序(非比较排序)
计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用,操作步骤:
统计相同元素出现次数。
根据统计的结果将序列回收到原来的序列中。
// 计数排序voidCountSort(int* arr, int n) {
// 求数组内最大,最小值int max = arr[0], min = arr[0];
for (int i = 0; i < n; ++i) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
// 开空间int gap = max - min + 1;
int* count = (int*)calloc(sizeof(int), gap);
// 统计每一个元素出现的次数for (int i = 0; i < n; ++i) {
count[arr[i] - min]++;
}
// 排序int index = 0;
for (int i = 0; i < gap; ++i) {
while (count[i]--) {
arr[index++] = i + min;
}
}
free(count);
}