#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define N 200000
int b[N];
void init_array(int *a, int n)
{
int i;
srand(time(NULL));
for(i = 0; i < n; ++i)
a[i] = rand();
}
void bubble_sort(int *a, int n)
{
int i, j;
int temp;
for(i = 0; i < n-1; ++i)
for(j = i+1; j < n; ++j)
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
void select_sort(int *a, int n)
{
int i, j;
int min, index;
for(i = 0; i < n-1; ++i)
{
min = a[i];
index = i;
for(j = i+1; j < n; ++j)
if(min > a[j])
{
min = a[j];
index = j;
}
if(index != i)
{
a[index] = a[i];
a[i] = min;
}
}
}
void insert_sort(int *a, int n)
{
int i, j, k;
int temp;
for(i = 1; i < n; ++i)
if(a[i-1] > a[i])
{
temp = a[i];
for(j = i-1; j >= 0; --j)
if(temp >= a[j]) break;
for(k = i; k > j+1; --k)
a[k] = a[k-1];
a[j+1] = temp;
}
}
void quick_sort(int *a, int start, int end)
{
int i = start, j = end;
if(i >= j) return;
int temp = a[start];
while(i < j)
{
while(i < j && a[j] >= temp)
--j;
a[i] = a[j];
while(i < j && a[i] < temp)
++i;
a[j] = a[i];
}
a[i] = temp;
quick_sort(a, start, i-1);
quick_sort(a, i+1, end);
}
void my_merger_sort(int *a, int start, int middle, int end)
{
int i = start, j = middle+1, count = start;
while(i <= middle && j <= end)
if(a[i] <= a[j]) b[count++] = a[i++];
else b[count++] = a[j++];
if(i <= middle)
while(i <= middle)
b[count++] = a[i++];
else
while(j <= end)
b[count++] = a[j++];
for(i = start; i <= end; ++i)
a[i] = b[i];
}
void merger_sort(int *a, int start, int end)
{
if(start < end)
{
int middle = (start+end)/2;
merger_sort(a, start, middle);
merger_sort(a, middle+1, end);
my_merger_sort(a, start, middle, end);
}
}
void my_heap_sort(int *a, int i, int n)
{
int t = (i+1)*2;
int temp = a[i];
while(t <= n)
{
if(t == n)
--t;
else t = a[t]>=a[t-1]?t:t-1;
if(a[t] > a[i])
{
a[i] = a[t];
a[t] = temp;
i = t;
t = (i+1)*2;
}
else break;
}
}
void heap_sort(int *a, int n)
{
int i, temp;
for(i = n/2-1; i >= 0; --i)
my_heap_sort(a, i, n);
for(i = n-1; i > 0; --i)
{
temp = a[i];
a[i] = a[0];
a[0] = temp;
my_heap_sort(a, 0, i);
}
}
void print_array(int *a, int n)
{
int i;
for(i = 0; i < n; ++i)
printf("%d\n", a[i]);
}
int main()
{
int a[N];// = {5, 3, 8, 1, 4, 2, 9, 7, 6, 0};
init_array(a, N);
//bubble_sort(a, N); //冒泡
//select_sort(a, N); //选择
//insert_sort(a, 10); //插入
//quick_sort(a, 0, N-1); //快速
//merger_sort(a, 0, N-1); //归并
heap_sort(a, N); //堆
print_array(a, N);
return 0;
}
