#include<stdio.h>
#include<stdlib.h>
void bubbleSort(int arr[],int size);
void SelectionSort(int *arr, int size);
void InsertionSort(int *arr, int size);
void ShellSort(int *arr, int size);
void Merge(int *SR, int *TR, int i, int middle, int rightend);
void MergeSort(int *SR, int *TR1, int s, int t);
void swap(int *a, int *b) ;
void QuickSort(int *arr, int maxlen, int begin, int end);
void HeapSort(int *arr, int size);
void CountSort(int *arr,int n);
void bucketSort(int *arr, int size);
void RadixSort(int *arr, int len, int dec, int order);
int main()
{
int arr[10] = {1,9,6,3,5,2,4,8,7,10},i=0;
//BubbleSort(arr,10);
//SelectionSort(arr,10);
//InsertionSort(arr,10);
//ShellSort(arr,10);
//int arr_merge[10]={0};
//MergeSort(arr,arr_merge,0,9);
//QuickSort(arr,10,0,9);
//HeapSort(arr,9);
//CountSort(arr,10);
//bucketSort(arr,10);
RadixSort(arr,10,2,1);
for(i=0;i<10;i++)
{
printf("arr[%d] = %d
",i,arr[i]);
}
printf("
");
return 0;
}
/*冒泡排序*/
void BubbleSort(int arr[], int size)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++) {
for (j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j+1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
/*选择排序*/
void SelectionSort(int *arr, int size)
{
int i, j, k, tmp;
for (i = 0; i < size - 1; i++) {
k = i;
for (j = i + 1; j < size; j++) {
if (arr[j] < arr[k]) {
k = j;
}
}
tmp = arr[k];
arr[k] = arr[i];
arr[i] = tmp;
}
}
/*插入排序*/
void InsertionSort(int *arr, int size)
{
int i, j, tmp;
for (i = 1; i < size; i++) {
if (arr[i] < arr[i-1]) {
tmp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = tmp;
}
}
}
/*希尔排序*/
void ShellSort(int *arr, int size)
{
int i, j, tmp, increment;
for (increment = size/ 2; increment > 0; increment /= 2) {
for (i = increment; i < size; i++) {
tmp = arr[i];
for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {
arr[j + increment] = arr[j];
}
arr[j + increment] = tmp;
}
}
}
/*归并排序*/
void Merge(int source[],int temp[], int start, int mid, int end)
{
int i = start, j=mid+1, k = start;
while(i!=mid+1 && j!=end+1)
{
if(source[i] > source[j])
temp[k++] = source[j++];
else
temp[k++] = source[i++];
}
while(i != mid+1)
temp[k++] = source[i++];
while(j != end+1)
temp[k++] = source[j++];
for(i=start; i<=end; i++)
source[i] = temp[i];
}
//内部使用递归
void MergeSort(int source[], int temp[], int start, int end)
{
int mid;
if(start < end)
{
mid = start + (end-start) / 2;//避免溢出int
MergeSort(source, temp, start, mid);
MergeSort(source, temp, mid+1, end);
Merge(source, temp, start, mid, end);
}
}
/*快速排序*/
void QuickSort(int *arr, int maxlen, int begin, int end)
{
int i, j;
if (begin < end) {
i = begin + 1;
j = end;
while (i < j) {
if(arr[i] > arr[begin]) {
swap(&arr[i], &arr[j]);
j--;
} else {
i++;
}
}
if (arr[i] >= arr[begin]) {
i--;
}
swap(&arr[begin], &arr[i]);
QuickSort(arr, maxlen, begin, i);
QuickSort(arr, maxlen, j, end);
}
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void Heapify(int *arr, int m, int size)
{
int i, tmp;
tmp = arr[m];
for (i = 2 * m; i <= size; i *= 2) {
if (i + 1 <= size && arr[i] < arr[i+1]) {
i++;
}
if (arr[i] < tmp) {
break;
}
arr[m] = arr[i];
m = i;
}
arr[m] = tmp;
}
void BulidHeap(int *arr, int size)
{
int i;
for (i = size / 2; i > 0; i--) {
Heapify(arr, i, size);
}
}
void swap2(int *arr, int i, int j)
{
int tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/*堆排序*/
void HeapSort(int *arr, int size)
{
int i;
BulidHeap(arr, size);
for (i = size; i > 1; i--) {
swap2(arr, 1, i);
Heapify(arr, 1, i - 1);
}
}
/*计数排序*/
void CountSort(int data[],int n)
{
int i,j,count,*data_p;
data_p=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)//初始化data_p
data_p[i]=0;
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)//扫描待排序数组
if(data[j]<data[i])//统计比data[i]值小的值的个数
count++;
while(data_p[count]!=0)//对于相等非0的数据，应向后措一位。数据为0时，因数组data_p被初始化为0，故不受影响。
/* 注意此处应使用while循环进行判断，若用if条件则超过三个重复值后有0出现 */
count++;
data_p[count]=data[i];//存放到data_p中的对应位置
}
//用于检查当有多个数相同时的情况
i=0,j=n;
while(i<j)
{
if(data_p[i]==0)
{
int temp=i-1;
data_p[i]=data_p[temp];
}//of if
i++;
}//of while
for(i=0;i<n;i++)//把排序完的数据复制到data中
data[i]=data_p[i];
free(data_p);//释放data_p
}
/*桶排序*/
void bucketSort(int *arr, int size)
{
int i,j;
int buckets[size];
memset(buckets, 0, size * sizeof(int));
for (i = 0; i < size; i++) {
buckets[arr[i]]++;
}
for (i = 0, j = 0; i < size; i++) {
while((buckets[i]--) >0)
arr[j++] = i;
}
}
int get_index(int num, int dec, int order)
{
int i, j, n;
int index;
int div;
for (i = dec; i > order; i--) {
n = 1;
for (j = 0; j < dec - 1; j++)
n *= 10;
div = num / n;
num -= div * n;
dec--;
}
n = 1;
for (i = 0; i < order - 1; i++)
n *= 10;
index = num / n;
return index;
}
/*基数排序*/
void RadixSort(int *arr, int len, int dec, int order)
{
int i, j;
int index;
int tmp[len];
int num[10];
memset(num, 0, 10 * sizeof(int));
memset(tmp, 0, len * sizeof(int));
if (dec < order) {
return;
}
for (i = 0; i < len; i++) {
index = get_index(arr[i], dec, order);
num[index]++;
}
for (i = 1; i < 10; i++) {
num[i] += num[i-1];
}
for (i = len - 1; i >= 0; i--) {
index = get_index(arr[i], dec, order);
j = --num[index];
tmp[j] = arr[i];
}
for (i = 0; i < len; i++) {
arr[i] = tmp[i];
}
RadixSort(arr, len, dec, order+1);
}