class Solution {
public:

/********************************************************************
直接插入排序
数组前面维持一个有序区，每次从后面的无序区里选一个数插入到前面的有序区，直至全部已排序
*********************************************************************/
void insertsort(vector& nums)
{
for (int i = ; i < nums.size(); i++) { //找到插入位置 int insertpos = , insertval = nums[i]; while (nums[insertpos] <= nums[i] && insertpos insertpos; j--)
nums[j] = nums[j - ];
nums[insertpos] = insertval;//插入
}
}
/*********************************************************************
//希尔排序，直插排序的变形，执行以下循环:
//if(gap<=0)break, else gap=nums.size()/2 //按下标相隔gap进行分组， 对每一组进行直插排序。 *********************************************************************/ void shellsort(vector& nums)
{
int gap=nums.size()/;
while(gap>=)
{
//对于第0,1,..gap-1组进行直插排序
for(int i=;iinsertpos;k--)nums[k]=nums[k-];
nums[insertpos]=insertval;
}
}
gap/=;
}
}
/*********************************************************************
//直接选择排序，后端维护一个有序序列，每次从未排序序列中找出一个最大值，
//与无序序列的最后一个元素交换位置
*********************************************************************/
void choosesort(vector& nums)
{
for(int i=;imaxval)maxpos=j,maxval=nums[j];
int temp=nums[nums.size()--i];
nums[nums.size()-i-]=maxval;nums[maxpos]=temp;
}
}
/*********************************************************************
//堆排序，选择排序的变种，利用一个大顶堆(升序排序)，保证根节点为最大元素，
//这样一直与末尾交换并删除，最终完成排序
//重点是大顶堆的维护 buildheap()
*********************************************************************/
//对于前n个元素，使其构成一个大顶堆
void buildheap(vector& nums,int n)
{
//从叶子往前找，若是叶子小于根，进行互换,序号为i的叶子其根序号为(i-1)/2
for(int i=n-;i>;i--)
{
if(nums[i]>nums[(i-)/])
{
int temp=nums[i];
nums[i]=nums[(i-)/];nums[(i-)/]=temp;
}
}
}

void heapsort(vector& nums)
{
for(int i=;i<nums.size();i++)
{
buildheap(nums,nums.size()-i);//维护大顶堆
int temp=nums[];//交换首尾元素
nums[]=nums[nums.size()-i-];nums[nums.size()-i-]=temp;
}
}

/*********************************************************************
冒泡排序
两两交换…
*********************************************************************/
void bubblesort(vector& nums)
{
for(int i=;i& nums,int left,int right)
{
if(left>=right)return;
int l=left,r=right;
int base=nums[l];
while(l=base && l<r)r--;
nums[l]=nums[r];
while(nums[l]<=base && l<r)l++;
nums[r]=nums[l];
}
nums[l]=base;
quicksort(nums,left,l);
quicksort(nums,l+,right);
}

/*********************************************************************
归并排序，
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
*********************************************************************/
void merge(vector& nums, int left, int mid, int right)
{
//对两个有序序列作归并处理
int l = left, r = mid + ;
vector arr;//归并后的序列，等下更新到nums中
while (l <= mid && r <= right)
{
if (nums[l] <= nums[r])
{
arr.push_back(nums[l++]);
}
else
{
arr.push_back(nums[r++]);
}
}
while (l <= mid)arr.push_back(nums[l++]);
while (r <= right)arr.push_back(nums[r++]);
//arr更新到nums中
for (int i = ; i < arr.size(); i++)
nums[left + i] = arr[i];
}

void mergesort(vector& nums, int left, int right)
{
if (right <= left)return;
int mid = (right + left) / ;
//对分组的两个序列进行归并排序
mergesort(nums, left, mid);
mergesort(nums, mid + , right);
//重点是归并步骤，把两个有序子序列合并成一个有序序列
merge(nums, left, mid, right);
}

vector<int> sortArray(vector<int>& nums) {

    quicksort(nums,,nums.size()-);

    return nums;  
}  

};

