class Solution {

public:

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

直接插入排序

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

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

void insertsort(vector<int>& 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<int>& 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<int>& 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<int>& 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<int>& 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<int>& 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<int>& 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<int>& nums, int left, int mid, int right)

{

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

    int l = left, r = mid + ;

    vector<int> 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<int>& 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;

    }

};