如果存在tmp>a[end],或者插入的元素是0，都只需将tmp赋给a[end+1]即可

? 2.0 再由单趟推广到多趟，也就是需要确定每次单趟排序时end与tmp的位置

希尔排序

间隔为gap分为一组，对一组进行插入排序，我们先假设gap是3，分成gap组

?排蓝色这组的代码，其实和直接插入完全一样，仅仅是两个数之间的间距由1变成了gap

?接下来我们需要解决的问题就是，实现排红色组和绿色组，也就是让end分别从0,1,2开始我们用下面这种方式解决

?仅仅是将i+=gap改为i++这样就实现了同时可以排序红绿蓝三组（gap为3）

最后一个问题，gap的取值问题，上述代码我们是取gap=3为例，但在实际排序中，给gap一个定值肯定是不行的，数组可能很大也可能很小

?选择排序

第一种选择排序?

?改进方法，如果max的下标与left的下标相同时，只需要在第一次交换之后，将最小值min的下标赋给最大值max的下标后即可。

堆排序

?同理排降序就应该建小堆，原因及思路和上面完全一致。

void HeapSort(int* a, int n)
{
?? ?for (int i = (n - 1 - 1) / 2;i >= 0;i--)
?? ?{
?? ??? ?AdjustDown(a, n, i);
?? ?}
?? ?int end = n - 1;
?? ?while (end > 0)
?? ?{
?? ??? ?Swap(&a[0],&a[end]);
?? ??? ?AdjustDown(a, end, 0);
?? ??? ?end--;
?? ?}
}
?

冒泡排序

1.0 单趟排? 思想，如果前一个数大于后一个数就交换，最终实现将最大的数据放在数组末尾

?2.0 多趟排基本思想：已经在末尾数据就不用再去管，控制单趟排序的长度即可，也就是图中绿色框之前的部分

第一种方法：

?第二种方法：

?对一组有序的数而言，它是不进行交换的，因此我们设置一个exchange进行检查，如果没发生交换就证明它是有序的的，直接跳出结束程序。

快速排序：

? ? ?快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快排的根本思想还是分治

1.0? 排单趟区间

2.0? 像二叉树一样递归排序它的左右子树

思路图：

将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare 版本

2. 挖坑法

3. 前后指针版本

PS：以下代码博主写了有返回值和无返回值的，两者没任何区别，有返回值只是为了便于复用。

hoare法（左右指针法）

快排首先进行单趟排序

? ?选出一个数字Key，一般是最左边的，或者是最右边的，Key放到它的正确的位置上去，左边的要比Key小，右边的要比Key大

? 选择左边的值作为Key，right先走，right找比key小的值，left找比key大的值，找到之后进行交换，直到他俩相遇，最后再把key与左右相遇地方的值交换

最终key所在的位置就是，他在最后排好序的的一堆数里面的位置，如下图，6最终的位置就是他在最后有序数字中的位置，位于第六个

思路图：

为什么左边做key，要让右边先走？

相遇存在两种情况：左遇到右与右遇到左

如果左边做key，左边先走，最终结果如图

?达不到我们的预期（key的左边都比它小，右边都比它大）

而让右边先走，无论是左遇右，还是右遇左，都可以保证最后结束的位置的值比key的值要小

?左右指针法的代码

void PartSort1(int* a, int n)
{
	int left = 0, right = n - 1;
	int keyi = left;
	while (left < right)
	{
		while (a[right] >= a[keyi])
		{
			right--;
		}
		while (a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[right]);

}

但是以上代码存在一个问题：对这样的一种情况

?这部分代码就会一直进行，造成越界的情况；

?同时,他们之间的等于号也是必不可少的

如果去掉等于号，对这样的情况就会造成死循环

?一直交换左右两边的5.

最终左右指针法的完整代码如下：（无返回值的）

void PartSort1(int* a, int n)
{
	int left = 0, right = n - 1;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[right]);

}

有返回值的

int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

单个区间的排序已经完成，之后再进行左右区间的递归，也就是整个快排的过程

?将数组分为? [begin,meeti-1]? meeti? [meeti+1,end] 三部分，递归这两个区间，meet就是每次左右相遇的位置，当这个区间一个值也没有或者只有一个值就结束，

完整的快排代码如下：(如果仅是写一个快排这样写即可)

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int keyi = left;
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	int meeti = left;  //或者 int meeti = right; 都是可以的
	Swap(&a[keyi], &a[meeti]);
	
	// [begin,meeti-1] meeti [meeti+1,end]
	QuickSort(a, begin, meeti - 1);
	QuickSort(a, meeti + 1, end);

}

挖坑法：

时间复杂度O(N)

基本思路

先找一个最左边或者最右边的值存起来，

1.0? 我们在这里选择最左边的值作为key将它保存起来，这样他就形成了一个坑，

2.0? 从右边开始找比key小的值，找到之后把它放到刚开始的这个坑里去，这个地方就形成一个新的坑

3.0 再从左边开始找比key大的值，找到之后再把它放到新的坑里去，循环2,3步直到左与右相遇

4.0 最后左右相遇停止时，把key放到最终结束的坑中去。

PS：如果开始找的是最右边的值，就要从左边开始，也就是2 ，3步换下顺序

思路图如下：

代码如下：

int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		//找到后放到左边的坑中去，右边形成新的坑
		a[left] = a[right];

		//找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		//找到后放到右边的坑中去，左边形成新的坑
		a[right] = a[left];
	}

	//将刚开始保存的数字放到左右相遇的地方的坑中去
	a[left] = key;

	return left;
}

左右指针法：

思路：这里我们选取最左边的当做key，设置cur与prev，开始一前一后，cur去找比key小的值，找到以后++prev，同时交换prev与cur，直到数组尾

思路图：

代码如下：

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

在学习上述三种方法后快排进而可以写成这样：单趟排想用那种方法，就用哪种方法

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a,begin,end); //想用其他单趟排的方法改下这即可

    
    // [begin,keyi-1] keyi [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
	
}

快排的时间复杂度O(NlogN)

理想的快排情况，每次单趟排都是二分，选的key每次都是这组数据的中位数，时间复杂度就是O(NlogN)

?分析一下对快排影响最大的是选的key，如果key越接近中位数，就越接近二分，效率就越高

三数取中法

?使用方法：我们在Pastsort中任然是取最左面的一个，只需要在每个Pastsort中加入以下这段代码即可。

小区间优化：

插入排序的传值：

因为插排形参传的是数组与个数，所以我们将快排的区间转化成数组与个数。

经过优化的快排如下：

快排的非递归写法

首先我们要明白栈是后进先出的，快排的递归，递归的是一段区间

? ? ?递归的顺序可以类比为二叉树的前序遍历也就是根左右，我们用栈模拟这个递归的过程，我们先让09入栈对[0 9]区间找key，再入69， 04 因为后进先出，再入34， 01，最后入89， 6，这样就完美模拟了整个递归的过程，如果我们想要递归的顺序是根右左，就先让09 入栈，再入04,69，再入01 34，再入6，89即可，反一下。?

归并排序

归并的思路：

归并排序的非递归写法：

但是这段代码只针对的如上数组，数组只有8个数据，因此我们由特殊推广到一般，对一般的数组会存在以下几种问题

内排序与外排序

两个文件归并只要求两个都有序就行，所以这里的归并有两种方法：

计数排序?