C语言归并排序与基数排序代码
时间: 2023-10-17 13:07:44 浏览: 44
归并排序代码:
```
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right)
{
int len = right - left + 1;
int *temp = (int*)malloc(sizeof(int)*len);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right)
{
if (arr[i] < arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (int m = 0; m < len; m++)
arr[left + m] = temp[m];
free(temp);
}
void merge_sort(int arr[], int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main()
{
int arr[] = { 3, 2, 1, 5, 4 };
int len = sizeof(arr) / sizeof(int);
merge_sort(arr, 0, len - 1);
for (int i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
```
基数排序代码:
```
#include <stdio.h>
#include <stdlib.h>
int get_max(int arr[], int len)
{
int max = arr[0];
for (int i = 1; i < len; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
void radix_sort(int arr[], int len)
{
int max = get_max(arr, len);
int *count = (int*)malloc(sizeof(int) * (max + 1));
int *temp = (int*)malloc(sizeof(int) * len);
int radix = 1;
while (max / radix > 0)
{
for (int i = 0; i < max + 1; i++)
count[i] = 0;
for (int i = 0; i < len; i++)
count[arr[i] / radix % 10]++;
for (int i = 1; i < max + 1; i++)
count[i] += count[i - 1];
for (int i = len - 1; i >= 0; i--)
temp[--count[arr[i] / radix % 10]] = arr[i];
for (int i = 0; i < len; i++)
arr[i] = temp[i];
radix *= 10;
}
free(count);
free(temp);
}
int main()
{
int arr[] = { 329, 457, 657, 839, 436, 720, 355 };
int len = sizeof(arr) / sizeof(int);
radix_sort(arr, len);
for (int i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
```