#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<math.h>
#include<time.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void PrintArray(int* a, int n)
{
int i = 0;
for (; i < n - 1; ++i)
{
printf("%d ", a[i]);
}
printf("%d\n", a[i]);
}
//自小到大
void InsertSort(int* a, int n)//直接插入
{
assert(a);
int i,j;
for (i = 1; i < n; i++)
{
if (a[i] < a[i - 1])
{
int temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
printf("第%02d趟:", i);
PrintArray(a, n);
}
}
void BubbleSort(int* a, int n)//冒泡排序
{
assert(a);
int i,j=n,k = 1;
int flag = 1;
while (flag)
{
flag = 0;
for (i = 1; i < j; i++)
{
if (a[i] < a[i - 1])
{
swap(&a[i], &a[i - 1]);
flag = 1;
}
}
j--;
if (flag)
{
printf("第%02d趟:", k++);
PrintArray(a, n);
}
}
}
void SelectionSort(int* a, int n)//直接选择
{
assert(a);
int min, i, j;
for (i = 0; i < n; i++)
{
min = i;
for (j = i; j < n; j++)
{
if (a[j] < a[min])
min = j;
}
swap(&a[i], &a[min]);
printf("第%02d趟:", i+1);
PrintArray(a, n);
}
}
void QuickSort(int* a, int left, int right, int n)//快速排序
{
assert(a);
if (left < right)
{
static int k = 1;
int i = left, j = right, x = a[left];
while (i < j)
{
while (i < j && a[j] >= x) // 从右向左找第一个小于x的数
j--;
if (i < j)
a[i++] = a[j];
while (i < j && a[i] < x) // 从左向右找第一个大于等于x的数
i++;
if (i < j)
a[j--] = a[i];
}
a[i] = x;
printf("第%02d趟:", k++);
PrintArray(a, n);
QuickSort(a, left, i - 1, n);
QuickSort(a, i + 1, right, n);// 递归调用
}
}
void MergeSort(int*a, int left, int right, int* temp)//归并排序
{
if (left >= right)
return;
int mid = (left + right) / 2;//left + ((right - left) >> 1);
int begin1, begin2, end1, end2;
int i = 0;
MergeSort(a, left, mid, temp);
MergeSort(a, mid + 1, right, temp);
begin1 = left;
end1 = mid;
begin2 = mid + 1;
end2 = right;
i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])
{
temp[i++] = a[begin2++];
}
else
{
temp[i++] = a[begin1++];
}
}
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
//memcpy(a + left, temp + left, end1-left);
for (i--; i >= left; i--)
{
a[i] = temp[i];
}
}
void table()
{
printf("请选择对该组数据进行排序的方法:\n");
printf("1.直接插入排序\n");
printf("2.希尔排序\n");
printf("3.冒泡排序\n");
printf("4.快速排序排序\n");
printf("5.简单选择排序\n");
printf("6.归并排序\n");
printf("0.退出\n");
}
int main()
{
int a[10] = { 9,4,3,2,5,6,1,7,0,8 };
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++)
a[i] = rand() % 100;//生成随机数组
int n = sizeof(a) / sizeof(a[0]);
int* temp = (int*)malloc(sizeof(int)*n);
int x = 0;
printf("排序前数组:");
PrintArray(a, n);
table();
scanf("%d", &x);
printf("第00趟:");
PrintArray(a, n);
switch (x)
{
case 1:
InsertSort(a, n);//直接插入
break;
case 3:
BubbleSort(a, n);//冒泡排序
break;
case 5:
SelectionSort(a, n);//直接选择
break;
case 6:
MergeSort(a, 0, n-1, temp);//归并排序
break;
case 0:
break;
}
printf("排序后数组:");
PrintArray(a, n);
system("pause");
return 0;
}