class Solution {

public:

/********************************************************************

直接插入排序

数组前面维持一个有序区，每次从后面的无序区里选一个数插入到前面的有序区，直至全部已排序

*********************************************************************/

void insertsort(vector& nums)

{

    for (int i = ; i < nums.size(); i++)

    {

        //找到插入位置

        int insertpos = , insertval = nums[i];

        while (nums[insertpos] <= nums[i] && insertpos<i)insertpos++;

        //挪动位置来插入

        for (int j = i; j > insertpos; j--)

            nums[j] = nums[j - ];

        nums[insertpos] = insertval;//插入

    }

}

/*********************************************************************

//希尔排序，直插排序的变形，执行以下循环:

//if(gap<=0)break, else gap=nums.size()/2

//按下标相隔gap进行分组， 对每一组进行直插排序。

*********************************************************************/

void shellsort(vector& nums)

{

    int gap=nums.size()/;

    while(gap>=)

    {

        //对于第0,1,..gap-1组进行直插排序 

        for(int i=;i<gap;i++)

        {

            //对 [j,j+gap,j+2gap,…]进行只直插排序

            for(int j=i;j<nums.size();j+=gap)

            {

                int insertpos=i,insertval=nums[j];

                while(nums[insertpos]<=nums[j] && insertpos<j)insertpos++;

                for(int k=j;k>insertpos;k--)nums[k]=nums[k-];

                nums[insertpos]=insertval;

            }

        }

        gap/=;

    }

}

/*********************************************************************

//直接选择排序，后端维护一个有序序列，每次从未排序序列中找出一个最大值，

//与无序序列的最后一个元素交换位置

*********************************************************************/

void choosesort(vector& nums)

{

    for(int i=;i<nums.size();i++)

    {

        int maxpos=,maxval=nums[];//找出[0,nums.size()-i-1]中的最大值

        for(int j=;j<nums.size()-i;j++)

            if(nums[j]>maxval)maxpos=j,maxval=nums[j];

        int temp=nums[nums.size()--i];

        nums[nums.size()-i-]=maxval;nums[maxpos]=temp;

    }

}

/*********************************************************************

//堆排序，选择排序的变种，利用一个大顶堆(升序排序)，保证根节点为最大元素，

//这样一直与末尾交换并删除，最终完成排序

//重点是大顶堆的维护 buildheap()

*********************************************************************/

//对于前n个元素，使其构成一个大顶堆

void buildheap(vector& nums,int n)

{

    //从叶子往前找，若是叶子小于根，进行互换,序号为i的叶子其根序号为(i-1)/2

    for(int i=n-;i>;i--)

    {

        if(nums[i]>nums[(i-)/])

        {

            int temp=nums[i];

            nums[i]=nums[(i-)/];nums[(i-)/]=temp;

        }

    }

}

void heapsort(vector& nums)

{

    for(int i=;i<nums.size();i++)

    {

        buildheap(nums,nums.size()-i);//维护大顶堆

        int temp=nums[];//交换首尾元素

        nums[]=nums[nums.size()-i-];nums[nums.size()-i-]=temp;

    }

}

/*********************************************************************

冒泡排序

两两交换…

*********************************************************************/

void bubblesort(vector& nums)

{

    for(int i=;i<nums.size();i++)

        for(int j=i;j<nums.size();j++)

        {

            if(nums[j]<nums[i])

            {

                int temp=nums[i];

                nums[i]=nums[j];nums[j]=temp;

            }

        }

}

/*********************************************************************

快速排序，选取一个基准，一趟排序后，把大于基准的元素放在右边，

小于它的元素放在左边，一直下去直到排序完成。

*********************************************************************/

void quicksort(vector& nums,int left,int right)

{

    if(left>=right)return;

    int l=left,r=right;

    int base=nums[l];

    while(l<r)

    {

        while(nums[r]>=base && l<r)r--;

        nums[l]=nums[r];

        while(nums[l]<=base && l<r)l++;

        nums[r]=nums[l];

    }

    nums[l]=base;

    quicksort(nums,left,l);

    quicksort(nums,l+,right);

}

/*********************************************************************

归并排序，

将已有序的子序列合并，得到完全有序的序列；

即先使每个子序列有序，再使子序列段间有序。

*********************************************************************/

void merge(vector& nums, int left, int mid, int right)

{

    //对两个有序序列作归并处理

    int l = left, r = mid + ;

    vector arr;//归并后的序列，等下更新到nums中

    while (l <= mid && r <= right)

    {

        if (nums[l] <= nums[r])

        {

            arr.push_back(nums[l++]);

        }

        else

        {

            arr.push_back(nums[r++]);

        }

    }

    while (l <= mid)arr.push_back(nums[l++]);

    while (r <= right)arr.push_back(nums[r++]);

    //arr更新到nums中

    for (int i = ; i < arr.size(); i++)

        nums[left + i] = arr[i];

}

void mergesort(vector& nums, int left, int right)

{

    if (right <= left)return;

    int mid = (right + left) / ;

    //对分组的两个序列进行归并排序

    mergesort(nums, left, mid);

    mergesort(nums, mid + , right);

    //重点是归并步骤，把两个有序子序列合并成一个有序序列

    merge(nums, left, mid, right);

}

    vector sortArray(vector& nums) {

        quicksort(nums,,nums.size()-);

        return nums;

    }

};