分类: C/C++
2008-06-26 21:43:53
#include
using namespace std;
void DataInput(int * p, int c); // 输入函数
void DataCopy(int * dest1, int * dest2, int * dest3, int * source, int c); // 复制函数
void DataShow(int * p, int c); // 显示函数
void BubbleSort(int * p, int c); // 冒泡排序
void SelectSort(int * p, int c); // 选择排序
void QuickSort(int * p, int left, int right); // 快速排序
void InsertSort(int * p, int c); // 选择排序
int B_loop = 0; // 冒泡排序法循环次数
int B_exchange = 0; // 冒泡排序法交换次数
int S_loop = 0; // 选择排序法循环次数
int S_exchange = 0; // 选择排序法交换次数
int Q_loop = 0; // 快速排序法循环次数
int Q_exchange = 0; // 快速排序法交换次数
int I_loop = 0; // 快速排序法循环次数
int I_exchange = 0; // 快速排序法交换次数
int main()
{
int n;
while (1)
{
B_loop = 0;
B_exchange = 0;
S_loop = 0;
S_exchange = 0;
Q_loop = 0;
Q_exchange = 0;
cout << "请输入要存储数据的总个数:";
cin >> n;
while (cin.get() != '\n')
continue;
int * data = new int[n];
DataInput(data, n);
cout << "\n当前输入数据如下:\n\n";
DataShow(data, n);
int * datacopy1 = new int[n];
int * datacopy2 = new int[n];
int * datacopy3 = new int[n];
DataCopy(datacopy1, datacopy2, datacopy3, data, n);
BubbleSort(datacopy1, n);
cout << "\n冒泡法排序完成!循环" << B_loop << " 次,交换" << B_exchange << " 次.\n";
SelectSort(datacopy2, n);
cout << "\n选择法排序完成!循环" << S_loop << " 次,交换" << S_exchange << " 次.\n";
QuickSort(datacopy3, 0, n - 1);
cout << "\n快速法排序完成!循环" << Q_loop << " 次,交换" << Q_exchange << " 次.\n";
cout << "\n排序后,数据如下:\n\n";
DataShow(datacopy3, n);
cout << "\n输入回车,继续测试,输入其它退出程序 ";
if (cin.get() != '\n')
break;
cout << endl << endl;
}
cout << "\n程序结束,谢谢使用!^O^\n\n";
return 0;
}
void DataInput(int * p, int c)
{
cout << "\n逐个输入数据:\n";
for (int i = 0; i < c; ++i)
{
cout << "#" << i + 1 <<": ";
cin >> p[i];
while (cin.get() != '\n')
continue;
}
cout << "\n数据输入完毕!\n";
}
void DataCopy(int * dest1, int * dest2, int * dest3, int * source, int c)
{
for (int i = 0; i < c; ++i)
{
dest1[i] = source[i];
dest2[i] = source[i];
dest3[i] = source[i];
}
}
void DataShow(int * p, int c)
{
for (int i = 0; i < c; ++i)
{
cout.width(6);
cout << p[i];
if (i!=0 && i % 10 == 0)
cout << endl;
}
cout << endl;
}
void BubbleSort(int * p, int c)
{
int temp;
for (int i = 0; i < c; ++i)
{
for (int j = c - 1; j >=i; j--)
{
if (p[j] < p[j - 1])
{
temp = p[j - 1]; // 将较大放到后面
p[j - 1] = p[j];
p[j] = temp;
B_exchange++; // 交换次数加
}
}
B_loop++; // 循环次数加
}
}
void SelectSort(int * p, int c)
{
int i,j;
int min;
int IndexMin;
int temp;
for (i = 0; i < c-1; i++)
{
min = p[i];
pos = i;
for (j = i + 1; j < c; ++j)
{
if (p[j] < temp)
{
min = p[j];
IndexMin = j;
}
}
temp = p[i];
p[i] = p[IndexMin];
p[IndexMin]=temp;
}
}
void QuickSort(int * p, int left, int right)
{
int temp;
int i = left;
int j = right;
int middle = p[(left + right) / 2];
do
{
while ((p[i] < middle) && (i < right))
i++;
while ((p[j] > middle) && (j > left))
j--;
if (i <= j)
{
temp = p[i];
p[i] = p[j];
p[j] = temp;
i++;
j--;
Q_exchange++;
}
Q_loop++;
}while (i <= j);
if (left < j)
QuickSort(p, left, j);
if (right > i)
QuickSort(p, i, right);
}
void InsertSort(int * p, int c)
{
//......
}