ソートアルゴリズムによる集約
7302 ワード
/*
===========================================================================
（ ， ）：
1、
， ，
。 ， 。
： a1,a2,a3,a4,a5， a2=a4， a1,a2,a4,a3,a5，
， a2 a4 ， a4 。 a1,a4,
a2,a3,a5 。
2、
， ， ， ；
， ， 。
3、
， 。
， 。
===========================================================================
*/
#include <stdio.h>
/*
================================================
：
： （ ）、
================================================
*/
/*
====================================================
：
， ；
，
。
。 O(n2)--[n ]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;
for (i=0; i<n-1; i++) /* ：~n-2 n-1 */
{
min = i; /* i ， */
for (j=i+1; j<n; j++)/* */
{
if (*(x+j) < *(x+min))
{
min = j; /* ， */
}
}
if (min != i) /* min ， */
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}
/*
================================================
：
： （ ）、
================================================
*/
/*
====================================================
：
， (n-1) [n>=2]
， n ， n
。 ， 。
。 O(n2)--[n ]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;
for (i=1; i<n; i++) /* ：~n-1 n-1 */
{
/*
i 。 ： ，
， ， ，
。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j--) /* ：j=i-1，j--， i ， 。*/
{
*(x+j+1) = *(x+j); /* 。 t ， ，j==-1， */
}
*(x+j+1) = t; /* i */
}
}
/*
================================================
：
： （ ）、
================================================
*/
/*
====================================================
：
， ，
， ，
。 ：
， 。
，
k， 。
。 O(n2)--[n ]
=====================================================
*/
void bubble_sort(int *x, int n)
{
int j, k, h, t;
for (h=n-1; h>0; h=k) /* */
{
for (j=0, k=0; j<h; j++) /* k=0， k*/
{
if (*(x+j) > *(x+j+1)) /* ， */
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /* */
k = j; /* 。 k 。*/
}
}
}
}
/*
================================================
：
： （ ）、
================================================
*/
/*
====================================================
：
， ， ，
。 （
） ， ，
。D.L.shell
。 d ，
d. ，
， 。 ，
， 。
， ，
， 。
。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h>0; h=h/2) /* */
{
for (j=h; j<n; j++) /* */
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}
/*
================================================
：
： （ ）、
================================================
*/
/*
====================================================
：
。
， 。 ，
，
。 ， （ ）
， 。
， 。
C.A.R.Hoare 。
， 。
， 。
。 O(nlog2n)， O(n2)
=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;
if (low < high) /* ， ， 。 low */
{
i = low;
j = high;
t = *(x+low); /* */
while (i<j) /* */
{
while (i<j && *(x+j)>t) /* */
{
j--; /* */
}
if (i<j)
{
*(x+i) = *(x+j); /* ： ， */
i++; /* ， */
}
while (i<j && *(x+i)<=t) /* */
{
i++; /* */
}
if (i<j)
{
*(x+j) = *(x+i); /* ： ， */
j--; /* */
}
}
*(x+i) = t; /* ， */
quick_sort(x,low,i-1); /* */
quick_sort(x,i+1,high); /* */
}
}
/*
================================================
：
： （ ）、
================================================
*/
/*
====================================================
：
， 。
： n （h1,h2,...,hn),
（hi>=h2i,hi>=2i+1） （hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)
。 。
， （ ） 。
。 ， 、 。
， ，
， 。
。 (n-1) 。 ，
， ， n 。
， ， ，
。 。 ，
。
。 O(nlog2n)。
*/
/*
：
： （ ）、 、
*/
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x+s); /* */
k = s; /* */
j = 2*k + 1; /* */
while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/* ： ， 。*/
{
j++;
}
if (t<*(x+j)) /* */
{
*(x+k) = *(x+j);
k = j; /* ， */
j = 2*k + 1;
}
else /* ， ， 。*/
{
}
}
*(x+k) = t; /* */
}
/*
：
： （ ）、
*/
void heap_sort(int *x, int n)
{
int i, k, t;
for (i=n/2-1; i>=0; i--)
{
sift(x,n,i); /* */
}
for (k=n-1; k>=1; k--)
{
t = *(x+0); /* */
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0); /* */
}
}
#define MAX 4
int main()
{
int *p, i, a[MAX];
/* */
p = a;
printf("Input %d number for sorting.
",MAX);
for (i=0; i<MAX; i++)
{
scanf("%d",p++);
}
printf("
");
/* */
/*
p = a;
select_sort(p, MAX);
/**/
/* */
/*
p = a;
insert_sort(p,MAX);
*/
/* */
/*
p = a;
insert_sort(p,MAX);
*/
/* */
p = a;
quick_sort(p,0,MAX-1);
/**/
/* */
/*
p = a;
heap_sort(p,MAX);
*/
for (p=a, i=0; i<MAX; i++)
{
printf("%d ",*p++);
}
printf("
");
return 1;
}