1. hoare法(最原始版本）：
图解：
//Hoare版本的单趟快排 int PartSort1(int* arr1, int left,int right)//先进行单趟快排,这里对应的left和right都是下标，注意对于让其同时自动跳动位置的情况，使用循环去处理是最好的，而不是用if语句，那样适用于变化相同的情况 { int midi = GetMidi(arr1, left, right); swap(&arr1[left], &arr1[midi]);//取到中间数据的下标后，将其与left交换，即可让key的值为中间值，这样的话进行快速排序的速度就会避免n^2的情况了 int key = left;//注意这里要操作key的下标 while (left < right)//这便是单趟循环的过程 { while (left<right&&arr1[right]>=arr1[key])//利用循环去处理这个过程，而不是利用if语句,要加上等于的情况，否则程序会死循环一直不动 { right--; } while (left<right&&arr1[left]<=arr1[key])//同样加上等于防止程序死循环.加上left<right是为了防止，假设right访问的每一个数都比key大于等于，则这个循环会一直持续到遍历结束，然后越界，同样left也是同理，所以我们要控制left<right以保证访问不会越界 {//即极端最坏情况下他们两个相遇就不循环了 left++; } swap(&arr1[right], &arr1[left]);//跳出循环就交换 } swap(&arr1[left], &arr1[key]);//相遇就跟key交换 return left;//返回key下标方便下一步分治 }
思路：
最初的版本思路就是很简单，就是将最左边的值设为基准值key，然后设置两个指针left和right,right向左移动，left向右移动，当right对应的元素小于key对应的值时，right停下，left则是大于时停下，然后交换他们两个对应的元素，然后继续这个过程直到left==right，此时将对应的下标的元素和key对应的元素交换，返回left对应的下标即可，此时这个坐标就是我们需要的正确位置的中间值的正确位置的下标，而我们接下来进一步递归它的左边和右边即可
注意细节：
1.防止越界的问题，这个排序法越界的情况有这种情况：倘若right或者left一直移动，就有可能直接移动到数组下标之外，所以，我们在移动的时候，需要加上一个控制条件：left<right，这样，就不会发生越界的情况了，而是当left等于right后就会直接交换key了。
2.注意死循环的问题，我们必须要处理相等的问题，因为不处理的话，指针不会向后走，那么永远也实现不了left>=right的循环跳出条件，所以我们要让其数值等于key的时候也要让指针向后走。
3.注意，我们在快速排序操作的同样是下标，别看错了
2.挖坑法(原始版本优化）：
图解：
/挖坑法版本的单趟快排 int PartSort2(int* arr1, int left, int right)//注意，坑位的值是可以忽略的，所以这里不要用交换，直接赋值覆盖即可，我写的交换很容易出现错误，倘若赋值为0就会出错 { int midi = GetMidi(arr1, left, right); swap(&arr1[left], &arr1[midi]); //注意不要赋值为0，除非你保证再调整一次指针，交换使用0会有bug，但假如是直接覆盖就不会出现这种情况 int key = arr1[left]; int hole = left;//注意，这里不能赋值为0，那样的话就没法递归了，直接写死了 while (left < right) { while (left<right && arr1[right] >= key) { right--; } arr1[hole] = arr1[right]; hole = right; while (left < right && arr1[left] <= key) { left++; } arr1[hole] = arr1[left]; hole = left; } arr1[hole]=key;//循环结束后把数值放入坑位 return left; }
思路：
挖坑法是原始版本的进一步更新，它的区别就是key不再存在于数组里，而是存储数组的left位置独立出来，然后把left位置当成初始的第一个坑，然后利用和原始版本相同的left和right双指针，right对应的元素和key本身去比，倘若小于就停下并且将数值放在hole位置，然后hole位放到right的位置，left则反之大于就放在hole的新位置，然后再把hole放在left的位置，周而复始，直到遇到left=right停下，然后将这个位置的数值和key去交换，返回left的下标即可
注意细节：
1.注意挖坑法的key是数值而不是下标了，这个跟原始版本是不一样的，别一概而论，要清楚的思考好这些问题。
2.由于hole里面的数值可以忽略，故我们直接覆盖即可，不要用交换，那样会出错
补充：
！！！！我们发现一个细节，就是我使用这两种方法的时候前面都有一个：
int midi = GetMidi(arr1, left, right); swap(&arr1[left], &arr1[midi]);
这个代码是用来做什么的呢？
由于快速排序的核心思路便是找到对应的中间的数值并且放到正确的位置上，故我们找到的数值越接近之间值，则排序会越快，反之就会越慢，这就是快速排序的时间复杂度极其不稳定的原因，因此，我们使用一个三数取中的方法去稳定每次我们的mid值，让其与left位置的数值交换，让我们取到的key越发接近于每一组数据的中间值，这样就可以稳定我们快速排序的时间复杂度和速度。
三数取中的代码如下：
int GetMidi(int* arr1, int left, int right)//三数取中法函数，防止遇到全数据有序的情况快排受不了，由于有序。故取中值基本上就是最中间的数据，我们用三数取中的方法取的就是整个数据中的中间数据 {//注意啊，这里操作的是下标而不是具体的数值，但比较的是数值 int mid = (left + right) / 2; if (arr1[left] > arr1[mid]) { if (arr1[right] < arr1[mid]) { return mid; } else if (arr1[right] > arr1[left]) { return left; } else { return right; } } else//arr1[left]<arr1[mid] { if (arr1[mid] < arr1[right]) { return mid; } else if (arr1[right] < arr1[left]) { return left; } else { return right; } } //这里还是用逻辑判断法吧，假如要用比较函数需要在堆区开辟大量空间，会让堆区内存占满，所以还是用逻辑判断法比较好 }
3.前后双指针法(最推荐版本）：
代码如下：
//前后双指针版本的单趟快排 int PartSort3(int* arr1, int left, int right) { int midi=GetMidi(arr1,left,right); Swap(&arr1[left],&arr1[midi]); int key = left; int prev = left; int cur = left + 1; while (cur <= right) { if (arr1[cur] < arr1[key]&&++prev!=cur)//如果prev=cur就没必要交换了，这样可以优化运算速度,这里很细节，在判断的逻辑里对prev先++，哪怕判断为空，这是为了预防prev与cur初始的位置发生重合的情况，比如遇到两个数据都小于key，就会导致prev的移动后与cur的位置重合，此时不交换 { swap(&arr1[++prev], &arr1[cur]); } cur++; } swap(&arr1[key], &arr1[prev]); return prev; }
思路：
前后双指针的思路就是，创建一个指针prev指向left，下一个指针cur指向left+1,形成一个前后指针，然后跟原始版本一个思路，把left位置当成基准值key,然后cur向后走，yo倘若cur遇到大于等于key的值，正常向后走，不用管其他的，倘若小于key对应的值，则首先将prev++让其访问到下一位然后与cur对应的位置数值交换，之后持续这个过程，直到cur遇到边界，此时交换key对应的数值和prev对应的数值，然后返回prev下标即可。
注意的细节：
1.我们操作的依旧是下标，这一点别忘了，快速排序最特殊的只有挖坑法的key是数值，其他的都是下标。
2.当prev++后倘若与cur下标相同，就没必要交换了，这样可以省下运算速度。
4.进一步优化快速排序：
void QuickSort(int* arr1, int left,int right)//快速排序函数 {//我认为思路同直接选择排序差不多，都是直接操作下标来操作，其思路有点类似二叉树递归的思想，直接查找key，查找key左侧，查找key右侧这样的思路进行 if (left >= right)//注意，结束传递开始回归的情况有两种，第一种为只有一个元素了，此时left==right了，第二种情况是，存在递归的过程中比如left 0,right 1的情况，此时右边的递归left=2而right仍为1，这样的话就存在left大于right的情况，所以我们返回的条件是left>=right { return; } if (right - left > 10)//注意这里我加上这句话的原因，考虑到递归快排越向下递归的次数越多，但对于10个数据来说，其排序已经基本确定好了，对于这种小范围的排序，直接插入排序的效率更高且可以省略更多大量的递归排序。 { int keyi = PartSort3(arr1, left, right); QuickSort(arr1, left, keyi-1);//注意这里的思路，先递归左边，再递归右边，仿照二叉树前序遍历的方法去思考即可 QuickSort(arr1, keyi+1, right); } else { InsertSort(arr1 + left, right - left + 1);///当数据量小于10的时候，直接用直接插入排序即可，传参注意第二个参数是个数，right-left后要加上1，这样才表示个数 }//注意，一定要加else，否则这里会重复运算直接插入排序，效率十分低，要明确，这里是一种选择，直接插入排序不是必须要执行的，只有到小于等于10的情况下才执行。 }
我们在这里对快速排序进行了进一步的优化，优化的空间在于，倘若数据不断地分割后每一组数据的数据量已经很少的时候，就没必要再使用单趟分割了，就像我们为什么选择向下排序建堆而不是向上排序建堆一个道理，越向下，数据划分的越细小，枝叶越多，分支越多，则单趟快排的次数越多，这样程序的运行效率就更低，但相比之下其实对于小于10的数据数组，我们完全可以直接对其插入排序就好，这也是为什么我说排序无好坏，主要是根据不同场景下的灵活使用。
5.快速排序的非递归算法：
使用递归当然是快速排序最契合的思路和方法，但我们有时候会与遇到递归堆栈过深导致爆栈的问题，这个时候我们必须紧急抢救这样的情况，再用递归已经不现实了，所以作为合格的程序员，我们理应要掌握非递归的快速排序写法。
！！！！首先要强调一下，非递归去实现递归的过程其实也就是利用循环模拟递归的过程，我们在二叉树层序遍历的时候就已经利用队列实现了这个思路，所以我们的快速排序的非递归也是如此。！！！
我们这里的快速排序的非递归是利用一个栈辅助实现的
代码如下：
void QuickSortNonR(int*arr1,int left,int right)//快速排序的非递归写法（辅助栈实现） { ST st; STInit(&st); STPush(&st,right); STPush(&st, left);//首先把首位区间存进去，注意栈的特点，先进后出，所以我们进栈和出栈的顺序要对称 while (!STEmpty(&st)) { int begin = STTop(&st);//先获取左区间 STPop(&st);//注意，一定要删除，这样方便左区间向右区间转化 int end = STTop(&st);//再获取右区间 STPop(&st);//这里要把左区间和右区间存起来，因为后续就要删除 int keyi = PartSort3(arr1, begin, end); if (keyi+1 < end)//先入栈右区间 { STPush(&st, end); STPush(&st, keyi +1); } if (keyi - 1 > begin)//跟递归的返回条件一样，不符合的数据就自动不入栈了，然后数据不入栈，就如同左访问结束去访问右边一样 { STPush(&st, keyi - 1); STPush(&st, begin);//再入栈左区间，这样数据出栈的时候就是先出左区间，再去右区间 } } STDestroy(&st); }
思路：
我们的主要目的就是利用栈去模拟实现一个快速排序的递归过程，所以我们找中间值正确位置的下标的单趟用三种方法均可，首先将left和right放入栈，然后进入我们的循环，控制条件为不为空，如同层序遍历一样，我们首先要存储left和right的值，然后将两个数值从栈中pop掉，然后利用单趟排序找到keyi关键值，之后就是一个模拟递归的过程，将分别区间的左右值进行判断是否符合left<right，符合就放入栈，然后持续这个过程直到栈为空即可。
注意细节：
1.栈的特点是先进后出，所以我们的目的是先递归左边再递归右边，故我们放入栈的顺序应该为先放入右边再放入左边，这样就可以先利用左边的边界先处理，然后每一次循环都是如此，左边永远被先出栈和先使用，这就模拟了我们先递归左边的过程，然后栈里面就剩下了剩下的右边，然后右边再分成左边和右边，同样也是先处理左边…这就模拟了一个递归的过程，所以一定要注意：先放右边再放左边才能先用左边再用右边模拟递归
2.注意数据要及时出栈，这样才能形成一个模拟递归
3.使用了栈，别忘了最后要销毁栈，释放内存
2.归并排序-----时间复杂度O(N*log(N)) 空间复杂度O(N)
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并首先是要归，即不断分割数组，不断分割 不断分割直到数组无法分割为止，然后是下一个并的过程，即将归的数据首先进行排序后整体归还到原数组中完成一次归并，故我们这里采取类似快速排序差不多的递归思路去处理问题。
1.归并排序的递归写法：
如图：
代码如下：
void _MergeSort(int* arr1,int left,int right,int* tmp)//归并的分割子函数.传入tmp数组是用来进行归并过程的 { if (left >= right) { return; } int mid = (left + right) / 2; _MergeSort(arr1,left, mid,tmp);//先分隔左边 _MergeSort(arr1, mid+1,right,tmp); //归并到tmp数据组，然后将其拷贝回去 int begin1 = left; int end1 = mid; int begin2 = mid + 1; int end2 = right; int newbegin = left;//注意，运用递归，要用递归的思路展开 while (begin1 <= end1 && begin2 <= end2)//对数据继续归并排序进入tmp数据组并且排好序放入 { if (arr1[begin1] <= arr1[begin2])//在这里加上一个等号，这样的话归排序就变成稳定的了，倘若不加的话归并排序是不稳定的 { tmp[newbegin++] = arr1[begin1++]; } else //注意，这里不要光用if,因为光用if会导致一旦遇到相等的情况，指针不会向后走，循环就会一直进行，这里是关于if语句的理解不到位，这里要注意，别弄错了 { tmp[newbegin++] = arr1[begin2++]; } } while (begin1 <= end1) { tmp[newbegin++] = arr1[begin1++]; } while (begin2 <= end2) { tmp[newbegin++] = arr1[begin2++]; } memcpy(arr1 + left, tmp + left, (right - left + 1) * sizeof(int));//最后要把数据再从tmp拷贝回去到原字符串中，注意，这里传arr1+left和tmp+left是因为防止其tmp本身的数据覆盖造成乱序，让其对应好位置开始归并排序存入tmp中，也就是说，拷贝不一定是从0开始的，准确来说是从begin开始的 } void MergeSort(int* arr1, int sz)//归并排序，核心思想是递归和两个数组的插入排序 { int* tmp = (int*)malloc(sizeof(int) * sz);//首先定义一个数组用来存储数据 if (tmp == NULL) { perror("malloc fail"); exit(-1); } //归并排序，需要我们分割数组的位置，所以这里需要一个子函数用来递归 _MergeSort(arr1, 0, sz - 1, tmp); free(tmp); tmp = NULL; }
思路：
归并排序的大体思路，就是利用一个开辟的动态数组，在数据分割回归完之后，针对每一步的数据，利用我们的两个数组排列成一个有序数组的方法去写一个有序的尾插，这样就保证了每一组数都获得了排序，然后传回了原来的数组，我们的递归过程也是先左递归再右递归不断的缩小范围
细节：
1.归并排序的第一个细节是别忘了排序结束后要释放动态内存
2.在归并函数内部，我们针对有序尾插步骤的时候，别忘了处理一个到边界另一个数据要把剩下的全插入到动态数组中的细节。
3.用memcpy函数时，传入数据的个数是right-end+1，别忘了加一，因为下标相减+1才是元素的个数
2.归并排序的非递归写法：
适用的情况和快速排序的非递归一个道理，我们要能在爆栈的时候及时利用迭代去修复处理问题。
具体的图解思路为：
代码如下：
void MergeSortNonR(int* arr1, int sz)//归并排序非递归写法 { int* tmp = (int*)malloc(sizeof(int) * sz);//首先定义一个数组用来存储数据 if (tmp== NULL) { perror("malloc fail"); exit(-1); } int gap = 1;//定义一个长度值，控制gap使其变成11归 22归 44归这样的扩大递归的形式 while(gap <sz) { for (int i = 0; i < sz; i += 2*gap) { int begin1 = i; int end1 = i + gap-1;//别忘了减一 int begin2 = i + gap; int end2 = i + 2 * gap-1;//别忘了减一 int newbegin = i; //如果第二组不存在，这一组就不用归并了 if (begin2 >= sz)//注意，等于sz也算越界，千万别忘了，而且注意这里为什么我只判断begin2就好了，因为begin2倘若越界了，则end2一定越界，而end1与begin2差一，假设begin2恰好等于sz，则此时的end1正好在最后一个位置，这个时候直接跳出，排序也已经完成了，故直接break是合理的。 { break; } //如果第二组右边界越界，修正一下即可 if (end2 >= sz) { end2 = sz - 1;//将end2修正到sz-1，让其与前面的数字归并排序，这样不会越界了 } while (begin1 <= end1 && begin2 <= end2)//对数据继续归并排序进入tmp数据组并且排好序放入 { if (arr1[begin1] < arr1[begin2]) { tmp[newbegin++] = arr1[begin1++]; } else //注意，这里不要光用if,因为光用if会导致一旦遇到重复情况，指针不会向后走，循环就会一直进行，这里是关于if语句的理解不到位，这里要注意，别弄错了 { tmp[newbegin++] = arr1[begin2++]; } } while (begin1 <= end1) { tmp[newbegin++] = arr1[begin1++]; } while (begin2 <= end2) { tmp[newbegin++] = arr1[begin2++]; } memcpy(arr1 + i,tmp +i,(end2-i+1)*sizeof(int));//注意这里的拷贝细节，由于begin1一直会变，但begin1的初始值是等于i的，故我们直接让其利用i来计数即可，比如这里,对于数据个数来说，就是从end2到i+1即为数据个数，两个数组的头从arr1+1和tmp+i开始即可。 }//注意，数组下标，左闭右闭形式，下标相减后要加一才是对应的元素个数 gap *= 2;//使递归开始11 22 44递归形式 } free(tmp); tmp = NULL; //但目前只能处理偶数个情况，对于奇数要设置特殊情况去判断 }
思路：
我前面说过，非递归本质上就是对递归的模拟，但这里面并没有直接套用模拟递归的方法，它使用的本质上是一种类似斐波那契数列的方法，由小到大去以偶数倍扩大自己能控制的范围直到gap的范围正好等于sz，其他的思想同归并递归写法差不多。
注意的细节：
1.由于我们一次扩大两倍，所以我们处理偶数倍数组确实很好处理，但对于奇数倍的处理却很麻烦，因为奇数倍的最后一组是不完全的，但我们按照偶数倍数的正常方法处理，所以就会产生越界的情况。
越界的情况可能的为：
begin1 end1 begin2 end2四个边界值越界，但begin1由于由i控制，故不会越界，故会越界的只有end1,begin2 end2,我们的归并排序不一定非要数据量相同时候排，也可以不相等的时候排序，这样我们就可以带着奇数剩下的尾部的数据去排列，故我们这样处理：
if (begin2 >= sz)//注意，等于sz也算越界，千万别忘了，而且注意这里为什么我只判断begin2就好了，因为begin2倘若越界了，则end2一定越界，而end1与begin2差一，假设begin2恰好等于sz，则此时的end1正好在最后一个位置，这个时候直接跳出，排序也已经完成了，故直接break是合理的。 { break; } //如果第二组右边界越界，修正一下即可 if (end2 >= sz) { end2 = sz - 1;//将end2修正到sz-1，让其与前面的数字归并排序，这样不会越界了 }
在对begin1 end1 begin2 end2进行完初始化后，我们就需要判断越界：
1.倘若begin2>=sz了，证明下一组的数据没法排了，故直接跳出来就好。
2，倘若end2>=sz了，说明这一组仍有三个数，这个时候不对称排序数据即可，将end2=sz-1再去排序即可。
2.我们拷贝数据，有人会问，直接2*gap不好么，为什么非要end2-i+1这样的方法去做呢？
由我们的第一问可以知道，有的时候数据不一定是2gap这么多，比如end2的尾部优化后就会出现数据量减少的情况，这个时候我们要是再2gap这种粗暴的无脑方法就会越界，故我们根据实际情况用end2-i+1处理即可。
memcpy(arr1 + i,tmp +i,(end2-i+1)*sizeof(int));
5.第四类排序：极致速度的整型数据类型的排序
1.计数排序（又叫鸽巢原理）时间复杂度O(MAX(N范围)) 空间复杂度O(范围）
代码如下：
void CountSort(int* arr1, int sz)//计数排序 { int max = arr1[0]; int min = arr1[0]; int i = 0; for (i = 0; i < sz; i++)//首先对数据进行最大值最小值的取得，从而确定相对映射的数值和开辟的动态数组的大小 { if (arr1[i] > max) { max = arr1[i]; } if (arr1[i] < min) { min = arr1[i]; } } int range = max - min + 1; int* count = (int*)calloc(sizeof(int), range);//动态开辟一段数组且初始化每一个元素为0，这里使用memmset也可以，但我这里使用了calloc直接开辟并初始化了。 if (count == NULL) { perror("calloc failed"); exit(-1); } for (i = 0; i < sz; i++) { count[arr1[i] - min]++; } int j = 0; for (i = 0; i < range; i++)//注意这里，别搞错了，用range大小开辟的数组当然要用range遍历，这个range和sz可是不相同的，别理解错了。 { while (count[i]--) { arr1[j++] = i + min; } } free(count); count = NULL; }
思路：
计数排序的思路就是，首先遍历一遍数组，找到最大值和最小值，然后以这俩个值为基准，首先创建一款动态的数组，大小range,range为max-min+1,也就是将最大值与最小值之间的所有数字每一个都看作一个元素，然后利用calloc将每一个元素的初始值设为0，然后再一次遍历数组，利用相对映射的方法，将每一个数组的元素与min相减得到一个相应下标，对这个下标的元素0加加，这样进行累计，遍历结束后，动态数组里面就存储着相对最小值的数据的相对值的下标位置及其个数，然后我们遍历动态数组，将每一个数据从下标为0的位置依次复原，将数据的原来值返回并且按照元素大小记录的个数依次存储，这样得到的就是一个有序的数组。
计数排序的优缺点：
计数排序的优点就是快，对于越集中的数据计数排序的排序速度越快，但排序数据只能是整型非常单一，而且它的快完全是利用空间换出来的快，空间开辟可能会过大
6.其他排序的方法：
1.基数排序：一位一位比较
2.桶排序
这两种在这里不过多赘述，因为不如前面的高级排序更好，更加适用
7.对排序的整体总结：
1.稳定性：
稳定性的概念是数据的相对位置的变动情况是否频繁，比如，在一个数组中，1 2 4 6 7 8 9 10 11 100，我们说9相当于2的位置是在2的后边，在排序的过程中，若9总是在2的后边，则我们说这种排序的稳定性是很好的。
2.排序方法一览：
稳定性是很有必要的，它在权重排序中的作用很大，比如同样是700分，但一个数学为145，一个为149，那么按照语文的稳定排序，149就可以稳定的在145前面。
而对于我们排序的稳定性，我们不要硬记，要想反例，这里我不过多赘述。
8.总结：
排序作为计算机管理数据最常用也是最关键的数据管理知识之一，其掌握用重大意义，希望各位可以认真学习这块的相关内容，争取做到“数据掌握易如反掌”！！！！
