#include <stdlib.h>
#include <string.h>
#include "sort.h" //冒泡排序
int bubbleSort(int a[], int n)
{
int i, j;
for (i=n-; i>=; i--)
{
for (j=; j<i; j++)
{
if (a[j]>a[j+])
{//交换a[i]和a[j]，也可使用临时变量实现
a[j] += a[j+];
a[j+] = a[j] - a[j+];
a[j] = a[j] - a[j+];
}
}
}
return ;
} /***********编译器自带快排************/
int cmp(const void * a, const void * b)
{
return *(int *)a - *(int *)b;
} int quickSortC(int a[], int n)
{
qsort(a, n, sizeof(a[]), cmp);
return ;
}
/***********编译器自带快排************/ //直接插入排序
int insertSort(int a[], int n)
{
int i, j, k, tmp;
for (i=; i<n; i++)
{
for (j=; j<i; j++)
{
if (a[i]<a[j])//insert a[i] before a[j]
{
tmp = a[i];
for (k=i; k>j; k--)
{
a[k] = a[k-];
}
a[j] = tmp;
}
}
}
return ;
} //希尔排序（无监视哨，迭代，也可递归实现）
int shellSort(int a[], int n)
{
int i, j, k, tmp, group = , step = n/;
while (step > )
{
for (i=group+step; i<n; i+=step)
{
tmp = a[i];
for (j=group; j<i; j+=step)
{
if (a[j]>a[i])
{
for (k=i; k>j; k-=step)
{
a[k] = a[k-step];
}
a[j] = tmp;
}
}
}
step /= ;
}
return ;
} /*
归并排序，鼓捣了半天，还是写成两个子函数的明了
*/
int merge(int a[], int m, int b[], int n, int arr[])
{
int i=, j=, k=;
while (i<m && j<n)
{
arr[k++] = a[i]<b[j] ? a[i++] : b[j++];
}
if (i<m)
{
memcpy(&arr[k], &a[i], (m-i)*sizeof(int));
}
else if(j<n)
{
memcpy(&arr[k], &b[j], (n-j)*sizeof(int));
}
return ;
} int mergeSort(int a[], int len)
{
int i, j, k, step, g1, g2, m, n;
int * arr = (int *)malloc(sizeof(int)*len); for (step=; step<=len; step<<=)
{//
g1 = ;
g2 = g1 + step;
k = ;
memcpy(arr, a, len*sizeof(int));
for (i=g1,j=g2; g1<len; g1=g2+step, g2=g1+step)
{
//先处理不足两组的情况，即g2>=len的情况
m = g2<len ? step : len-g1;
n = g2+step<len ? step : len-g2;
if (g2>=len)//剩余末尾分组
{
memcpy(&a[k], &arr[g1], m*sizeof(int));
k += m;
break;
}
if(merge(&arr[g1], m, &arr[g2], n, &a[k]))
{
free(arr);
return ;
}
k += m+n;
}
}
free(arr);
return ;
}