10_3_2.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

template <class T>
T BubbleSort(T r[], int n, int k)
{
	int i, j, count = 0;
	T t;
	for (i = 0; i < n; i++)
		for (j = 0; j < n - i; j++)
		{
			count++;
			if (r[j] > r[j + 1])
			{
				t		= r[j];
				r[j]		= r[j + 1];
				r[j + 1]	= t;
			}
		}
	// 验证排序的正确性
	for (i = 0; i < n; i++)
		cout << r[i] << " ";
	cout << endl;

	// 输出一共执行的次数
	cout << "一共执行了" << count << "次" << endl;

	return r[k - 1];
}

template <class T>
T SelectSort(T r[], int n, int k)
{
	int i, j, minIndex, count = 0;
	T t;
	for (i = 0; i < k; i++)
	{
		minIndex = i;
		for (j = i + 1; j < n; j++)
		{
			count++;
			if (r[j] < r[minIndex])
				minIndex = j;
		}
		if (minIndex != i)
		{
			t = r[i];
			r[i] = r[minIndex];
			r[minIndex] = t;
		}
	}
	// 验证排序的正确性
	for (i = 0; i < n; i++)
		cout << r[i] << " ";
	cout << endl;

	// 输出一共执行的次数
	cout << "一共执行了" << count << "次" << endl;

	return r[k - 1];
}

void main()
{
	const int N = 10;  // 这个数据可以修改
	int a[N];
	srand(time(NULL));
	for (int i = 0; i < N; i++)
	{
		a[i] = rand() % (N * 3);
	}
	cout << "第1小的数为：" << BubbleSort(a, N, 1) << endl;
	cout << "第3小的数为" << SelectSort(a, N, 3) << endl;
}