一、实验目的与要求：
1、通过学习多种排序算法，体会对同一种操作多种不同的算法设计；通过比较各种排序算法对于数据存储结构的要求，体会算法设计不依赖于数据存储结构，而算法实现依赖于数据存储结构；通过分析排序算法的效率，研究如何进一步提高算法性能的方法。
2、要求掌握每种排序算法思路，算法描述，算法设计与算法实现手段，掌握排序算法时间复杂度和空间复杂度的分析方法，具有排序算法的设计能力。
二、任务描述：
1、编制程序实现插入排序
2、编制程序实现冒泡排序
3、编制程序实现快速排序
#include<iostream>
using namespace std;
#define Element int
const int DefaultSize=100;
class RecordList
{
public:
Element *R;
int MaxSize;//数组的大小
int CurrentSize;//真实的元素的个数
void Swap(Element &x,Element &y)
{
Element temp=x;x=y;y=temp;
}
RecordList(int MaxSz=DefaultSize)
{
R=new Element[MaxSz];
MaxSize=MaxSz;
CurrentSize=0;
}
//将元素e插入到顺序表的第i个元素之前
void Insert(Element e,int i)
{
for(int j=CurrentSize-1;j>=i-1;j--)
{
R[j+1] = R[j];
}
R[i-1]=e;
CurrentSize++;
}
void Print()
{
for(int i=0;i<CurrentSize;i++)
{
cout<<R[i]<<" ";
}
cout<<endl;
}
void InsertionSort();//直接插入排序
void BinaryInsertSort();//折半插入排序
void ShellSort();//希尔排序
void BubbleSort();//冒泡排序
void QuickSort();//快速排序
int Partition(int low,int high);//快速排序
void QSort(int low,int high);
};
void RecordList::InsertionSort()
{
int i,j;Element temp;
for(i=1;i<CurrentSize;i++)
{
temp=R[i];//将带排序数据存储于临时变量
//寻找合适的插入的下标j
for(j=i-1;j>=0;j--)
{
if(R[j]>temp) R[j+1]=R[j];
else //找到了一个合适的下标
break;
}
//j==-1 R[0]=temp或j之后的位置
R[j+1]=temp;//temp回填
}
}
void RecordList::BinaryInsertSort()
{
int i,j;Element temp;
int left,right,middle;
for(i=1;i<CurrentSize;i++)
{
temp=R[i];//将带排序数据存储于临时变量
//寻找合适的插入的下标j
left=0,right=i-1;
while(left<=right)
{
middle=(left+right)/2;
if(temp<R[middle]) right=middle-1;
else left=middle+1;
}
for(j=i-1;j>=left;j--)
R[j+1]=R[j];
//回填
R[left]=temp;
}
}
/*希尔排序
先讲整个待排序记录 分割 成为 若干个 子序列，
保证子序列在原始数组中不相邻 且间距gap相等
分别对每个子序列 进行直接插入排序;
然后减少记录间的间距，直到最后间距减小为1，
待整个序列中的记录 “基本有序”时，
再对全体记录进行一次直接插入排序
*/
void RecordList::ShellSort()
{
int gap=CurrentSize,i,j;Element temp;
do
{
gap/=3;
for(i=gap;i<CurrentSize;i++)
{
temp=R[i];
j=i;//j每趟 子序列的直接插入排序的比较的子下标
while(j>=gap&&temp<R[j-gap])
{
R[j]=R[j-gap];j=j-gap;
}
R[j]=temp;
}
}while(gap>=1);
}
/*
从数组末端R[n-1]开始，不断比较相邻元素，
若逆序则交换，第一趟冒泡可使最小元素浮到R[0]
继续第二轮冒泡，从R[1]-R[n-1]从确定最小元素
*/
//
void RecordList::BubbleSort()
{
int pass=1;//做冒泡的次数
int NoSwap=0;//是否交换过：初始值有交换过
while(pass<CurrentSize&&NoSwap==0)//最多CurrentSize-1
{
NoSwap=1;//每趟冒泡做之前均认为下面的两两元素都无需交换
//每趟的冒泡
for(int j=CurrentSize-1;j>=pass;j--)
{
if(R[j]<R[j-1])
{Swap(R[j],R[j-1]);NoSwap=0;}
}
pass++;
}
}
//基准值 枢轴值
//较基准值较大记录 从前面移动到后面
//较基准值较小记录 从后面移动到前面
void RecordList::QuickSort()
{
QSort(0,CurrentSize-1);
}
void RecordList::QSort(int low,int high)
{
if(low<high){
int pivotpos=Partition(low,high);
QSort(low,pivotpos-1);
QSort(pivotpos+1,high);
}
}
int RecordList::Partition(int low,int high)
{
//用子表第一个元素作枢轴记录
Element pivot=R[low];
while(low<high)
{
//high从后往前扫描，直到R[high]<pivot
//(在后面的区域找到了一个比pivot更小的数)
while(low<high&&R[high]>=pivot)high--;
//将R[high]移动到R[low]的位置
R[low]=R[high];
//low从前往后扫描，直到R[low]>pivot
while(low<high&&R[low]<=pivot) low++;
//将R[low]移动到R[high]的位置
R[high]=R[low];
}
R[low]=pivot;
return low;//low所在的位置
}
void main()
{
int data[20]={26,88,41,35,62,16,51,38,26};
RecordList list(20);
for(int i=1;i<=9;i++)
list.Insert(data[i-1],i);
list.Print();
list.QuickSort();
list.Print();
//list.BinaryInsertSort();
//list.Print();
}
