#include<iostream>
using namespace std;

//快速排序
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定
void QuickSort(int arr[], int l, int r)
{
	if (l < r)
	{
		int temp = arr[l];
		int i, j, k;
		i = l, j = r;

		while (i < j)
		{
			while (i < j&&temp <= arr[j])//先找到右边第一个比temp小的元素，然后将它向左移动
				j--;
			arr[i++] = arr[j];
			while (i < j&&temp >= arr[i])//找到左边第一个比temp大的元素，然后将它向右移
				i++;
			arr[j--] = arr[i];
		}
		arr[i] = temp;//中间（指左边的数小于temp，右边的数大于temp）这个空用temp补上
		//递归调用
		QuickSort(arr, l, i-1);
		QuickSort(arr, j+1, r);
	}
}

//插入排序
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void InsertSort(int arr[], int n)
{
	int i, j;
	
	for (i = 1; i < n; i++)
	{
		int temp = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > temp)
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j+1] = temp;
	}
}

//冒泡排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void BubbleSort(int arr[], int n)
{
	int i, j, temp;
	for(i=0;i<n-1;i++)
		for(j=0;j<n-1-i;j++)//每次最大元素往后移动，则比较次数n-1-i
			if (arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}

}

//选择排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void SelectSort(int arr[], int n)
{
	int i, j,temp;
	for (i = 0; i < n - 1; i++)         // i为已排序序列的末尾
	{
		int min = i;
		for (j = i + 1; j < n; j++)     // 未排序序列,相当于每次从未排序的部分选出最小的添加到排过序的末尾
		{
			if (arr[j] < arr[min])              // 找出未排序序列中的最小值
			{
				min = j;
			}
		}
		if (min != i)
		{
			temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}
}

//希尔排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void ShellSort(int arr[], int n)
{
	int h = 0;
	while (h <= n)                          // 生成初始增量
	{
		h = 3 * h + 1;
	}
	while (h >= 1)
	{
		for (int i = h; i < n; i++)
		{
			int j = i - h;
			int get = arr[i];
			while (j >= 0 && arr[j] > get)
			{
				arr[j + h] = arr[j];
				j = j - h;
			}
			arr[j + h] = get;
		}
		h = (h - 1) / 3;                    // 递减增量
	}
}


// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
void Merge(int arr[], int left, int mid, int right)// 合并两个已排好序的数组arr[left...mid]和arr[mid+1...right]
{
	int len = right - left + 1;
	int *temp = new int[len];       // 辅助空间O(n)
	int index = 0;
	int i = left;                   // 前一数组的起始元素
	int j = mid + 1;                // 后一数组的起始元素
	while (i <= mid && j <= right)
	{
		temp[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];  // 带等号保证归并排序的稳定性
	}
	while (i <= mid)
	{
		temp[index++] = arr[i++];
	}
	while (j <= right)
	{
		temp[index++] = arr[j++];
	}
	for (int k = 0; k < len; k++)
	{
		arr[left++] = temp[k];
	}
}

void MergeSortRecursion(int arr[], int left, int right)    // 递归实现的归并排序(自顶向下)
{
	if (left == right)    // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
		return;
	int mid = (left + right) / 2;
	MergeSortRecursion(arr, left, mid);
	MergeSortRecursion(arr, mid + 1, right);
	Merge(arr, left, mid, right);
}

void MergeSortIteration(int arr[], int len)    // 非递归(迭代)实现的归并排序(自底向上)
{
	int left, mid, right;// 子数组索引,前一个为arr[left...mid]，后一个子数组为arr[mid+1...right]
	for (int i = 1; i < len; i *= 2)        // 子数组的大小i初始为1，每轮翻倍
	{
		left = 0;
		while (left + i < len)              // 后一个子数组存在(需要归并)
		{
			mid = left + i - 1;
			right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够
			Merge(arr, left, mid, right);
			left = right + 1;               // 前一个子数组索引向后移动
		}
	}
}

//堆排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定


void Swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

void Heapify(int arr[], int i, int size)  // 从arr[i]向下进行堆调整
{
	int left_child = 2 * i + 1;         // 左孩子索引
	int right_child = 2 * i + 2;        // 右孩子索引
	int max = i;                        // 选出当前结点与其左右孩子三者之中的最大值
	if (left_child < size && arr[left_child] > arr[max])
		max = left_child;
	if (right_child < size && arr[right_child] > arr[max])
		max = right_child;
	if (max != i)
	{
		Swap(arr, i, max);                // 把当前结点和它的最大(直接)子节点进行交换
		Heapify(arr, max, size);          // 递归调用，继续从当前结点向下进行堆调整
	}
}

int BuildHeap(int arr[], int n)           // 建堆，时间复杂度O(n)
{
	int heap_size = n;
	for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每一个非叶结点开始向下进行堆调整
		Heapify(arr, i, heap_size);
	return heap_size;
}

void HeapSort(int arr[], int n)
{
	int heap_size = BuildHeap(arr, n);    // 建立一个最大堆
	while (heap_size > 1)   
	{	// 堆（无序区）元素个数大于1，未完成排序
		// 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
		// 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法
		Swap(arr, 0, --heap_size);
		Heapify(arr, 0, heap_size);     // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
	}
}



void main()
{
	int a[5] = { 16,13,55,1,67 }; 
	//QuickSort(a, 0, size(a) - 1);//减一的原因是要定位到最后一个元素
	//InsertSort(a, size(a));
	//BubbleSort(a, size(a));
	//SelectSort(a, size(a));
	//ShellSort(a, size(a));
	//MergeSortIteration(a, size(a));
	//HeapSort(a, size(a));
	for (int i = 0; i < size(a); i++)
		cout << a[i]<<"  ";
	system("pause");
}