[数据结构与算法]数据结构 排序

插入排序思想：
将带排列的元素插入到已经排列好的有序序列中
***直接插入排序：***即在待排序的队列中，从第一个元素开始插入，与相邻元素进行大小比较，若后一位元素小于则往右移，若大于则于插入元素及之前的元素比较多大小进行左移，例如：

希尔排序思想：
选定一个整数，作为将所有待排序元素每次（递减）分组组内元素之间的增长量，并在每个小组内进行排序，每次堆增长量进行缩小（例如/2）当这个整数递减到1的时候即排序结束,例如：

选择排序思想：
每次从待排序的元素中找出最大或者最小的 值进行排序。
堆排序思想：
在堆这一数据结构之下实现的排序算法，升序建大堆，降序建小堆。
冒泡排序思想：
重复的走过要排序的数列，比较两个相邻的数值大小，带着较大值继续与下一个比较，一直到没有进行比较的需要。
快速排序思想：
在待排序的数列中任选一个元素作为队列中心将排序队列分割为两半，左边的数值都小于该元素，右边的数值均大于该元素，左右序列重复此过程，直到排序完成。
将区间分为两半的常见方式有1、hoare版本，2、挖坑法、3、前后指针法
归并排序思想：
采用分治法，将未排序的序列拆分排序之后再进行归并，形成最终的有序队列

1、冒泡排序

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int *a, int n)
{
	assert(a);
	int end = n;
	while (end > 0)
	{
		int flag = 0;
		for (int i = 1; i < end; ++i)
		{
			if (a[i - 1]>a[i])
			{
				swap(&a[i - 1], &a[i]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
		--end;
	}
}

2、快速排序的递归实现

int GetMidIndex(int a, int begin, int end)
{
	int mid = begin + ((end - begin) >> 1);

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}_
		else if (a[begin]>a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}
//

int partSort1(int *a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midindex]);
	int key = a[begin];
	int start = begin;
	while (begin < end)
	{
		while (begin < end)
		{
			while (begin < end&&a[end] >= key)
				--end;
			while (begin < end&&a[begin] <= key)
				++begin;
			swap(&a[begin], &a[end]);
		}
			swap(&a[begin],&a[start]);
			return begin;
}

3、快速排序挖坑法

int PartSort2(int*a, int begin, int end)
	{
		int key = a[begin];
		while (begin < end)
		{
			while (begin<end&&a[end]>key)
				--end;
			a[begin] = a[end];
			while (begin < end&&a[begin] <= key)
				++begin;
			a[end] = a[begin];
		}
		a[begin] = key;
		return begin;
	}

4、快速排序前后指针法

int PartSort3(int a, int begin, int end)
	{
		int midindex = GetMidIndex(a, begin, end);
		Swap(&a[begin], &a[[midindex]);
		int key = a[begin];
		int prev = begin;
		int cur = begin + 1;
		while (cur < end)
		{
			if (a[cur] < key&&++prev != cur)
				swap(&a[cur], &a[prev]);
			++cur;
		}
		swap(&a[begin], &a[prev]);
		return prev;
	}

	void QuickSort(int a, int left, int right)
	{
		if (left >= right)
			return;
		if (right - left + 1 < 10)
		{
			InsertSort(a+left,right-left+1)；
		}
		else
		{
			int div = PartSort3(a, left, right);
			QuickSort(a, left, div - 1);
			QuickSort(a, div + 1, right);
		}

5、用栈实现非递归快速排序

	void QuickSortR(int*a, int left, int right)
		{
			Stack st;
			StackInint(&st, 10);
			if (left < right)
			{
				StackPush(&st, right);
				StackPush(&st, left);
			}
			while (StackEmpty(&st) != 0)
			{
				left = StackTop(&st);
				StackPop(&st);
				right = StackTop(&st);
				StackPop(&st);
				int div = PartSort1(a, left, right);
				if (left < div - 1)
				{
					StackPush(&st, div - 1);
					StackPush(&st, left);
					if (div + 1 < right)
					{
						StackPush(&st, &right);
						StackPush(&st, &div + 1);
					}
				}
			}
		}