几种常见的排序-数据结构课程设计

/*
Name:排序
Author:wujilin
Description:几种常见的排序方法
Date: 19-07-06 15:41
Copyright:wujilin
*/

#include<stdio.h>
#include<stdlib.h>
#define M 11

void InsertSort(int a[])//插入排序
{
int i, j;

for (i = 2; i < M; i++)
{
if(a[i] < a[i-1])
{
a[0] = a[i];
a[i] = a[i-1];
for (j = i - 2; j > 0 && a[j] > a[0]; j--)
{
a[j+1] = a[j];
}
a[j+1] = a[0];
}
}

printf("进行插入排序:");
for ( i = 1 ; i < M; i++)
{
printf("%4d",a[i]);
}
printf("\n");
}

void BinarySort(int a[])//折半排序
{
int i, j, m, low, high;

for (i = 2; i < M; i++)
{
a[0] = a[i];
low = 1;
high = i - 1;

while (low <= high)
{
m = (low + high)/2;
if (a[0] > a[m])
{
low = m + 1;
}
else
{
high = m - 1;
}
}
for ( j = i - 1; j > high  ; j--)
{
a[j+1] = a[j];
}
a[j+1] = a[0];
}

printf("进行折半排序:");
for (i = 1; i < M ; i++)
{
printf("%4d",a[i]);
}
printf("\n");
}

void Bubble(int a[])//冒泡排序
{
int i, j, temp;
int flag = 1;

for ( i = 1; i < 10; i++)
{
flag = 0;
for (j = i + 1; j <= 10; j++)
{
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
flag = 1;
}
}
}

printf("进行起泡排序:");
for ( i = 1; i <= 10; i++)
{
printf("%4d", a[i]);
}
printf("\n");
}

void HeapSort(int a[])//堆排序
{
int i;

for (i = (M-1)/2; i > 0 ; i--)
{
HeapAdjust(a, i, M-1);
}
for (i = M - 1 ; i > 0 ; )
{
a[0] = a[i];
a[i] = a[1];
a[1] = a[0];
i--;
HeapAdjust(a, 1, i);
}
printf("进行堆排序:");
for ( i = 1; i < M ; i++)
{
printf("%4d", a[i]);
}
printf("\n");
}

int HeapAdjust(int a[], int i, int n)
{
int j, k;
int flag = 1;

j = 2 * i;
k = a[i];
while (j <= n && flag == 1)
{
if (j < n && a[j] < a[j+1])
{
j++;
}
if (k >= a[j])
{
flag = 0;
}
else
{
a[j/2] = a[j];
j *= 2;
}
}
a[j/2] = k;

return 0;
}

void ShellSort(int a[])//希尔排序
{
int k, i, j, temp;

k = M-1/2;
for (; k > 0; k--)
{
for (i = k + 1; i <= 10; i++)
{
j = i - k;
while (j > 0)
{
if (a[j] > a[i])
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
j = j - k;
}
}
}

printf("进行希尔排序:");
for ( i = 1; i < M; i++)
{
printf("%4d",a[i]);
}
printf("\n");
}

[1] [2] 下一页