排序的概念?
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
在这里主要用C语言来介绍以下排序（不特别说明就以排升序为例）。
目录
?
插入排序
基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
注意：当把一个待排序数插入到待定序列前，这个序列是已经有序的。
比如说我们要把待排数字4，插入到有序数列中：
? ? ? ? ? ? ?
?我们应该从数组里面最后一个元素开始比较（从后面往后挪数据的时间开销比较小）。
1、首先比较末位置的5比4大，所以5需要往后挪一步。
? ? ? ? ??
?2、接着下一步end位置的值比4小，那么，end+1的位置就把待排序数字4插入。
? ? ? ? ? ?
但是还会存在这样的特殊情况：
?1、? 比如待插入的数据比原序列里的数字都小：
? ? ? ? ? ?
2、 当我们挪动数据会出现这样现象：end越界了
? ? ? ? ??
3、同样的，我们在end+1的位置把待排序数字0插入就行了。
? ? ? ? ?
?以上是针对单趟的插入排序，那么如何实现多趟排序来使得一组数据有序呢？
比如说我们对以下数据进行排序：
? ? ? ? ? ? ? ? ? ?
? ? ? ?我们可以先把第一个数据当做end位置的数据，记录end+1的数据作为带插入数据。第一次就针对2个数据排序，当待插入数据插入后，这两个数据就有序了，以此类推，这样就保证每次插入的数据前面的序列有序。
?InsertSort
//插入排序
void InsertSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int end=i;
int x = a[end + 1];
while (end >= 0)
{
if (a[end] > x) //排升序
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = x;
}
}//插入排序
void InsertSort(int* a, int n)
{
?? ?int i = 0;
?? ?for (i = 0; i < n - 1; i++)//如图我们可以见到，end的位置最大在n-2的位置上，这样就能保? ? ? ?证a[end+1]不越界。? ? ? ? ? ??
?? ?{
?? ??? ?int end=i;//从第一个位置开始，往后一次作为末位置
?? ??? ?int x = a[end + 1];//记录要插入的数据，此时，它前面的序列一定时有序的
?? ??? ?while (end >= 0) //end>=0,保证了x和待排序的序列中每一个元素进行比较
?? ??? ?{
?? ??? ??? ?if (a[end] > x) //当end位置的数据大于待插入数据时，end的数据需要往后挪
?? ??? ??? ?{
?? ??? ??? ??? ?a[end + 1] = a[end]; //end位置的数据往后挪到end+1位置上
?? ??? ??? ??? ?end--;//end--后，就可以保证接着比较前面的数据
?? ??? ??? ?}
?? ??? ??? ?else //当a[end]<=x时，说明x需要找了要插入的地方
?? ??? ??? ?{
?? ??? ??? ??? ?break;//跳出循环
?? ??? ??? ?}
?? ??? ?}
?? ??? ?a[end + 1] = x;//a[end+1]位置插入x，a[end]<x,所以要在end后插入x
?? ?}
}
测试结果：
插入排序特点
1. 元素集合越接近有序，直接插入排序算法的时间效率越高O(N)
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
希尔排序
希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。注意：希尔排序是针对插入排序的优化。思想是，先进行预排序，是序列不断接近有序，当gap等于1时，相当于插入排序，对于接近有序的序列插入排序效率很高。
ShellSort?
第一种写法
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
int j = 0;
for (j = 0; j < gap; j++)
{
int i = 0;
for (i = j; i < n - gap; i += gap)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)//排升序
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
}//插入排序
void ShellSort(int* a, int n)
{
?? ?int gap = n;
?? ?while (gap > 1) //接下来gap会不断缩小，直到gap为1进行排序后就有序了
?? ?{
?? ??? ?gap = gap / 3 + 1; //或者我们可以用gap=gap/2;来控制gap的变化，此过程gap一定会等? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?于1
?? ??? ?int j = 0;
?? ??? ?for (j = 0; j < gap; j++)? //一共有gap组，所以进行gap次
?? ??? ?{
?? ??? ??? ?int i = 0;
?? ??? ??? ?for (i = j; i < n - gap; i += gap) //类比于插入排序i最大的位置在n-gap-1处? ?//以gap==2为例，n-gap位置之前的任何一个数据，加gap后都不会越界，比如下面的8和6就是gap组中，分别每一组最后排序的数据。如果之后的5和7作end的话执行int x = a[end + gap];命令后，x实际上就已经越界了。
? ? ? ? ? ??
?? ??? ??? ?{
?? ??? ??? ??? ?int end = i;
?? ??? ??? ??? ?int x = a[end + gap];? ?//各自组进行各自的比较? ? ? ? ? ? ? ? //对已经分的gap组，针对对应的组进行排序
?? ??? ??? ??? ?while (end >= 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if (a[end] > x)//排升序
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?a[end + gap] = a[end];?
?? ??? ??? ??? ??? ??? ?end -= gap;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else? //当a[end]<=x时，说明x需要找了要插入的地方
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?a[end + gap] = x; //a[end+gap]位置插入x，a[end]<x,所以要在end后插入x
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
第二种写法
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1) //多组控制
{
gap = gap / 3 + 1;
int i = 0;
for (i = 0; i < n - gap; i++) //每个gap排序
{
int end = i;
int x = a[end + gap];
while (end >= 0) //单趟排序
{
if (a[end] > x)//排升序
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}void ShellSort(int* a, int n)
{
?? ?int gap = n;
?? ?while (gap > 1) //多组控制，直到gap<=1时，就停止了。此时已经进行了gap=1的排序了
?? ?{
?? ??? ?gap = gap / 3 + 1;
?? ??? ?int i = 0;
?? ??? ?for (i = 0; i < n - gap; i++) //一个挨着一个排序，依次对每个组挨着进行排序，不再是一? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 个一个组分开排序。
?? ??? ?{
?? ??? ??? ?int end = i;
?? ??? ??? ?int x = a[end + gap];
?? ??? ??? ?while (end >= 0) //单趟排序
?? ??? ??? ?{
?? ??? ??? ??? ?if (a[end] > x)//排升序
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?a[end + gap] = a[end];
?? ??? ??? ??? ??? ?end -= gap;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?a[end + gap] = x;
?? ??? ?}
?? ?}
}
测试结果：
?希尔排序特点
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有? ? ? ?序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性? ? ? ? ?能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好? ? ? ? 些树中给出的希尔排序的时间复杂度都不固定。我们只需要记得结果就行了，各种情况平? ? ?均值：O(N^1.3)。
4. 稳定性：不稳定。
选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。? ? ? ? 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
比如以这种序列为例：
? ? ? ? ? ? ??
?
---------------------------------------------------------------------------------------------------------------------------------
?1、我们在每一次遍历begin和end间的数据时，选出序列中最大的值，和最小的值。
? ? ? ? ? ? ? ? ? ? ?
?2、然后把选出的最小的mini值与begin位置的值进行交换，把选出的最大的maxi值与end位置的? ? ? ? ? 值进行交换。
? ? ? ? ? ? ? ? ??
?3、此时，begin和end位置的数据已经是嘴和和最小值了，已经排好完毕。然后begin++，end--。
? ? ? ? ? ? ?
?......依次类推，知道begin==end时，就排完了，此时序列也就有序了。
注意：还有一种特殊情况，在下面分析代码时会详细讲到。
---------------------------------------------------------------------------------------------------------------------------------
SelectSort
//选择排序
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
int i = 0;
for (i = begin; i <= end; i++)
{
if (a[i] < a[mini]) //拿i的下标来比，这样保证了比较一轮
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}//选择排序
void Swap(int* a, int* b)
{
?? ?int tmp = *a;
?? ?*a = *b;
?? ?*b = tmp;
}
void SelectSort(int* a, int n)
{
?? ?int begin = 0;//记录待排序序列的第一个位置
?? ?int end = n - 1;//记录待排序序列的最后一个位置
?? ?while (begin < end)//当begin==end时就结束条件，这时候也就有序了
?? ?{
?? ??? ?int mini = begin;//记录最小数据的下标在这里我们们记录下标，因为在后面要进行Swap函数调用进行交换。不能创建mini=a[begin],否则根据栈的使用性质，序列中被交换的数据给mini后可能会丢失（在新一轮的遍历中被覆盖了）。
?? ??? ?int maxi = begin;//记录最大数据的下标
?? ??? ?int i = 0;
?? ??? ?for (i = begin; i <= end; i++)//在begin和end间进行遍历
?? ??? ?{
?? ??? ??? ?if (a[i] < a[mini]) ?//拿i的下标来比，这样保证了比较一轮
?? ??? ??? ?{
?? ??? ??? ??? ?mini = i;
?? ??? ??? ?}
?? ??? ??? ?if (a[i] > a[maxi])
?? ??? ??? ?{
?? ??? ??? ??? ?maxi = i;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?Swap(&a[begin], &a[mini]);
?? ??? ?if (maxi == begin)//特殊情况的处理
?? ??? ?{
?? ??? ??? ?maxi = mini;
?? ??? ?}-------------------------------------------------------------------------------------------------------------------------
? ? //对于下面这种情况
? ? ? ? ? ?
? ? //在第一轮选出maxi和mini后
? ? ? ? ? ?
//我们首先将mini位置的值和begin位置的值进行交换后?
? ? ? ? ? ?
//接着我们就不能直接把maxi位置的值和end位置的值进行交换了。否则，1就放到了end位置处，这显然不对。因为，mini已经把maxi位置存的最大值悄悄地换走了，这时候我们最大值变到了mini位置处，此时，maxi位置要进行重新调整，maxi=mini；
-------------------------------------------------------------------------------------------------------------------------
?? ??? ?Swap(&a[end], &a[maxi]);
?? ??? ?begin++;
?? ??? ?end--;
?? ?}
}
测试结果：
插入排序特点
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)，最坏的情况也是O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
---------------------------------------------------------------------------------------------------------------------------------
? ?建堆（大堆）过程：
1、 在进行完大堆的建立后，我们就开始进行排序了（在这里换一个大堆举例）。首先将a[0]和? ? ? ? ? ? ?a[end]位置交换
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?2、此时交换后，这个堆就不是大堆了，这时候我们需要将a[0]向下调整，重新形成大堆。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 
?3、然后选出次大的数进行交换
? ? ? ? ? ? ? ? ? ? ? ? ? ??
4、........重复上面操作
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
5、最后的堆得到的数组：
? ? ? ? ? ? ? ? ?? ??
很明显，这个数组是有序的。
注意：每次交换后，最后一个数据就固定了，不在动了，所以接下来进行操作数据的个数为end-1
--------------------------------------------------------------------------------------------------------------------------------
?思考：为什么排升序时不建小堆呢？
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
这种堆对应的数组：
? ? ? ? ? ? ? ? ?
?我们在取出堆顶的数据后会发生这种情况：
? ? ? ? ? ? ??
?此时，这种数组对应的堆是：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
我们发现这是堆就已经不是小堆了！如果接着依次取栈顶的数据，最后得到的序列一定不是有序的。如果还想保证取出次小的数，就必须重新构建小堆，这样一来一来，时间复杂度就变大了，导致代码性能降低。所以排升序不推荐建立小堆。
---------------------------------------------------------------------------------------------------------------------------------
?HeapSort
第一种方法
//堆排序
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;//默认是左孩子
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child]) //排升序
{
child += 1;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]); //交换数字不是地址，不需要二级指针来交换，
//和反转二叉树交换节点区分开
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
void HeapSort(int* a, int n)
{
int i = 0;
for (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--;
}
}?//堆排序
void AdjustDown(int* a, int n, int parent) //建立大堆
{
?? ?int child = parent * 2 + 1;//默认是左孩子
?? ?while (child < n)//当向下调整时，孩子的下标值不超过n-1,否则就越界了
?? ?{
?? ??? ?if (child + 1 < n && a[child + 1] > a[child]) //选出左右孩子大的那一个
?? ??? ?{
?? ??? ??? ?child += 1;
?? ??? ?}
?? ??? ?if (a[child] > a[parent])//当孩子的值大于父母的值时，就交换。
?? ??? ?{
?? ??? ??? ?Swap(&a[child], &a[parent]);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?? ??? ?}?? ??? ?else
?? ??? ?{
?? ??? ??? ?break;
?? ??? ?}
?? ??? ?parent = child;//孩子的值赋给父母
?? ??? ?child = parent * 2 + 1;//左孩子的值重新确定
?? ?}
}
void HeapSort(int* a, int n)
{
?? ?int i = 0;
?? ?for (i = (n - 1 - 1) / 2; i >=0 ; i--)//向下调整，从最后一个非叶子节点开始调整，直到第一个节点调整完毕结束，此时就建立了大堆
?? ?{
?? ??? ?AdjustDown(a, n, i);
?? ?}
?? ?int end = n - 1;//最后一个数据的下标
?? ?while (end > 0)//当end==0时就停止了，这时候剩一个值了，没必要再排了，已经有序了
?? ?{
?? ??? ?Swap(&a[0], &a[end]);//交换第一个节点和最后一个结点
?? ??? ?AdjustDown(a, end, 0);//调整第一个节点，构成大堆时间复杂度O(logN),end在这里表示n-1个数据进行比较，因为最大的值在n-1位置已经π好了，不能再动了，此时可调的数据还有n-1个，即此时的end个。
?? ??? ?end--;//排好后，end--，便于确定次大数的位置
?? ?}
}
?第二种方法
//堆排序
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;//默认是左孩子
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child]) //排升序
{
child += 1;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (i = 1; i < n; i++)
{
AdjustUp(a, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}//堆排序
void AdjustDown(int* a, int n, int parent)//上面已经介绍过了
void AdjustUp(int* a, int child)
{
?? ?int parent = (child - 1) / 2;//父母和孩子坐标的关系，通过孩子找到父母
?? ?while (child > 0)//当孩子<=0时就结束，因为在下面的控制条件中，parent和child不会小于? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0，当parent==child等于0时就不用再比较了，终止循环
?? ?{
?? ??? ?if (a[child] > a[parent])//孩子大于父母的值时，就交换
?? ??? ?{
?? ??? ??? ?Swap(&a[child], &a[parent]);
?? ??? ??? ?child = parent;//父母位置的值赋给孩子
?? ??? ??? ?parent = (child - 1) / 2;//则再上一个父母的位置的值确定
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?break;
?? ??? ?}
?? ?}
}-------------------------------------------------------------------------------------------------------------------------
向上建堆的过程如下所示：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
1、比如我们把新插入的数字4进行向上调整，首先，4>1，则交换4和1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
2、接下来，4<7，即孩子小于父母，这时候就不用交换，然后break终止循环，大堆重新调整完毕。
-------------------------------------------------------------------------------------------------------------------------
void HeapSort(int* a, int n)
{
? ? for (i = 1; i < n; i++)//向上调整建堆，就从下标为0/1的位置开始依次建堆
?? ?{
?? ??? ?AdjustUp(a, i);//这里不像AdjustDown那样传元素个数
?? ?}
?? ?int end = n - 1;//为了记录末位置的下标，便于交换，再一个是反应了当前建堆参加元素的? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 个数
?? ?while (end > 0)
?? ?{
?? ??? ?Swap(&a[0], &a[end]);
?? ??? ?AdjustDown(a, end, 0);
?? ??? ?end--;
?? ?}
}
测试结果：
堆排序特点?
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定注意：在这里第一种方法O(N*logN+logN)要比第二种方法O(N*logN+N)效率高了一点点。但是并没有质的提升，所以我们不必纠结。
冒泡排序
冒泡排序是通过相邻的数字挨个比较大小，然后进行交换，依次选出最大的数。
1.原理：比较两个相邻的元素，将值大的元素交换到右边
2.思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
(2)比较第2和第3个数，将小数 放在前面，大数放在后面。
......
(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成
(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
(6)依次类推，每一趟比较次数减少依次
-------------------------------------------------------------------------------------------------------------------------
? ? ?
然后接着下一趟：
??-------------------------------------------------------------------------------------------------------------------------
由于冒泡排序比较简单，在这里不赘述了。
BubbleSort
第一种写法
// 冒泡排序
void BubbleSort(int* a, int n)
{
int j = 0;
for (j = 0; j < n - 1; j++)
{
int flag = 0;
int i = 0;
for (i = 0; i < n - 1 - j; i++)
{
if (a[i] > a[i + 1])
{
flag = 1;
Swap(&a[i + 1], &a[i]);
}
}
if (flag == 0)//flag==0时，说明就没有就行交换
{
break;
}
}
}第二种写法
void BubbleSort(int* a, int n)
{
int end = n - 1;
while (end > 0)
{
int i = 0;
for (i = 0; i < end; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
}
}
end--;
}
}//冒泡排序
void BubbleSort(int* a, int n)
{
?? ?int end = n - 1;//end控制躺数，每次n个数字进行排序时，一共要排n-1趟
?? ?while (end > 0)//控制终止条件，相当于：0<end<=n-1趟
?? ?{
?? ??? ?int i = 0;
?? ??? ?for (i = 0; i < end; i++)//(n-1)--,这里end不断--，所以end控制了每趟要比较的次数
?? ??? ?{
?? ??? ??? ?if (a[i] > a[i + 1])
?? ??? ??? ?{
?? ??? ??? ??? ?Swap(&a[i], &a[i + 1]);
?? ??? ??? ?}
?? ??? ?}
?? ??? ?end--;
?? ?}
}
测试结果：
?冒泡排序特点
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
快速排序
? ? ? ?快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
hoare版本（递归）
我们选择基准值作为key。通常我们选择最左边或者最右边作key。left和right记录数组两边界
左边做key：right先走，直到找到比key小的停止；left后走，直到找到比key大的停止。然后此时left和right位置的值进行交换。然后重复上面步骤，直到right==left时停止，再交换key和left/right(left==right)位置的值，此时基准值(key)就排好了。
右边做key：left先走，直到找到比key大的停止；right后走，直到找到比key小的停止。然后此时left和right位置的值进行交换。然后重复上面步骤，直到right==left时停止，再交换key和left/right(left==right)位置的值，此时基准值(key)就排好了。
?-------------------------------------------------------------------------------------------------------------------------
对于这种序列来说：
? ? ? ? ? ? ??
1、right先走，找到比key位置小的值就停下
2、left再走，找到比key位置大的值就停下
? ??
? 3、交换left和right位置的值
? ? ? ? ??
?4、由于left<right，继续上面步骤
? ? ??
?5、时候left==right了，left停止找大了，交换key和left/right(left==right)位置的值
? ? ? ? ? ? ??
?6、这时候4(key的值)就已经排好，左边的值都比4小(或者等于)，右边的值大于等于4
?7、接着我们对4的左边和右边按照同样的方法排序，然后分别返回最后left==right的位置，然后再分割子区间进行排序。
8、这样不断递归，当第一层的递归调用完时就排序完毕了?。
?-------------------------------------------------------------------------------------------------------------------------
QuickSort(hoare版本)
int PartSort1(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int key = left;//左边当key
while (left < right)
{
while (left<right && a[right]>=a[key])//右边先走，找到比key小的数就停下
{
right--;
}
while (left < right && a[left] <= a[key])//左边找大，找到比key打的就停下
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[left]);
return left;//left==right相遇位置
}
void QuickSort(int* a, int left, int right)
{
if (left >= right) //递归停止条件
{
return;
}
int keyi = PartSort1(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}int PartSort1(int* a, int left, int right)
{
?? ?int mid = GetMidIndex(a, left, right); //待会会介绍这个函数的意义
?? ?Swap(&a[left], &a[mid]);
?? ?int key = left;//左边当key
?? ?while (left < right)
?? ?{
?? ??? ?while (left<right && a[right]>=a[key])//右边先走，找到比key小的数就停下
?? ??? ?{
?? ??? ??? ?right--;
?? ??? ?}
?? ??? ?while (left < right && a[left] <= a[key])//左边找大，找到比key打的就停下
?? ??? ?{
?? ??? ??? ?left++;
?? ??? ?}
?? ??? ?Swap(&a[left], &a[right]);//把left比key大的值放到右边，把right比key小的值放到左边
?? ?}
?? ?Swap(&a[key], &a[left]);//最后处理key位置的值，使key位置的值排好顺序
?? ?return left;//left==right相遇位置
}
void QuickSort(int* a, int left, int right)
{
?? ?if (left >= right) //递归停止条件
?? ?{
?? ??? ?return;
?? ?}
?? ?int keyi = PartSort1(a, left, right);//分割成[left,keyi-1] keyi [keyi+1,right]
?? ?QuickSort(a, left, keyi - 1); //递归左区间
?? ?QuickSort(a, keyi + 1, right);//递归右区间
}
测试代码：
挖坑法 （递归）
先将最左边序列的数据存放到临时变量key中，自己形成一个坑位。(left和right表示待排序序列边界)。
最左边先当坑位：右边先走，找到比key小的值停下，把right的值放到坑中，然后right位置形成新的坑位；然后左边找比key大的值，找到后就停下，把left的值放入坑中，然后left再形成新的坑位。依次类推，直到left==right时就停止。
最右边先当坑位：左边先走，找到比key大的值停下，把left的值放到坑中，然后left位置形成新的坑位；然后右边找比key小的值，找到后就停下，把right的值放入坑中，然后right再形成新的坑位。依次类推，直到left==right时就停止。
?-------------------------------------------------------------------------------------------------------------------------
以这个序列为例：
1、右边找小，找到后停下
??
2、right位置的值放到pivot坑里面，然后right形成新的坑位
??
?
?3、left找大，找到比key大的值就停下
? ? ? ??????????????
?
3、然后把left位置的值放到pivot中，left再形成新的坑位
??
?4、接着right继续找小
5、此时，left==right，就停止下来了?，这时候把key的值放到坑中，这趟排序就结束了，key的值就已排好序了
?6、然后针对pivot左边和右边区间进行递归，排序，当第一层递归结束后就排好序了
??-------------------------------------------------------------------------------------------------------------------------
QuickSort(挖坑法)
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int key = a[left];//左边做key
int pivot = left;
while (left < right)
{
while (left<right && a[right]>=key)//右边先走，找到比key小的就停止
{
right--;
}
a[pivot] = a[right];//放入坑中
pivot = right;//右边形成新的坑位
while (left < right && a[left] <=key)//左边找大，找大比key大的数就停止
{
left++;
}
a[pivot] = a[left];//放入坑中
pivot = left;
}
a[pivot] = key;
return pivot; //left==right,返回坑位
}
void QuickSort(int* a, int left, int right)
{
if (left >= right) //递归停止条件
{
return;
}
int keyi = PartSort2(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}//挖坑法
int PartSort2(int* a, int left, int right)
{
?? ?int mid = GetMidIndex(a, left, right);//待会我们再介绍这个问题
?? ?Swap(&a[left], &a[mid]);
?? ?int key = a[left];//左边做key
?? ?int pivot = left;
?? ?while (left < right)
?? ?{
?? ??? ?while (left<right && a[right]>=key)//右边先走，找到比key小的就停止
?? ??? ?{
?? ??? ??? ?right--;
?? ??? ?}
?? ??? ?a[pivot] = a[right];//放入坑中
?? ??? ?pivot = right;//右边形成新的坑位
?? ??? ?while (left < right && a[left] <=key)//左边找大，找大比key大的数就停止
?? ??? ?{
?? ??? ??? ?left++;
?? ??? ?}
?? ??? ?a[pivot] = a[left];//放入坑中
?? ??? ?pivot = left;
?? ?}
?? ?a[pivot] = key;
?? ?return pivot; //left==right,返回坑位
}
测试结果：
前后指针法（递归）?
或者：
先找一个值作key，以上两种方法都可以。cur找比key小的值就停下，然后交换++prev和cur坐标位置的值然后cur++。如果没有找到，cur++。直到cur>right时就停止。最后交换key位置和prev位置的值，这样key位置的值就排好序了。
??-------------------------------------------------------------------------------------------------------------------------
我们以这个序列为例：
? ? ? ? ? ???
?1、cur找比key位置小的值，找到就停下
? ? ?
?2、交换++prev和cur位置的值，而此时++prev==cur，相当于没有交换，然后cur++
? ??
?3、重复步骤1和步骤2后
? ? ? ?
?4、cur接着找比key位置小的值，但是此时cur>4不是，则cur++
5、重复以上步骤，直到cur>right时就停止
6、这时候再交换key和prev位置的值 ，这时候原key位置的值就排好序了
? ??
?7、然后针对prev左边和右边区间进行递归，排序，当第一层递归结束后就排好序了
?
???--------------------------------------------------------------------------------------------------------------------------
QuickSort(前后指针法)
// 快速排序前后指针法
//int PartSort3(int* a, int left, int right)
//{
// int mid = GetMidIndex(a, left, right);
// Swap(&a[left], &a[mid]);
// int key = left;
// int prev = left;
// int cur = left + 1;
// while (cur <= right)
// {
// while (cur <= right && a[cur] >= a[key])
// {
// cur++;
// }
// if (cur <= right)
// {
// Swap(&a[++prev], &a[cur]);
// cur++; //每次交换后，对cur进行加加，保证持续往后找
// }
// }
// Swap(&a[key], &a[prev]);
// return prev;
//}
//简洁的写法
int PartSort3(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int key = left;
int prev = left;
int cur = left + 1;
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 left, int right)
{
if (left >= right) //递归停止条件
{
return;
}
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}// 快速排序前后指针法
//int PartSort3(int* a, int left, int right)
//{
// ?? ?int mid = GetMidIndex(a, left, right);
// Swap(&a[left], &a[mid]);
//?? ?int key = left;
//?? ?int prev = left;
//?? ?int cur = left + 1;
//?? ?while (cur <= right)
//?? ?{
//?? ??? ?while (cur <= right && a[cur] >= a[key])//找到比key小的值就停止
//?? ??? ?{
//?? ??? ??? ?cur++;
//?? ??? ?}
//?? ??? ?if (cur <= right)//当cur<=right时就不在进行Swap(&a[++prev], &a[cur]);否则就越界了
//?? ??? ?{
//?? ??? ??? ?Swap(&a[++prev], &a[cur]);
//?? ??? ??? ?cur++; //每次交换后，对cur进行加加，保证持续往后找
//?? ??? ?}
//?? ?}
//?? ?Swap(&a[key], &a[prev]);
//?? ?return prev;
//}
//简洁的写法
int PartSort3(int* a, int left, int right)
{
?? ?int mid = GetMidIndex(a, left, right);
?? ?Swap(&a[left], &a[mid]);
?? ?int key = left;//最左边位置作key
?? ?int prev = left;
?? ?int cur = left + 1;
?? ?while (cur <= right)//循环终止条件
?? ?{
?? ??? ?if (a[cur] < a[key] && ++prev != cur) //++prev==cur时，就没必要交换
?? ??? ?{
?? ??? ??? ?Swap(&a[cur], &a[prev]);
?? ??? ?}
?? ??? ?cur++;//每次判断a[cur]和a[key]时，都要把cur++
?? ?}
?? ?Swap(&a[key], &a[prev]);
?? ?return prev;
}
测试结果：
?快速排序优化
快速排序是一个很强大的排序，但是在处理有序或接近有序的序列时它的时间复杂度就会变成0(N^2);针对有序序列情况，快速排序可以进行三数取中来优化，每次处理的数选择的key值就不再是序列中最小或最大值。（ 尽管优化了，但是处理一组序列数字都相同的数字时，快速排序时间复杂度还是O(N^2) ）。
GetMidIndex
int GetMidIndex(int* a, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (a[left] > a[mid])
{
if (a[right] > a[left])
{
return left;
}
else if (a[mid] > a[right])
{
return mid;
}
else
{
return right;
}
}
else//a[left]<=a[mid]
{
if (a[right] > a[mid])
{
return mid;
}
else if (a[right] < a[left])
{
return left;
}
else
{
return right;
}
}
}选出当前要排序列的最左边，中间，最右边的值中既不是最大也不是最小的值。
当我们选好后，就在进行这样操作：
?? ?int mid = GetMidIndex(a, left, right);
?? ?Swap(&a[left], &a[mid]);所以在每个PartSort开始进行以上操作，这样就保证了选取的最左边的key值就不是有序序列中的最值了，这种方法针对有序序列来排序的。
注意：尽管优化了，但是处理一组序列数字都相同的数字时，快速排序时间复杂度还是O(N^2)。
小区间优化
我们在每次递归时，最后几层的递归占了绝大次数。
?我们发现最后几层占了递归次数的绝大部分。递归调用次数太多了，我们怎样来解决这个问题呢？只要在最后几层的序列不使用快排而借助其他排序使他们有序，这样就不用递归调用了。选择排序是排序中性能最差的，插入排序的适应性比冒泡排序更好，所以选用插入排序（使用希尔排序和堆排序有点杀鸡用牛刀了，他们适合对数据个数较大的序列排序）。我们在这里可以尝试在快速排序最后几层使用其他排序(InsertSort)来优化。
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 keyi = PartSort1(a, left, right);
//int keyi = PartSort2(a, left, right);
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}void QuickSort(int* a, int left, int right)
{
?? ?if (left >= right) //递归停止条件
?? ?{
?? ??? ?return;
?? ?}
?? ?if (right - left + 1 < 10)? //在这里我们默认这个区间个数是10
?? ?{
?? ??? ?InsertSort(a + left, right - left + 1);//a+left，从数组这个位置开始排；right - left +1，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?排序数据的个数
?? ?}
?? ?else
?? ?{
?? ??? ?//int keyi = PartSort1(a, left, right);
? ? ? ? //int keyi = PartSort2(a, left, right);
?? ??? ?int keyi = PartSort3(a, left, right);
?? ??? ?QuickSort(a, left, keyi - 1);
?? ??? ?QuickSort(a, keyi + 1, right);
?? ?}
}
快速排序特点
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定?
快速排序（非递归）
上面介绍的三种快速排序方法都是使用递归的方法来实现的，如果处理的数据太大时，可能会出现栈溢出的情况，我们能不能想办法来实现一种非递归的快速排序呢？
我们要解决的问题是，当我们处理好一段左区间的排序后，右区间的范围怎么来找?我们需要借助东西来自动存储这个范围。那么用什么合适呢？
答案是用栈（后进先出的特点）来存储要排序的范围。以便左区间排序完毕后能够找到右区间。
我们要首先模拟栈，在这里不再讲述了，详细请看：栈的模拟实现（顺序表来模拟）_暴走的橙子～的博客-CSDN博客
-------------------------------------------------------------------------------------------------------------------------------
下面我们用图来展示这个过程，（我们就不采用三数取中了，直接进行PartSort来使key有序）。
1、我们先用栈保存要排序数组的下标
2、当栈空间不为空时就继续，取出数据，获得要排序区间的范围后进行PartSort排序。我们先存放这个区间的下限，再存放上限；先存放递归的右区间，再存放左区间的范围。
?3、这时候我们可以取出范围0~1的区间进行排序，取出后删掉0和1
4、0~1范围数是有序的，我们没必要存入栈中了接下来 我们取出3和9来进行范围3~9排序
?5、然后取出4和9，对范围4~9的数据进行依次PartSort，使得key有序。不断重复上面步骤。
当栈中的数据为空时（相当于递归的第一层调用完毕后），就排完有序了。
-------------------------------------------------------------------------------------------------------------------------------
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
struct Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))//当栈不为空时，就说明有可以继续排的区间
{
int end = StackTop(&st); //从栈里面先拿出的是右区间
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int keyi = PartSort3(a, begin, end);//对指定的区间进行排序
//[begin,keyi-1] keyi [keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
if (begin < keyi - 1)
{
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
}
StackDestory(&st);//记得最后销毁栈空间
}// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
?? ?struct Stack st;//给结构体定义一个变量
?? ?StackInit(&st);//初始化栈
?? ?StackPush(&st, left);//压栈
?? ?StackPush(&st, right);//压栈
?? ?while (!StackEmpty(&st))//当栈不为空时，就说明有可以继续排的区间
?? ?{
?? ??? ?int end = StackTop(&st); //从栈里面先拿出的是区间的上限
?? ??? ?StackPop(&st);//出栈
?? ??? ?int begin = StackTop(&st);//从栈里面后拿出的是区间的下限
?? ??? ?StackPop(&st);
?? ??? ?int keyi = PartSort3(a, begin, end);//对指定的区间进行排序
?? ??? ?//[begin,keyi-1] keyi [keyi+1,end]
?? ??? ?if (keyi + 1 < end)//可以再分成子区间的范围就压栈
?? ??? ?{
?? ??? ??? ?StackPush(&st, keyi + 1);//先存放右区间
?? ??? ??? ?StackPush(&st, end);
?? ??? ?}
?? ??? ?if (begin < keyi - 1)//可以再分成子区间的范围就压栈
?? ??? ?{
?? ??? ??? ?StackPush(&st, begin);//后存放左区间
?? ??? ??? ?StackPush(&st, keyi - 1);
?? ??? ?}
?? ?}
?? ?StackDestory(&st);//记得最后销毁栈空间（动态开辟的）
}
测试结果：
归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。注意：归并排序需要开辟一块等大的空间来存放数据，完后把数据拷贝到原数组。
?MergeSort
//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)//递归的终止条件
{
return;
}
int mid = left + ((right - left) >> 1);
//[left,mid] [mid+1,right]
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
int j = 0;
for (j = left; j <= right; j++)
{
a[j] = tmp[j];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
?? ?if (left >= right)//递归的终止条件
?? ?{
?? ??? ?return;
?? ?}
?? ?int mid = left + ((right - left) >> 1);//作用相当于(left+right)/2,只不过 left + ((right - left) >> 1)有效避免left+right后的数据int类型存不下，并且右移运算符(>>)效率比'/'要高
?? ?//[left,mid] [mid+1,right]
?? ?_MergeSort(a, left, mid, tmp);//递归左区间
?? ?_MergeSort(a, mid + 1, right, tmp);//递归右区间，当左右区间有序时，就可以合并了
?? ?int begin1 = left;
?? ?int end1 = mid;
?? ?int begin2 = mid + 1;
?? ?int end2 = right;
?? ?int i = left;//记录数据存放在tmp中的位置
?? ?while (begin1 <= end1 && begin2 <= end2)
?? ?{
?? ??? ?if (a[begin1] < a[begin2])
?? ??? ?{
?? ??? ??? ?tmp[i++] = a[begin1++];
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?tmp[i++] = a[begin2++];
?? ??? ?}
?? ?}
?? ?while (begin1 <= end1)
?? ?{
?? ??? ?tmp[i++] = a[begin1++];
?? ?}
?? ?while (begin2 <= end2)
?? ?{
?? ??? ?tmp[i++] = a[begin2++];
?? ?}
?? ?int j = 0;
?? ?for (j = left; j <= right; j++) //把每次排好的存放到临时数组中的数据，重新拷贝到原数组方便返回上层递归时的排序
?? ?{
?? ??? ?a[j] = tmp[j];
?? ?}
}
void MergeSort(int* a, int n)
{
?? ?int* tmp = (int*)malloc(n * sizeof(int));//开辟一块和和原数组等大的空间
?? ?if (tmp == NULL)//判断是否开辟成功，在VS2019版本不判断的话会报警告
?? ?{
?? ??? ?printf("malloc fail\n");
?? ??? ?exit(-1);
?? ?}
?? ?_MergeSort(a, 0, n - 1, tmp);//传参过去给子区间，然后进行排序
?? ?free(tmp);//释放空间
?? ?tmp = NULL;//置空
}
测试结果：
归并排序特点?
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
归并排序（非递归）
归并排序非递归的难度主要在于比边界的控制上。
我们首先按照gap=1分组，然后在各自的组内进行排序。紧接着gap=gap*2;继续分组，将两个有序序列合并......这样不断下去，直到gap>n时结束后，就把整个序列排好了。
--------------------------------------------------------------------------------------------------------------------------------
比如如下图所示：
? ? ? ? ? ? ??
1、首先,gap==1，我们将各自分的组进行排序
2、gap*=2,将gap==1时合并好的那5组进行合并，我们重复上面的操作（越界的部分不参与排序比较）
?
?3、gap*=2，将gap==2时合并好的那3组进行合并，我们再次重复上面的操作（越界的部分不参与排序比较）
4、gap*=2，接着操作，将最后(gap==4合并好的两组)两组进行合并（越界的部分不参与排序比较）
--------------------------------------------------------------------------------------------------------------------------------
MergeSortNonR
第一种写法
//归并排序非递归
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)
{
int i = 0;
for (i = 0; i < n; i += 2 * gap)
{
// 分组后：[i,i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
if (end1 >= n)//end1越界 [begin2，end2]不存在
{
end1 = n - 1;
}
if (begin2 >= n)//[begin1,end1]存在， [begin2，end2]不存在
{
begin2 = n;
end2 = n - 1;
}
if (end2 >= n)//[begin1, end1],end2存在，end2不存在
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
//printf(" %d ", index);
tmp[index++] = a[begin1++];
}
else
{
//printf(" %d ", index);
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
//printf(" %d ", index);
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
//printf(" %d ", index);
tmp[index++] = a[begin2++];
}
}
//临时数组中的数据拷贝到原数组
for (i = 0; i < n; i++)
{
a[i] = tmp[i];
}
//printf("\n");
gap *= 2;
}
free(tmp);
tmp = NULL;
}//归并排序非递归
void MergeSortNonR(int* a, int n)
{
?? ?int* tmp = (int*)malloc(sizeof(int) * n);//开辟好临时数组进行储存
?? ?if (tmp == NULL)
?? ?{
?? ??? ?printf("malloc fail\n");
?? ??? ?exit(-1);
?? ?}
?? ?int gap = 1;//从gap==1开始排
?? ?while (gap < n)
?? ?{
?? ??? ?int i = 0;
?? ??? ?for (i = 0; i < n; i += 2 * gap)
?? ??? ?{
?? ??? ??? ?// ?分组后：[i,i+gap-1] [i+gap,i+2*gap-1]------------------------------------------------------------------------------------------------------------------------
每一组的下标，也就是将要合并两组下标控制的范围：[i,i+gap-1] [i+gap,i+2*gap-1]。在每合并两个区间时，那两个子区间是已将排好序的。
??------------------------------------------------------------------------------------------------------------------------? ? ? ? ? ?int begin1 = i;
?? ??? ??? ?int end1 = i + gap - 1;
?? ??? ??? ?int begin2 = i + gap;
?? ??? ??? ?int end2 = i + 2 * gap - 1;
?? ??? ??? ?//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);//begin1是一定控制的数组下标一定时有效的，但是，end1，begin2，end2是可能越界的。也就是我们每次分组时最后一组指向空的情况。
//处理边界情况
?? ??? ??? ?if (end1 >= n)? ? ?//end1越界 [begin2，end2]不存在
?? ??? ??? ?{
?? ??? ??? ??? ?end1 = n - 1;//修正区间，方便[begin1,end1]的数据顺序不变拷贝到临时数组中
?? ??? ??? ?}
?? ??? ??? ?if (begin2 >= n)//[begin1,end1]存在， [begin2，end2]不存在,这时候后面的区间没必要参与归并排序，直接把[begin1,end1]数据按照原来顺序拷贝下来就行了。
?? ??? ??? ?{
?? ??? ??? ??? ?begin2 = n;
?? ??? ??? ??? ?end2 = n - 1;
?? ??? ??? ?}
?? ??? ??? ?if (end2 >= n)//[begin1, end1],end2存在，end2不存在，这时候begin2还是需要排序的，还是需要归并两个区间，这时候修正end2
?? ??? ??? ?{
?? ??? ??? ??? ?end2 = n - 1;
?? ??? ??? ?}? ? ? ? ? ? ??...........
?? ??? ?}
?? ??? ?//临时数组中的数据拷贝到原数组
?? ??? ?for (i = 0; i < n; i++) //这里时归并排序一轮后整体把临时数据中的数据拷贝到原数组
?? ??? ?{
?? ??? ??? ?a[i] = tmp[i];
?? ??? ?}
?? ??? ?//printf("\n");
?? ??? ?gap *= 2;
?? ?}
?? ?free(tmp);
?? ?tmp = NULL;
}
第二种方法
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)
{
int i = 0;
for (i = 0; i < n; i += 2 * gap)
{
// 分组后：[i,i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
if (end1 >= n || begin2>=n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
//printf(" %d ", index);
tmp[index++] = a[begin1++];
}
else
{
//printf(" %d ", index);
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
//printf(" %d ", index);
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
//printf(" %d ", index);
tmp[index++] = a[begin2++];
}
//把归并小区间拷贝到原数组
int j = 0;
//for (j = i; j <= i + 2 * gap - 1; j++)//i + 2 * gap - 1可能就越界了
for (j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
//printf("\n");
gap *= 2;
}
free(tmp);
tmp = NULL;
}void MergeSortNonR(int* a, int n)
{.............
?? ?int gap = 1;
?? ?while (gap < n)
?? ?{?............
//处理边界情况
?? ??? ??? ?if (end1 >= n || begin2>=n)// [begin1, end1],[ begin2, end2]。end1越界时，[ begin2, end2]也越界了，这时候不用再合并了，原数组[begin1,n-1]的数据时有序的；
begin2越界时，end2也越界了，这时候不用再合并了，原数组[begin1,end1]的数据时有序的；此时直接break跳出循环就行了
?? ??? ??? ?{
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?if (end2 >= n)//end2越界时，begin2不越界，这时候[begin1, end1],[ begin2,n-1]里面数据需要合并来使[begin1,n-1]区间有序，这时候就需要修正end2
?? ??? ??? ?{
?? ??? ??? ??? ?end2 = n - 1;
?? ??? ??? ?}? ? ? ? .........
?? ??? ??? ?//把归并小区间拷贝到原数组
?? ??? ??? ?int j = 0;
?? ??? ??? ?//for (j = i; j <= i + 2 * gap - 1; j++)//i + 2 * gap - 1可能就越界了
?? ??? ??? ?for (j = i; j <= end2; j++)//每次比较一组时就把排好顺序的数据从临时数组拷贝到原数组，造成第一和第二方法不同的原因
?? ??? ??? ?{
?? ??? ??? ??? ?a[j] = tmp[j];
?? ??? ??? ?}
?? ??? ?}
?? ??? ?//printf("\n");
?? ??? ?gap *= 2;
?? ?}
?? ?free(tmp);
?? ?tmp = NULL;
}
测试结果：
?归并排序特点（非递归）
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
-------------------------------------------------------------------------------------------------------------------------------
比如我们以这个序列为例：
1、首先我们先遍历一遍 序列选出最大值max=8，最小值min=1，开辟出(max-min+1)=8大小的空间
? ? ? ?
?2、遍历一遍序列，存放数据映射关系下标：i=cur(遍历的当前数)-min
?3、每次计算出下标后，在新开辟数组对应的下标位置上进行++
?4、遍历一遍临时数组，通过cur=i+min来找到原数据，再根据每个下标里面对应的数字来确定拷贝cur次数，逐个拷贝到原数组，这样就有序了
-------------------------------------------------------------------------------------------------------------------------------
CountSort
//计数排序
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
int i = 0;
for (i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
//开始计数
//相对位置：下标i=cur-min
for (i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//根据次数进行排序
int j = 0;//记录数组a下标
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
count = NULL;
}//计数排序
void CountSort(int* a, int n)
{
?? ?int max = a[0];
?? ?int min = a[0];
?? ?int i = 0;
?? ?for (i = 0; i < n; i++)//遍历一遍数组选出最大值和最小值
?? ?{
?? ??? ?if (a[i] > max)
?? ??? ?{
?? ??? ??? ?max = a[i];
?? ??? ?}
?? ??? ?if (a[i] < min)
?? ??? ?{
?? ??? ??? ?min = a[i];
?? ??? ?}
?? ?}
?? ?int range = max - min + 1;//确定要开辟临时数组大小
?? ?int* count = (int*)malloc(sizeof(int) * range);
?? ?memset(count, 0, sizeof(int) * range);//把计数数组中里面的值初始化成0
?? ?//开始计数
?? ?//相对位置：下标i=cur-min
?? ?for (i = 0; i < n; i++)
?? ?{
?? ??? ?count[a[i] - min]++;//i=a[i] - min,通过这样的映射来找到count数组下表位置，然后++
?? ?}
?? ?//根据次数进行排序
?? ?int j = 0;//记录数组a下标
?? ?for (i = 0; i < range; i++)//遍历一遍计数数组
?? ?{
?? ??? ?while (count[i]--)//同过计数数组里面存放的值来确定数据个数
?? ??? ?{
?? ??? ??? ?a[j++] = i + min;//通过映射：i+min来找到a[i](cur)的值
?? ??? ?}
?? ?}?? ?free(count);
?? ?count = NULL;
}
测试结果：
?计数排序特点
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,rang))
3. 空间复杂度：O(range)4、适合数据集中的序列排序，否则空间消耗会比较大（不适用正数和负数同时存在的序列排序）
排序算法性能总结
稳定性：数组相同的值，在排序以后相对位置是否变化。可能会变，不稳定。能保证不变的，就是稳定。
?排序性能大比拼
既然已经介绍了呢么多的排序算法，是时候该一决高下了，我们在这里多组数据测试进行比较。
我们在VS2019relase版本下进行测试。
TestOP
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
void TestOP()
{
srand((unsigned int)time(NULL));
int n = 50000;
int* a1 = (int*)malloc(n * sizeof(int));
int* a2 = (int*)malloc(n * sizeof(int));
int* a3 = (int*)malloc(n * sizeof(int));
int* a4 = (int*)malloc(n * sizeof(int));
int* a5 = (int*)malloc(n * sizeof(int));
int* a6 = (int*)malloc(n * sizeof(int));
int* a7 = (int*)malloc(n * sizeof(int));
int* a8 = (int*)malloc(n * sizeof(int));
int* a9 = (int*)malloc(n * sizeof(int));
int* a10 = (int*)malloc(n * sizeof(int));
int i = 0;
for (i = 0; i < n; i++)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
a9[i] = a1[i];
a10[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, n);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, n);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, n);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, n);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, n - 1);
int end5 = clock();
int begin6 = clock();
QuickSortNonR(a6, 0, n - 1);
int end6 = clock();
int begin7 = clock();
MergeSort(a7, 0, n - 1);
int end7 = clock();
int begin8 = clock();
BubbleSort(a8, n);
int end8 = clock();
int begin9 = clock();
MergeSortNonR(a9, n);
int end9 = clock();
int begin10 = clock();
//CountSort(a10, n);
int end10 = clock();
//单位是毫秒
printf("InsertSort : %d\n", end1 - begin1);
printf("ShellSort : %d\n", end2 - begin2);
printf("SelectSort : %d\n", end3 - begin3);
printf("HeapSort : %d\n", end4 - begin4);
printf("QuickSort : %d\n", end5 - begin5);
printf("QuickSortNonR : %d\n", end6 - begin6);
printf("MergeSort : %d\n", end7 - begin7);
printf("BubbleSort : %d\n", end8 - begin8);
printf("MergeSortNonR : %d\n", end9 - begin9);
//printf("CountSort : %d\n", end10 - begin10);
free(a1);
a1 = NULL;
free(a2);
a2 = NULL;
free(a3);
a3 = NULL;
free(a4);
a4 = NULL;
free(a5);
a5 = NULL;
free(a6);
a6 = NULL;
free(a7);
a7 = NULL;
free(a8);
a8 = NULL;
free(a9);
a9 = NULL;
free(a10);
a10 = NULL;
}
int main()
{
TestOP();
return 0;
}10000个数测试用例
50000个数测试用例
?由于计数排序在这种情况开辟的空间过大，我的电脑栈空间不够用，在这里屏蔽掉计数排序的测试了。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?
?100000个数测试用例
?
我们屏蔽掉插入排序、选择排序、冒泡排序进行比较。?
?
?总结
我们可以发现快速排序、希尔排序、堆排序、归并排序的效率很高，几乎是同一级别。
再次一级比较，理论上：插入排序（和冒泡排序效率差不多，但是插入排序的适应性更好）>冒泡排序(当序列有序时为O(N))>选择排序（无论什么情况都是O(N^2）
总体来说，快速排序的还是用的比较广泛的，只是在排序一个序列都是相同值或几乎所有值都是一样时，效率成了O(N^2),这时候可以选择其他排序来解决问题。