冒泡排序是将前一个元素与后一个元素进行比较，符合条件就进行交换，最大的元素需要与后面的每一个元素进行交换；

最后的数一定是最大的，因此第二层for语句是for (int j = 1; j < n - i; j++)，最后一个元素不进入循环。

void BubbleSort(int* a, int n)//a是数组名  n为数组内元素个数
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
        //将最大的元素往后挪，直到最后
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				exchange++;
			}
		}
		if (exchange == 0)//判断是否有交换，如果没有交换，说明排序已经成功，即使后面还有数据，
                          //但后面的数据已经是有序的
		{
			break;
		}
	}
}

void TEXTBubbleSort()
{
	int a[] = { 6,9,8,4,2,1,3,7,5 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

2、插入排序

          保存插入的元素，如果前面的元素大于插入元素，则将前面元素后移一位，用循环语句，将前面有序数组中所有大于插入元素的元素都后移一位，这样在前面就会有个位置空余出来，然后再a[end + 1] = tmp将插入元素放入空位。

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1;i++)
	{
		int end = i;
		int tmp = a[i + 1];//保存插入的元素
		while(end >= 0)
		{ 
			// 单趟排序：[0, end]有序 end+1位置的值，插入进入，保持他依旧有序
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//将前面大的元素往后放
				end--;
			}
			else
			{
				break;
			}
		}
			a[end + 1] = tmp;
	}
}
void TextInsertSort()
{
	int a[] = { 6,9,8,4,2,1,3,7,5 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

3、hoare排序（希尔排序）

    思路：如果使数组最左侧元素为key，则右侧先动，right- - 寻找比key小的数，找到后停止，随后left++，寻找比key大的数，找到后，a[right]与a[left]的元素交换，直到left与right相遇，再将a[key]与此时a[left]交换。

    这只是确定了如图中6的正确位置，后面使用递归发，将数组分成两个数组，6之前和6之后；

int PartSort1(int* a, int left, int right)
{
	int key = left;
	while (left < right)
	{
		while (left=a[key])//右侧寻找比key小的数
		{
			right--;
		}
		while (left= end) {
		return;
	}
	int keyi = PartSort1(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

4、选择排序      选择排序思路：假设最左边的元素为最小元素，下标为min，然后用left++寻找比它还要小的元素，找到就将这个元素的下标赋予min，遍历整个数组后，将min下标元素与left交换，这样，最小的元素就转移到最左侧。

void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int min = left;
		for (int i = left + 1; i <= right; i++)//从左往右寻找最小的数
		{
			if (a[i] < a[min])
			{
				min = i;//一旦找到，就将元素下标赋予min
			}
		}
		Swap(&a[left], &a[min]);//将min下标既最小的数与最左边的元素交换
		left++;
	}
}
void TextSelectSort()
{
	int a[] = { 6,9,8,4,2,1,3,7,5 };
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

5、前后指针     前后指针思路：设最左元素下标left为key和pre，cur为left+1,随后cur++,遇到比key小的元素，pre++，并交换cur与pre下标所在元素，直到cur走出数组范围，pre停止，并交换pre和key下标所在元素。

int PartSort2(int* a, int* left , int* right)
{
	int pre = left;
	int cur = left + 1;
	int key = left;
	while (cur < right)
	{
		if (a[cur] < a[key]&&a[++pre]!=a[cur])
		{
			Swap(&a[pre], &a[cur]);
		}
		cur++;
	}
	Swap(&a[pre], &a[key]);

	return pre;
}

//递归
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end) {
		return;
	}
	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

6、挖坑法      用key保持最左侧元素，相当于将这个位置挖成一个坑，下标为pit，随后右侧right- -，寻找比key小的元素，找到后将right下标元素放入pit下标元素，并移动pit到right处（a[pit]=a[right]，pit=right）,相当于right下标元素挖坑.     然后left++，寻找比key大的元素，再将left下标元素放入pit中，将left赋予pit（a[pit]=a[left],pit=left）。知道left与right相遇，再将pit坑位放入key。

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	int keyi = left;
	int prev = left, cur = left+1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && a[++prev] != a[cur])
			Swap(&a[prev], &a[cur]);

		++cur;
	}
	Swap(&a[prev], &a[keyi]);

	return prev;
}

void QuickSort1(int* a, int begin, int end)
{
	// 子区间相等只有一个值或者不存在那么就是递归结束的子问题
	if (begin >= end)
		return;

	int keyi = PartSort3(a, begin, end);
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi+1, end);
}