实验题目：内排序
一、实验目的和任务
1 掌握堆排序、快速排序算法；
2 掌握直接插入排序、简单选择排序、气泡排序算法。
二、实验内容及原理
1给定一组元素，如（46,74,16,53,14,26,40,38,86,65,27,34），写出堆排序、快速排序算法及程序。
2复习之前学过的直接插入排序、简单选择排序、气泡排序，并写出相应的算法及程序。
3 如果此实验要求用外排序完成，参考书中的程序仿写外排序的相关程序。
四、实验数据及程序代码
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
struct ElemType {
int num;
int stn;
char bir[12];
};
void Sift(ElemType A[], int n, int i) //堆排序
{
ElemType x = A[i];
int j;
j = 2 * i + 1;
while (j <= n - 1) {
if (j<n - 1 && A[j].stn<A[j + 1].stn)j++;
if (x.stn<A[j].stn)
{
A[i] = A[j]; i = j; j = 2 * i + 1;
}
else break;
}
A[i] = x;
}
void HeapSort(ElemType A[], int n)
{
ElemType x;
int i;
for (i = n / 2 - 1; i >= 0; i--)Sift(A, n, i);
for (i = 1; i <= n - 1; i++)
{
x = A[0]; A[0] = A[n - i]; A[n - i] = x;
Sift(A, n - i, 0);
}
}
void QuickSort(ElemType A[], int s, int t) //快速排序
{
int i = s + 1, j = t;
ElemType x = A[s];
while (i <= j) {
while (A[i].stn <= x.stn && i <= j)i++;
while (A[j].stn >= x.stn && j >= i)j--;
if (i<j)
{
ElemType temp = A[i]; A[i] = A[j]; A[j] = temp;
i++; j--;
}
}
if (s != j) { A[s] = A[j]; A[j] = x; }
if (s<j - 1)QuickSort(A, s, j - 1);
if (j + 1<t)QuickSort(A, j + 1, t);
}
void InsertSort(ElemType A[], int n) //直接插入排序
{
ElemType x;
int i, j;
for (i = 1; i<n; i++)
{
x = A[i];
for (j = i - 1; j >= 0; j--)
if (x.stn<A[j].stn)A[j + 1] = A[j];
else break;
A[j + 1] = x;
}
}
void SelectSort(ElemType A[], int n) //直接选择排序
{
ElemType x;
int i, j, k;
for (i = 1; i <= n - 1; i++)
{
k = i - 1;
for (j = i; j <= n - 1; j++)
{
if (A[j].stn<A[k].stn)k = j;
}
if (k != i - 1)
{
x = A[i - 1]; A[i - 1] = A[k]; A[k] = x;
}
}
}
void BubbleSort(ElemType A[], int n) //冒泡排序
{
ElemType x;
int i, j, flag;
for (i = 1; i <= n - 1; j--)
{
flag = 0;
for (j = n - 1; j >= i; j--)
if (A[j].stn<A[j - 1].stn)
{
x = A[j - 1]; A[j - 1] = A[j]; A[j] = x;
flag = 1;
}
if (flag == 0) return;
}
}
void main()
{
int t[12] = { 46,74,16,53,14,26,40,38,86,65,27,34 };
int i,flag;
ElemType* a = new ElemType[12];
for (i = 0; i<12; i++)
{
cout << t[i] << ' ';
}
cout << endl <<"选择排序方式："<< endl <<"1.快速"<< endl <<"2.堆排序"<< endl <<"3.直接插入"<< endl <<"4.直接选择"<< endl <<"5.气泡排序"<< endl;
loop:for (i = 0; i<12; i++)
{
a[i].stn = t[i];
}
cin >> flag;
switch (flag)
{
case 2:
HeapSort(a, 12);
cout <<"堆排序结果"<< endl;
for (i = 0; i < 12; i++)
{
cout << a[i].stn <<"";
}
cout << endl;
break;
case 1:
QuickSort(a, 0, 11);
cout <<"快速排序结果"<< endl;
for (i = 0; i < 12; i++)
{
cout << a[i].stn <<"";
}
cout << endl;
break;
case 3:
InsertSort(a, 12);
cout <<"直接插入结果"<< endl;
for (i = 0; i < 12; i++)
{
cout << a[i].stn <<"";
}
cout << endl;
break;
case 4:
SelectSort(a, 12);
cout <<"直接选择结果"<< endl;
for (i = 0; i < 12; i++)
{
cout << a[i].stn <<"";
}
cout << endl;
break;
case 5:
BubbleSort(a, 12);
cout <<"气泡排序结果"<< endl;
for (i = 0; i < 12; i++)
{
cout << a[i].stn <<"";
}
cout << endl;
break;
default:
cout <<"输入错误";
break;
}
goto loop;
}
五、实验数据分析及处理
六、实验结论与感悟（或讨论）
因为在快速排序方法中存在着不相邻元素之间的交换，所以快速排序也是一种不稳定的排序方法。