void InsertSort(int* a, int len)
{
	int idx = 0;
	int temp = 0;
	for (int i = 1; i < len; ++i)
	{	
		temp = a[i];
		for (idx = i - 1; idx >= 0 && a[idx] > temp; --idx)
		{
			a[idx + 1] = a[idx];
		}
		a[idx + 1] = temp;
	}
}

void SelectSort(int* a, int len)
{
	for (int i = 0; i < len; ++i)
	{
		int min = i;
		for (int j = i + 1; j < len; ++j)
		{
			if (a[j] < a[min])
			{
				min = j;
			}
		}
		if (i != min)
		{
			int temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}

//快速排序 	选择一个基准数，把比这个数小的挪到左边 这个数大的移动到右边 然后不断对左右两边执行这个操作 直到数组有序
//时间复杂度：平均时间复杂度：O(nlog2n);
int Partition(int* nums, int low, int high);
void QuickSort(int* nums, int begin, int end)
{
	if (begin < end)
	{
		int key = Partition(nums, begin, end);
		if (key - 1 > 0)
		{
			QuickSort(nums, begin, key - 1);
		}
		if (key + 1 < end)
		{
			QuickSort(nums, key + 1, end);
		}
	}
}
/*
*	第一趟快速排序
*/
int Partition(int* nums, int low, int high)
{
	if (nums == nullptr || low >= high)
    {
        //input invaild
        return -1;
    }

    int guard = nums[low];
    while (low < high)
    {
        while (low < high && nums[high] >= guard)
        {
            --high;
        }
        if (low < high)
        {
            nums[low] = nums[high];
            ++low;
        }
        while (low < high && nums[low] < guard)
        {
            ++low;
        }
        if (low < high)
        {
            nums[high] = nums[low];
            --high;
        }
    }
	nums[low] = guard;
	return low;
}

//shell排序  希尔排序是将数组按照一定步长分成几个子数组进行排序，通过逐渐缩短步长来完成最终排序
//时间复杂度：O(nlogn) ~~ O(n^2);
void ShellSort(int* a, int len)
{
	for (int gap = len >> 1; gap > 0; gap >>= 1)
	{
		for (int i = gap; i < len; ++i)
		{
			int temp = a[i];
			int j = i - gap;
			for (; j >= 0 && a[j] > temp; j -= gap)
			{
				a[j + gap] = a[j];
			}
			a[j + gap] = temp;
		}
	}
}

//归并排序 将一个数组打散成小数组，然后把小数组拼凑再排序知道数组有序
void MergeArray(int* nums, int begin, int mid, int end, int* temp)
{
	int low = begin;
	int high = mid; 
	int temp_idx = begin;
	while (low != mid && high != end)
	{
		if (nums[low] < nums[high])
		{
			temp[temp_idx++] = nums[low++];
		}
		else
		{
			temp[temp_idx++] = nums[high++];
		}
	}
	while (low < mid)
	{
		temp[temp_idx++] = nums[low++];
	}
	while (high < end)
	{
		temp[temp_idx++] = nums[high++];
	}
}

void MergeSort(int* nums, int begin, int end, int* temp)
{
	int mid = (begin + end) / 2;
	if (mid != begin) 
	{
		MergeSort(nums, begin, mid, temp);
		MergeSort(nums, mid, end, temp);
		MergeArray(nums, begin, mid, end, temp);
	}
}

/*
* 调整堆
* 参数：heap[begin, end]是以heap[begin]为根的完全二叉树；
* 且分别以heap[2*begin] 和 [2*begin + 1]为根的左右子树为大根堆；
* 调整heap[begin]使其符合大根堆;
*/
void AdjustHeap(int* heap, int begin, int end)
{
	if (heap == nullptr || begin >= end)
	{
		return;
	}
	int root_value = heap[begin];
	int root = begin;
	int child = root * 2;
	bool finish = false;
	while (child <= end && !finish)
	{
		if (child < end && heap[child] < heap[child + 1])
		{
			++child;
		}
		if (root_value >= heap[child])
		{
			finish = true;
		}
		else
		{
			heap[root] = heap[child];
			root = child;
			child = root * 2;
		}
	}
	heap[root] = root_value;
}

void CreateHeap(int* heap, int length)
{
	if (heap == nullptr || length == 0)
	{
		return;
	}
	//从length / 2个记录开始进行筛选建堆
	for (int index = length / 2; index >= 0; --index)
	{
		AdjustHeap(heap, index, length - 1);
	}
}

/*
*	堆排序 时间复杂度: 平均最好最坏都是O(log2n)
*/
void SortHeap(int* heap, int length)
{
	int mid = length / 2;
	for (int index = length - 1; index >= 1; --index)
	{
		//根节点和尾节点交换
		int temp = heap[0];
		heap[0] = heap[index];
		heap[index] = temp;
		AdjustHeap(heap, 0, index - 1);
	}
}

int SequenceSearch(int arr[], int length, int value)
{
	int index = 0;
	for (int idx = 0; idx < length; ++idx)
	{
		if (arr[idx] == value)
		{
			return idx;
		}
	}
	return -1;
}

int BinarySearch(int arr[], int length, int value)
{
	int mid = 0;
	int low = 0;
	int high = length - 1;
	while (low < high)
	{
		mid = (low + high) / 2;
		if (arr[mid] == value)
		{
			return mid;
		}
		else if (arr[mid] < value)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

//迭代查找
int BinarySearchRe(int arr[], int low, int high, int value)
{
	if (low < high)
	{
		return -1;
	}

	int mid = (low + high) / 2;
	if (arr[mid] == value)
	{
		return mid;
	}
	else if (arr[mid] < value)
	{
		return BinarySearchRe(arr, mid + 1, high, value);
	}
	else
	{
		return BinarySearchRe(arr,  low,  mid - 1, value);
	}
}

/*
 * 关于二叉排序树的插入、生成、查找
 */

/*
 * 根据二叉排序树的性质，二叉排序树插入
 */
typedef BinaryTreeNode BSTree;
void InsertBST(BSTree** tree, int key)
{
    //二叉排序树插入遇到tree的value和key相等 直接退出
    BSTree* bstree = nullptr;
    if (*tree == nullptr)
    {
        bstree = new BinaryTreeNode();
        bstree->value = key;
        bstree->left = nullptr;
        bstree->right = nullptr;
        *tree = bstree;
    }
    else if ((*tree)->value < key)
    {
        InsertBST(&((*tree)->right), key);
    }
    else if ((*tree)->value > key)
    {
        InsertBST(&((*tree)->left), key);
    }
}

/*
 * 创建二叉排序树
 */
void CreateBST(int* tree, int length)
{
    BSTree* bt = nullptr;
    BSTree** bstree = &bt;
    for (int index = 0; index < length; ++index)
    {
        InsertBST(bstree, tree[index]);
    }
}

/*
 * 二叉排序树 查找 递归
 */

BSTree* SearchBSTRe(BSTree* tree, int key)
{
    if (tree == nullptr)
    {
       return nullptr;
    }
    else if (tree->value < key)
    {
        return SearchBSTRe(tree->right, key);
    }
    else
    {
        return SearchBSTRe(tree->left, key);
    }
}

/*
 * Binary Sort Tree search  not recursion
 */
BSTree* SearchBST(BSTree* tree, int key)
{
    BSTree* temp = tree;
    while (temp)
    {
        if (temp->value == key)
        {
            return temp;
        }
        else if (temp->value < key)
        {
            temp = temp->right;
        }
        else
        {
            temp = temp->left;
        }
    }
}