Cの挿入ソート
データ構造を再学習します.
#include
typedef int ElemType;
void InsertSort(ElemType A[],int n);
void BInsertSort(ElemType A[],int n);
void ShellSort(ElemType A[],int n);
void print_arr(ElemType A[],int n);
int main()
{
int Arr[9] = {0,5,2,68,676,3,46,74,32};
int Arr_num = 8;
printf(" : ");
print_arr(Arr,Arr_num);
// printf("--- ---
");
// InsertSort(Arr,Arr_num);
// print_arr(Arr,Arr_num);
//
// printf("--- ---
");
// BInsertSort(Arr,Arr_num);
// print_arr(Arr,Arr_num);
printf("--- ---
");
ShellSort(Arr,Arr_num);
print_arr(Arr,Arr_num);
return 0;
}
//
// ,
//
// n~n^2
// 1
//
// n-1, n(n-1)/2, n^2/4
// 0, n(n+1)/2, n^2/4
void InsertSort(ElemType A[],int n)
{
int i,j;
for( i = 2; i <= n; i ++)
{
if( A[i] < A[i-1] )
{
A[0] = A[i];
for( j = i - 1; j > 0&&A[0] < A[j]; j --)// j ,
A[j + 1] = A[j];
A[j + 1] = A[0];
}
}
}
//
// ,
//
// n*log2(n)~n^2
// , n*log2(n)
// , 0, n(n+1)/2, n^2/4
void BInsertSort(ElemType A[],int n)
{
int i,j,low,high,mid;
for(i = 2; i <=n; i ++)
{
low = 0;
high = n - 1;
A[0] = A[i];
while(low <= high)
{
mid = (low + high) /2;
if(A[mid] > A[0]) high = mid - 1;
else low = mid + 1;
}
for(j = i - 1; j >= high + 1; j --)
{
A[j + 1] = A[j];
}
A[high + 1] = A[0];
}
}
//
// i,i+dk,i+2dk··· ,
// 1
// n^1.3~n^2
void ShellSort(ElemType A[],int n)
{
int dk;//
int count = 0;//
int i,j;
for(dk = n/2; dk >= 1; dk = dk/2)
{
++ count;
for(i = 1 + dk; i <= n; i ++)
{
if(A[i] < A[i - dk])
{
A[0] = A[i];
for(j = i - dk; j > 0 && A[0] < A[j]; j -= dk)//j>0 j - dk 0,
A[j + dk] = A[j];
A[j + dk] = A[0];
}
}
printf(" %d : ",count);
print_arr(A,n);//
}
}
void print_arr(ElemType A[],int n)
{
int i;
for(i = 1; i <= n; i++)
{
printf("%d ",A[i]);
}
printf("
");
}