#include<iostream>
#include<ctime>
#define Swap(i,j) {int s = (i); (i) = (j); (j) = s;}
const int MAXSIZE = 30;
int array[MAXSIZE];
/*直接插入排序
基本思想:当插入第I个元素时,前面的V[0],V[1]....V[I-1]已经排好序,这时用V[I]的排序码与
V[I-1],V[I-2]....的排序码进行比较,找到插入位置即将V[I]插入,原来位置上的元素向后移.
*/

void InsertSort(int (&array)[MAXSIZE],const int left,int const right)
{
    for (int i=left+1;i<=right;i++)
    {
        if (array[i] < array[i-1])
        {
            int temp = array[i], j = i-1;
            do
            {
                array[j+1] = array[j]; j--;
            }
            while (j >= left && temp < array[j]);
            array[j+1] = temp;
        }
    }
}

/*折半插入排序(二分法插入排序)
基本思想:设在数据表中有一个元素序列V[0],V[1]...V[n-1].其中V[0],V[1]...V[I-1]
是已经排好序的元素.在插入V[I]时,得用折半搜索寻找V[I]的插入位置.
*/

void BinaryInsertSort(int (&array)[MAXSIZE],int left,int right)
{
    for (int i=left+1;i<=right;i++)
    {
        int temp = array[i];
        while (left<=right)
        {
            int middle = (left+right)/2;
            if (temp < array[i]) right = middle - 1;
            else left = middle + 1;
        }
        for (int k=i-1;k>=left;k--) array[k+1] = array[k];
        array[left] = temp;
    }
}

/*希尔排序(SHELL SORT),又称缩小增量排序(diminishing-increment sort)
基本思想:设待排序元素序列有N个元素,首先取出一个整数gap<n作为间隔,将全部元素分为gap
个字序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.
然后缩小间隔gap,直到gap等于 1
*/

void ShellSort(int (&array)[MAXSIZE],const int left,const int right)
{
    int gap = right-left+1;     //增量的初始值
    do
    {
        gap = gap/3 + 1;   // 求下一增量
        for (int i=(left+gap);i<=right;i++)  //各子充列交错处理
            if (array[i] < array[i-gap])    //逆序
            {
                int temp = array[i], j = i-gap;
                do
                {
                    array[j+gap] = array[j];     //后移元素
                    j = j-gap;                   //现比较前一元素
                }while (j>left &&temp < array[j]);
            }
    }while (gap > 1);
}

/*快速排序
快速排序采用分治法(divide-and-conquer)进行排序.
基本思想:任取待排序元素序列中某个元素作基准,按照该元素排序码大小,将整个元素序列划分为左右两个
子序列,左侧都比基准元素小,右侧则大于或等于.然后分别对这两个子序列重复施行上述方法,直到所有的元素
都排在相应位置为止
*/

//快速排序的划分
int Partition(const int left,const int right)
{
    int pivotpos = left,pivot = array[left];    //基准元素
    for (int i=left+1;i<=right;i++)
        if (array[i] <pivot)
        {
            pivotpos++;
            if (pivotpos != i) Swap(array[pivotpos],array[i]);
        }
    array[left] = array[pivotpos];
    array[pivotpos] = pivot;
    return pivotpos;
}
//快速排序
void QuickSort(int(&array)[MAXSIZE],const int left,const int right)
{
    if (right-left <= 25) InsertSort(array,0,MAXSIZE-1); //数据规模较小时,采用直接插入.
    else
    {
        int pivotpos = Partition(left,right);
        QuickSort(array,left,pivotpos-1);
        QuickSort(array,pivotpos+1,right);
    }
}

//三路划分的快速排序算法
void Quick_Sort(int (&array)[MAXSIZE],int low,int high)
{
    int pivot=array[low];
    if (low >= high) return;
    while (low<high)
    {
        while (low<high && pivot<array[high]) high--;
        if (low<high)
        {
            array[low]=array[high];
            low++;
        }
        while (low<high && pivot>=array[low]) low++;
        if (low<high)
        {
            array[high]=array[low];
            high++;
        }
    }
    array[low]=pivot;
    Quick_Sort(array,low,low-1);
    Quick_Sort(array,low+1,high);
}

/*
选择排序
基本思想:每一趟(纺织品如第 I 趟,I = 0,1,2,...N-2)在后面 N-I个待排序元素中选出排序码
最小的元素,作为有序元素序列的第 I 个元素.待到第 N-2趟作完,待排序元素只剩下 1 个,就不用再选了.
*/
//直接选择排序
void SelectSort(int (&array)[MAXSIZE],const int left,const int right)
{
    for (int i=left;i<right;i++)
    {
        int k = i;
        for (int j=i+1;j<=right;j++)
            if (array[j] < array[k]) k = j;    //当前最小排序码的元素
        if (k != i) Swap(array[i],array[k]);
    }
}
/*
堆排序
(1):根据初始输入数据,得用堆的调整算法SiftDown()形成堆
(2):通过一系列的元素交换和重新调整堆进行排序
*/
//堆调整
void MaxHeap_SiftDown(int (&heap)[MAXSIZE],const int start,const int end)
{
    int i=start,temp = heap[start], j = 2*start + 1;
    while (j <= end)   //检查是否到最后位置
    {
        if (j < end && heap[j] < heap[j+1]) j++;
        if (temp >= heap[j]) break;
        else          //子女中大者上移
        {
            heap[i] = heap[j];
            i = j;     //i下降到子女位置
            j = 2*j + 1;
        }
    }
    heap[i] = temp;    //将temp中元素放到适合位置
}
//堆排序
void HeapSort(int (&heap)[MAXSIZE],const int size)
{
    for (int i=(size-2)/2;i>=0;i--)
        MaxHeap_SiftDown(heap,i,size-i);
    for (int j=size-1;j>=0;j--)
    {
        Swap(heap[0],heap[j]);
        MaxHeap_SiftDown(heap,0,j-1);
    }
}

//输出排序后的数列
void display(int (&array)[MAXSIZE],int size)
{
    for (int i=0;i<size;i++)
    {
        std::cout<<array[i]<<"  ";
        if ((i+1)%10 == 0) std::cout<<std::endl;
    }
}
int main(void)
{
    srand(unsigned(time(NULL)));
    for (int i=0;i<MAXSIZE;i++)
        array[i] = rand()%10000;

    std::cout<<"***直接插入排序***"<<std::endl;
    InsertSort(array,0,MAXSIZE-1);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***折半插入排序(二分法插入排序)***"<<std::endl;
    BinaryInsertSort(array,0,MAXSIZE-1);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***希尔排序(SHELL SORT)***"<<std::endl;
    ShellSort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***快速排序***"<<std::endl;
    QuickSort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***三路划分的快速排序***"<<std::endl;
    Quick_Sort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***直接选择排序***"<<std::endl;
    SelectSort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***堆排序***"<<std::endl;
    HeapSort(array,MAXSIZE);
    display(array,MAXSIZE);
    return 0;
}