排序

一、实验目的与要求：
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();
}