#include<iostream>
using namespace std;

int len = 10;
int a[10] = {5,7,2,6,4,1,3,9,8,10};

/*
 *冒泡排序,时间复杂度O(N^2)；空间复杂度：O(1)；稳定排序
 *思路：第一趟：两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置；一共进行n-1趟这样的交换将可以把所有的元素排好。
*/
void MaoPao(int a[]){
    int temp;
    int flag = 0;
    // n-1趟排序
    for(int i = 0; i < len - 1; i++){
        for(int j = 0; j < len - 1 -i; j++){
            if(a[j] > a[j + 1]){
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;
            }
        }
        // 若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序
        if(flag == 0)break;
    }
}

/*
 *插入排序，时间复杂度O(N^2)；空间复杂度O(1)；稳定排序
 *思路：假设数组除最后一个元素都有序了，那么将最后一个元素与前面的比较，如果前面的元素大则向右移动。实际过程从数组的第二个元素开始执行插入排序
*/
void ChaRu(int a[]){
    // 从第一轮就从第二个元素开始找，所以n-1轮就可以
    for(int i = 0; i < len - 1; i++){
        // 已经有序的最后一个元素
        int end = i;
        // 需要排序的元素
        int temp = a[end + 1];
        while(end >= 0){
            if(a[end] > temp){
                // 直接替换 循环外面再将被替换的值放到适当位置
                a[end + 1] = a[end];
                end--;
            }
            else{
                break;
            }
        }
        a[end + 1] = temp;
    }
}

/*
 *希尔排序，时间复杂度O(N^1.5)；空间复杂度O(1)；不稳定排序。
 *思路：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。然后将gap逐渐减小重复上述分组和排序的工作。当到达gap=1时，所有元素在统一组内排好序。
*/
void ShellSort(int a[], int n){
    int gap = n;
	while (gap > 1)
	{
		//gap /= 2;
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
}

/*
 *选择排序，时间复杂度O(N^2); 空间复杂度O(1);不稳定排序。
 *思路：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完。优化：每次最大和最小同时选.
*/
void SelectSort(int a[], int n){
    //保存数组的起始位置
    int begin = 0;
    //保存换数组的末尾位置
    int end = n - 1;
    int temp;
    while (begin < end)
	{
		int maxi = begin;//保存最大元素下标
		int mini = begin;//保存最小元素下标
        //遍历数组寻找最小和最大元素
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
        //将最小元素交换到起始位置
        temp = a[begin];
        a[begin] = a[mini];
        a[mini] = temp;

        //判断最大值的位置是否在起始位置
		if (maxi == begin)
		{
			maxi = mini;    
		}
        //将最大元素交换到末尾位置
        temp = a[end];
        a[end] = a[maxi];
        a[maxi] = temp;
        //移动数组起始和末尾位置
		begin++;
		end--;
	}
}

/*
 *堆排序，时间复杂度O(N*logN)；空间复杂度O(1)；不稳定排序。
 *思路：升序为例，构建一个堆结构，然后每个父节点均替换为子节点的最大值，然后根节点就是最大值，重复这个步骤。
*/
void HeapAdjust(int H[], int s, int length)
{
    int tmp = H[s];
    // 左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    int child = 2 * s + 1; 
    while (child < length)
    {
        if (child + 1 < length && H[child] < H[child + 1])
        { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            child++;
        }
        if (H[s] < H[child])
        {   // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child;       // 重新设置s ,即待调整的下一个结点的位置
            child = 2 * s + 1;
        }
        else
        { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
            break;
        }
        H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
    }
}
/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{
    // 最后一个有孩子的节点的位置 i=  (length -1) / 2
    for (int i = (length - 1) / 2; i >= 0; --i)
        HeapAdjust(H, i, length);
}
void HeapSort(int H[], int length)
{
    // 初始堆
    BuildingHeap(H, length);
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {
        // 交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i];
        H[i] = H[0];
        H[0] = temp;
        // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H, 0, i);
    }
}

/*
 *快速排序，时间复杂度O(N*logN)；空间复杂度O(logN)；不稳定排序。
 *思路：最右边的值为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。确定两个指针left 和right 分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换left和right指针对应位置的值。重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。
*/
int PartSort(int a[], int left, int right){
    // 选最右面为基准
    int key = right;
    while(left < right){
		//选右边为基准值，左指针先走
        while(left < right && a[left] <= a[key]){
            left++;
        }
        //右指针再走
        while(left < right && a[right] >= a[key]){
            right--;
        }
        // 交换
        int temp = a[right];
        a[right] = a[left];
        a[left] = temp;
    }
    int temp = a[key];
    a[key] = a[left];
    a[left] = temp;
    return left;
}
void QuickSort(int a[], int left, int right){
    if(left >= right)return;
    // 第一次快排
    int keyi = PartSort(a, left, right);
    // 左子序列快排
    QuickSort(a, left, keyi - 1);
    // 右子序列快排
    QuickSort(a, keyi + 1, right);
}

/*
 *归并排序，递归实现，时间复杂度O(N*logN)；空间复杂度O(N)；稳定排序。
  *思路：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
*/
void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
	if (left >= right)
	{
		return;
	}
 
    //划分数组，每次一分为二
	int mid = (left + right) / 2;
	_MergeSort(a, left, mid,tmp);//划分左区间
	_MergeSort(a, mid + 1, right,tmp);//划分右区间
 
    //合并有序序列
	int begin1 = left, end1 = mid;//有序序列1
	int begin2 = mid + 1, end2 = right;//有序序列2
	int i = left;
    //注意结束条件为一个序列为空时就停止
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
 
    //两序列不可能同时为空，将剩余元素合并
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
 
    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
	int j = 0;
	for (j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
}
void MergeSort(int* a, int n)
{
    //因为需要将两个有序序列合并，需借助额外数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1,tmp);
	free(tmp);
	tmp = NULL;
}

int main(){
    
    // MaoPao(a);
    // ChaRu(a);
    // ShellSort(a, len);
    // SelectSort(a, len);
    // HeapSort(a, len);
    // QuickSort(a, 0, len - 1);
    // MergeSort(a, len);
    cout<<"out:"<<endl;
    for(int i = 0; i < len; i++){
        cout<<a[i];
        cout<<',';
    }
}