编一程序对2种排序方法进行比较：交换法、选择法、插入法、冒泡法四种方法选2。具 体比较方法是随机生成一

发布网友 发布时间：2022-07-14 08:01

我来回答

共1个回答

热心网友 时间：2023-10-11 18:28

#include "stdio.h"
#include "time.h"
#include "stdlib.h"

void SimpleSelectSort(int arr[], int n, long *compare, long *swap);
void BubbleSort(int arr[], int n, long *compare, long *swap);
void GetRandomNumber(int arr[], int n, int max);

void main()
{
int i;
int max = 100;
int n = 300;
int arr[300];
long compare, swap;

GetRandomNumber(arr, n, max);

printf("Initial Array : \n");
for(i=0; i<n; i++)
{
if(i>0 && i%25==0)
printf("\n");
printf("%-3d", arr[i]);
}
printf("\n");

SimpleSelectSort(arr, n, &compare, &swap);
printf("After Simple Select Sorted\n");
printf("\tcompare : %ld\tswap : %ld\n", compare, swap);

BubbleSort(arr, n, &compare, &swap);
printf("After Simple Select Sorted\n");
printf("\tcompare : %ld\tswap : %ld\n", compare, swap);
}

/* 简单选择排序(选择类排序)，记录比较次数和交换次数 */
void SimpleSelectSort(int arr[], int n, long *compare, long *swap)
{
int i, j, k;
int temp;

*compare = 0;
*swap = 0;

for(i=0; i<n-1; i++)
{
k = i;
for(j=i+1; j<n; j++)
if(++(*compare) && arr[j] < arr[k])
k = j;
if(k != i)
{
(*swap)++;
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
}

/* 冒泡排序(交换类排序)，记录比较次数和交换次数 */
void BubbleSort(int arr[], int n, long *compare, long *swap)
{
int i, j;
int temp;

*compare = 0;
*swap = 0;

for(i=0; i<n-1; i++)
for(j=0; j<n-i-1; j++)
if(++(*compare) && arr[j] > arr[j+1])
{
(*swap)++;
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}

/* 得到一组随机数(<max)，存储在数组中 */
void GetRandomNumber(int arr[], int n, int max)
{
int i;
int temp;

srand(time(NULL));

for(i=0; i<n; i++)
arr[i] = rand() % max;
}