/*
* 如果待排序的表中，存在多个关键字相同的元素，经过排序后
* 这些具有相同关键字的元素之间的相对次序保持不变，则称这种
* 排序方法是稳定的。反之，如果具有相同关键字的元素之间的相
* 对次序发生变化，则称这种排序方法是不稳定的。
*/

/*
* 1.插入排序：假设待排序的元素存放在R[0, n-1]中，怕徐过程中的某一时刻，R
* 被划分为两个子区间R[0,i-1]和R[i,n-1]（刚开始i = 1，有序区只有R[0]一个元素），
* 其中，前一个子区间是已经排好序的有序区，后一个子区间是当前未排序的地方，不妨称其
* 为无序区。直接插入排序的一趟操作是将当前无序区的头元素R[i](1<=i<=n-1)插入到有序区
* R[0,i-1]中的适当的位置上，使得R[0,i]变为新的有序区。
* @R_434_1304@O(n^2),是一种稳定排序。 
*/

void InsertSort(int R[], int length)
{
	int i, j;
	int tmp;
	for (i = 1; i < length; i++)
	{
		tmp = R[i];
		j = i - 1;
		while (j >= 0 && tmp < R[j])
		{
			R[j + 1] = R[j];
			j--;
		}
		R[j + 1] = tmp;
	}
}

/*
* 2.折半插入排序：直接插入排序将无序区中开头元素R[i](1<=i<=n-1)插入到有序区R[0,i-1]
* 中，此时可以采用折半查找方法现在R[0,i-1]中找到插入的位置，再通过移动元素进行插入。
* 时间复杂度O(n^2),是一种稳定排序。
* 就平均性能而言，折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。
*/

void InsertSort(int R[], int length)
{
	int i, j, low, high, mid;
	int tmp;
	for (i = 1; i < length; i++)
	{
		tmp = R[i];
		low = 0, high = i - 1;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (tmp < R[mid])
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}

		for (j = i - 1; j >= high + 1; j--)
		{
			R[j + 1] = R[j];
		}

		R[j + 1] = tmp;
	}
}

/*
* 3.冒泡排序：通过无序区中相邻元素关键字的比较和位置的交换，使得关键字最小的元素如气泡
* 一般逐渐上浮，直到“水面”。整个算法是从最下面的元素开始，对每两个相邻的关键字进行比较，
* 且使关键字较小的元素换至关键字较大的元素之上，使得经过一趟冒泡排序后，关键字最小的元素
* 到达最上端。接着，再在剩下的元素中找关键字次小的元素，并把它换到第二个位置上。依次类推，
* 直到所有的元素有序为止。 
* 时间复杂度O(n^2), 是一种稳定排序
*/

void BubbleSort(int R[], int n)
{
	int i, j;
	int tmp;
	for (i = 0; i < n - 1; i++)
	{
		for (j = n - 1; j > i; j--)
		{
			if (R[j] < R[j - 1])
			{
				tmp = R[j];
				R[j] = R[j - 1];
				R[j - 1] = tmp;
			}
		}
	}
}

/*
* 在某一趟比较时没有出现任何元素的交换，就说明已经排好序了，就可以结束了。
*/

void BubbleSort(int R[], int n)
{
	int i, j;
	bool exchange;
	int tmp;

	for (i = 0; i < n - 1; i++)
	{
		exchange = false;
		for (j = n - 1; j > i; j--)
		{
			if (R[j] < R[j - 1])
			{
				tmp = R[j];
				R[j] = R[j - 1];
				R[j - 1] = tmp;
				exchange = true;
			}
		}

		if (!exchange)
		{
			return;
		}
	}
}

/*
* 4.快速排序：在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准，
* 把该元素放入适当的位置后，数据序列被此元素划分为两部分，所有关键字比
* 该元素关键字小的元素放置在前一部分，所有关键字比它大的元素放置在后一
* 部分，并把该元素排在这两部分的中间(称该元素归位)，这个过程称作一趟快速
* 排序，之后对所有划分出来的两部分分别重复上述过程，直至每部分内只有一个
* 元素或为空为止。简而言之，每趟将表的第一个元素放入适当位置，将表一分为二，
* 对子表按递归方式继续这种划分，直到划分的子表长为1或0。 
* 最坏的时间复杂度是O(n^2),最好的时间复杂度为O(nLOG2 n)。不稳定的排序算法。
*/

void Quicksort(int R[], int s, int t)
{
	int i = s, j = t;
	int tmp;
	if (s < t)
	{
		tmp = R[s];
		while (i != j)
		{
			while (j > i &amp;& R[j] >= tmp)
				j--;

			R[i] = R[j];

			while (j > i && R[i] <= tmp)
				i++;
			R[j] = R[i];
		}
		R[i] = tmp;

		QuickSort(R, s, i - 1);
		QuickSort(R, i + 1, t);
	}
}

/*
* 5.选择排序：第i趟排序开始时，当前有序区和无序区分别为R[0,i-1]和R[i,n-1]。该趟排序时从无序区中选出关键字
* 最小的元素R[k],将它与无序区的第一个元素交换，使R[0,i]和R[i+1,n-1]分别变为新的有序区和新的无序区。每趟
* 排序均使有序区增加一个元素，无序区减少一个元素，直到结束。
* 时间复杂度O(n^2),不稳定的排序算法。
*/

void SelectSort(int R[], int n)
{
	int i, j, k;
	int tmp;
	for (i = 0; i < n - 1; i++)
	{
		k = i;
		for (j = i + 1; j < n; j++)
		{
			if (R[j] < R[k])
			{
				k = j;
			}
		}

		if (k != i)
		{
			tmp = R[i];
			R[i] = R[k];
			R[k] = tmp;
		}
	}
}

/*
* 6. 归并排序：归并排序是多次将两个或两个以上的有序表合成一个新的有序表。最简单的归并是直接将
* 两个有序的子表合并成一个有序的表即二路归并。将R[0,n-1]看成n个长度为1的有序序列，然后进行两两
* 归并，然后再进行归并，直到得到长度为n的有序序列。
* 时间复杂度O(nlog2 n), 稳定排序算法。
* 
*/

void Merge(int R[], int low, int mid, int high)
{
	int* R1;
	int i = low, j = mid + 1, k = 0;
	R1 = new int[high - low + 1]();
	while (i <= mid && j <= high)
	{
		if (R[i] < R[j])
		{
			R1[k] = R[i];
			i++;
			k++;
		}
		else
		{
			R1[k] = R[j];
			k++;
			j++;
		}
	}

	while (i <= mid)
	{
		R1[k] = R[i];
		k++;
		i++;
	}

	while (j <= high)
	{
		R1[k] = R[j];
		j++;
		k++;
	}

	for (k = 0, i = low; i <= high; k++, i++)
	{
		R[i] = R1[k];
	}

	delete[] R1;
	R1 = nullptr;
}


//对整个表进行一趟归并
void MergePass(int R[], int length, int n)
{
	int i;

	for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length)    //归并length长的两个相邻子表
	{
		Merge(R, i, i + length - 1, i + 2 * length - 1);
	}

	if (i + length - 1 < n)                 // 余下两个子表，后者长度小于length
	{
		Merge(R,i, i + length - 1, n - 1);  //归并这两个子表
	}
}

void MergeSort(int R[], int n)  //自底而上的两路归并算法
{
	int length;
	for (length = 1; length < n; length = 2 * length)
	{
		MergePass(R, length, n);
	}
}