计数排序
计数排序是一种非比较排序。
原理:
代码:
void CountSort(int* nums, int numsSize) {
int max = nums[0], min = nums[0];
for (int i = 0; i < numsSize; i++) {
if (nums[i] > max) {
max = nums[i];
}
if (nums[i] < min) {
min = nums[i];
}
}
int range = (max - min) + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
//统计次数
for (int i = 0; i < numsSize; i++) {
count[nums[i] - min]++;
//count[nums[i] ]++;
}
int j = 0;
for (int i = 0; i < range; i++) {
while (count[i]--) {
nums[j++] = i + min;
//nums[j++] = i;
//++j;
}
}
free(count);
}
for循环中i的范围应该注意,是range不是numsSize。
归并排序
原理:
代码:
void _MergeSort(int* nums, int left, int right,int*tmp) {
if (left >= right) {
return;
}
int mid = (left + right) >> 1;
//[left,mid] [mid+1,right]有序后,即可进行归并
_MergeSort(nums, left, mid, tmp);
_MergeSort(nums, mid+1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2) {
if (nums[begin1] < nums[begin2]) {
tmp[index++] = nums[begin1++];
}
else {
tmp[index++] = nums[begin2++];
}
}
while (begin1 <= end1) {
tmp[index++] = nums[begin1++];
}
while (begin2 <= end2) {
tmp[index++] = nums[begin2++];
}
for (int i = left; i <= right; i++) {
nums[i] = tmp[i];
}
}
void MergeSort(int* nums, int numsSize) {
int* tmp = (int*)malloc(sizeof(int) * numsSize);
_MergeSort(nums, 0, numsSize - 1,tmp);
free(tmp);
}
归并排序核心是利用_MergeSort,然后在_MergeSort中分区间递归。
递归后归并。最小区间例如【0,0】【1,1】选小的往下放,然后拷贝回原数组。