前言：
数据是计算机程序永远绕不开的话题，任何程序往往都在做这几件事，存放数据，读取数据，利用数据，销毁数据。所以，怎样管理数据使其为我们所用是一个很关键的问题，而排序则是最直观也是最关键的管理数据的方式之一，对一组数据进行排序看似简单，但大规模的数据排序方法却不仅仅是实现的问题，它还要求内存空间运算速度等问题，所以接下来我将说一说排序的方法和一些思想。
1.排序的基本思想与要求：
对于排序，我们往往需要考察其这几个方面：
1.能否实现普遍性：即对于任意数据都能成功对齐进行数据的排序处理
2.运算的时间如何：当处理大数据的时候，使用某种排序方法是否能迅速将数据排好
3.对于空间的占用有多大：例如一些递归思想的排序，由于需要多层调用堆栈，因此需要开辟很大的空间，是否存在爆栈问题
4.（！！！！最为关键的一点）排序的稳定性如何，能否保证数据之间的相对顺序不会发生频繁的改变和调动
因此，从这几点出发，我们就需要明白我们接下来所说的每一种排序方法大致在哪个位置，长处和优势是什么，因为首先数据排序的方法无高低之分，排10个以内的数据使用冒泡排序可能优于使用快速排序等处理大数据的排序。
！！！排序方法无高低贵贱之分，术业有专攻，我们要根据实际情况灵活选择就好了！！！
2.第一类排序：小数据基本排序算法
1.冒泡排序 -----时间复杂度O（N^2) 空间复杂度O（1）
基本实现如下：
void swap(int* x, int* y)//交换函数 { int tmp = *x; *x = *y; *y = tmp; } void BubbleSort(int* arr1, int sz)//冒泡排序函数 { int j = 0; for (j = 0; j < sz; j++) { int flag = 0; int i = 0; for (i = 1; i < sz-j; i++)//这里别出错，是sz-j而不是，仅仅小于j,排好一个元素后还得排sz-1个，这个思路别错了 { if (arr1[i] <arr1[i -1]) { swap(&arr1[i], &arr1[i -1]); flag = 1; } } if (flag == 0) { break; } } }
说明：
冒泡排序太过简单，所以这里我简单强调几点：
1.我使用的是优化版本的冒泡排序，即当数据排序好之后就不用重复循环过程而是直接退出循环了，这里利用了指示变量flag，需要交换时flag变为1，否则就仍然为0不变，倘若不变证明数据已经排好了，故直接跳出循环即可。
2.注意控制边界，这取决于你时i+1还是i-1的问题，i+1注意控制尾部，i-1注意控制头部，我这里使用的就是控制i-1控制头部的方法
2.直接插入排序 -----时间复杂度O（N^2) 空间复杂度O（1）
基本实现如下：
void InsertSort(int*arr1,int sz)//直接插入排序函数 { int i = 0; for (i = 0; i < sz - 1; i++) { int end =i; int tmp = arr1[end + 1];//要存储即将插入的数据，否则会覆盖，就找不到这个数据了，所以在排列开始前要先把数据存储起来。 while (end >= 0) { if (tmp < arr1[end]) { arr1[end + 1] = arr1[end]; } else { break;//注意这里用break的细节，常规写一个arr1[end+1]=tmp即可，但是倘若是end减到-1的情况跳出循环了，其赋值方式与小于等于是相同的，所以我们不如直接跳出循环写在一起，这个思路很巧妙，要积累。 } end--;//别忘了单趟循环end要--，以保证比较是一直进行的 } arr1[end + 1] = tmp; } }
直接插入排序的算法：
先考虑单趟，控制下标为0到下标为end+1范围内的数组元素是有序的，其实现方法为：
从end的位置开始，令end+1位置的数组开始与end位置的数字开始比较，若相应数字大于arr1[end],则将其补在下标end位置元素的前面，反之，倘若相等或者相应数字小于，则将end位置的数据放到end+1 位置，为tmp腾出一个位置来存放数据，当end不断的自减去到-1的时候，自动跳出循环，此时直接给end+1赋值tmp即可，这便是单趟的思路。
多趟的思路，其实就是每次改变end的数值，以保证每次排序的范围扩大，从0开始到sz-2(注意，由于有end+1的存在，且数组最多到sz-1下标，故我们这里控制end最多到sz-2。 插入排序对于排列升序和降序道理相同
需要注意的细节：
**1.首先，这不仅仅是直接插入排序或者是冒泡排序的问题，几乎所有的排序都面临控制边界的问题，在直接插入排序也需要控制好边界，对于我这里+1的写法，就要控制其end最多不能超过sz-2,而且要强调，我们这里操作的是下标，而不是里面具体的元素，故我们一定要看好下标的边界在哪里。 **2.其次，搞清楚我们的直接插入的逻辑是什么，将一个元素放在当前数组的最后尾部向着头部比较前进，遇到合适的位置就插入进入，这个大思路别错，而且我们操纵的是下标，这个千万要记住别忘了！！！！** **3.掌握一种逻辑方法，即先单趟再多趟的思路，就是先搞清楚我们一次插入的过程是怎样实现的，然后套上一个循环就可以实现整个数据的整体排序了**
3.直接选择排序-----时间复杂度O（N^2) 空间复杂度O（1）
代码实现如下：
void SelectSort(int* arr1, int sz)//直接选择排序函数 //注意：！！！！！我们这里使用优化版本，即每次选出最大和最小的，最大的放在最右边，最小的放在最左边，然后调整数组的范围直到数组结束，但要注意，我们这里要找的是下标而不是里面的具体数值！！！！！ {//必须要强调：直接选择排序对应的不是内部的元素，而是其下标，这个一定要记住！！！！！！！ int i = 0; int left = 0; int right= sz - 1; while (left < right)//注意循环的条件 { int mini = left;//注意每次都要刷新mini和maxi的初始下标，防止数据被覆盖以及进一步缩小范围至[left+1,right] int maxi = right; for (i = left+1; i <=right; i++)//遍历的范围也在left到right范围内部，元素范围也从left+1的位置开始到right-1的范围内访问 { if (arr1[i] > arr1[maxi]) { maxi = i; } if (arr1[i] < arr1[mini]) { mini = i; } } swap(&arr1[left], &arr1[mini]);//注意要交换而不是赋值，这个不要想错了 if (left == maxi)//倘若为 9 1也就是最大值与left重叠，mini一旦与其交换，下一次maxi就会直接和right交换这样就出错了，所以一旦有这种情况，即left和maxi重叠的情况，则交换完之后，如果left==maxi，则把mini的下标赋给maxi，这样就避免了这种情况的出现 { maxi = mini; } swap(&arr1[right], &arr1[maxi]);//注意，两个swap谁在前面谁需要调整 left++; right--; } }
直接选择排序的大体是一种不断缩小范围的思路，即从两边向中间夹击。
具体思路：
首先定义一个left和一个end,他们负责控制我们能控制的数据的范围，从整个数组开始，每一次循环都各缩小一位查找的范围，在每一个范围里，我们遍历整个范围去寻找这个范围里面的最大值和最小值，然后将最小值放在最左边即left位置（当然我这里以升序为例子），最大值放在最右边即right位置，然后left++ right–结束一次循环，直到我们的left=right时证明范围已经缩小为0，范围内部没有数据了，这时我们的升序也已经排好了。这种缩小范围的思路有点类似二分查找的利用left和right的方法,但又没有使用递归的思路，这是我的理解，你也可以找到适合自己的理解方式
需要注意的细节：
1.！！进一步强调，我们这里操纵的是下标，而不是所谓的元素，在找最大值最小值的时候我们也是通过比较完下标对应的元素后利用maxi和mini来存储最大值和最小值的下标，后面我们的交换则是交换对应的元素，但注意此时的下标的指向是没变的！！
2.第一点强调的最后一句话很关键：交换的是元素，但对应下标的指向没有变，也就是说，不管maxi对应的元素交换与否，我们的maxi都指向一个位置，同理mini也是，这就会引发下面的一种情况：
倘若left位置是最大值9,同时maxi也指向那个位置，我们先交换最小值把left和mini指向的元素交换，但maxi指向的元素没变，那么下一步最大值maxi与right交换的时候，maxi存储的位置就不是最大值了，这不就乱了吗？
所以，在交换完left和mini后，我们需要判断一下，我们的left和maxi指向的位置是不是同一个，倘若不是就正常向下交换最大值即可，但倘若是，经过交换之后，我们的最大值实际上在最小值mini指向的元素位置上，故我们要把maxi=mini，保证maxi下一轮的交换对应的元素是最大值而不是其他值,这个判断不管是大的先交换还是小的先交换都需要，先交换的就需要判断。
那么以上就是最基本的三种排序方式，他们三个分别代表了三种思想：1.依次比较 2.插入 3.比大小交换 ，这三种方式也是后面处理的处理大数据数据排序的方法的基本思想
3.第二类排序：由基本排序衍生的下一类大数据处理排序：
1.堆排序-----时间复杂度 O(N*log(N)) 空间复杂度 O(1)
代码实现如下：
void AdjustDown(int* arr1, int sz, int parent)//向下调整函数 { int child = parent * 2 + 1;//向下调整要传父亲节点，求出子节点，这样直接就把堆给构建出来了 while (child < sz)//向下调整是循环，别忘了，这个向下调整写的还是不够好 { if (child + 1 < sz && arr1[child + 1] > arr1[child])//注意。向下调整传父亲节点，向上调整传孩子节点 { child++; } if (arr1[child] > arr1[parent]) { swap(&arr1[child], &arr1[parent]); parent = child; child = child * 2 + 1; } else { break; } } } void HeapSort(int* arr1, int sz)//堆排序函数,向下调整建堆法,升序向上建大堆 { int i = 0; for(i = (sz - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr1, sz, i); } int end = sz - 1; while (end > 0) { swap(&arr1[end], &arr1[0]);//别忘了先交换首尾元素，然后找到 AdjustDown(arr1, end, 0); end--; } }
基本思路：
堆排序在我们上一个专题文章：树形结构部分我进行了详细的讲解，故在这里我简单说一下，堆排序的基本思路就是升序建大堆，降序建小堆（具体的建堆方法比较这里不过多赘述，向下调整需要交换的次数更少故提倡向下调整建堆），收尾元素交换，访问权限减一后剩下的节点向下调整建堆，然后重复这个过程即可。
注意的细节：
1.堆排序的向下调整建堆也好，向上调整建堆也好，都要控制好边界（我这里使用的是向下调整建堆）。向上调整我不过多赘述了，向下调整注意好子节点的选取，选取的时候要注意这样一种情况：
左子节点已经为数组的边界了（我们的堆构建是基于数组实现的），倘若这个时候我们去访问右子节点就越界了，所以我们要进行判断，倘若右子节点已经越界了，则不用进行子节点选择了，直接把左子节点当成子节点和父亲节点比即可。
void AdjustDown(int* arr1, int sz, int parent)//向下调整函数 { int child = parent * 2 + 1;//向下调整要传父亲节点，求出子节点，这样直接就把堆给构建出来了 while (child < sz)//向下调整是循环，别忘了，这个向下调整写的还是不够好 { if (child + 1 < sz && arr1[child + 1] > arr1[child])//注意。向下调整传父亲节点，向上调整传孩子节点 { child++; } if (arr1[child] > arr1[parent]) { swap(&arr1[child], &arr1[parent]); parent = child; child = child * 2 + 1; } else { break; } } }
这里要强调的是：堆排序的思想本质可以说是由直接选择排序的思想衍生过来的，借助了二叉树的堆的结构实现的一个排序方法。
2.希尔排序 ----- 时间复杂度O(N^1.3) 空间复杂度O(1)
具体实现如下：
void ShellSort(int* arr1, int sz)//希尔排序函数，希尔排序算法的思路就是：对于数据首先进行一个预处理，将其通过不断削减gap的数值使其逐渐变得有规律，直到最后gap==1的时刻，成为了插入排序，但由于先前的排序铺垫，插入排序只需要调整微小的局部数据即可，故效率很高 { //先写常规写法：即分批次希尔排序法，也可以用并序希尔排序法 int gap = sz;//默认把gap数值从数组的长度开始分组，直到gap变成1 while (gap > 1) { gap =gap/ 3+1;//注意，这里的逻辑就是，每一次不断缩减gap的数值使其分组越来越细，当gap等于1时实际上即为插入排序的过程，得到的即为最后的排序，注意，gap过大时有时自己除自己不一定得到1，所以我们人为的补上一个1，保证其最后gap一定会等于1 //int j = 0; //for(j=0;j<gap;j++) //{ int i = 0;//上面的使用了j的是常规的希尔为分列希尔排序，下面我们采用并序希尔排序法，即从0到sz-gap进行插入排序 for (i = 0; i < sz - gap; i++)//这里便是一个常规的插入排序的过程，只不过插入的间隔是gap，如果是常规算法，这里就是i+=gap,反之连续希尔排序就是i++ { int end = i; int tmp = arr1[end + gap]; while (end >= 0) { if (tmp < arr1[end]) { arr1[end + gap] = arr1[end]; } else { break; } end -= gap; } arr1[end + gap] = tmp; } //} } }
基本思路：
希尔排序是以插入排序为基础发展的一种更为快速的排序方法，又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。用更为简洁的方法来解释就是：进行多组的插入排序，但间隔的值不是1了，而是从大的值开始，依次缩减，将数据不断进行预处理使其不断趋向于有序，然后直到最后一次这个间隔的值变为1的时候，即为插入排序的时候，将这个数据完全排为有序数组我们把这个间隔值称为gap,
如图，这就是希尔排序的图解思路。
希尔排序的方法有两种，分为单趟插入希尔排序法和同时插入希尔排序法，我上面采取的是同时插入希尔排序法。
1.单趟插入希尔排序法：
即一组一组排到边界值，直接把一组排好后再排下一组
具体的方法就是如上图：
2.同时插入希尔排序法：
即只利用一个循环，然后依照周期的规律依次各进行一次插入排序后向下进行再排一次以此类推直到周期的最后一组数据触碰到边界时结束，即为i<sz-gap为边界。
如下图所示：
单趟的代码如下：
void ShellSort(int* arr1, int sz)//希尔排序函数，希尔排序算法的思路就是：对于数据首先进行一个预处理，将其通过不断削减gap的数值使其逐渐变得有规律，直到最后gap==1的时刻，成为了插入排序，但由于先前的排序铺垫，插入排序只需要调整微小的局部数据即可，故效率很高 { //先写常规写法：即分批次希尔排序法，也可以用并序希尔排序法 int gap = sz;//默认把gap数值从数组的长度开始分组，直到gap变成1 while (gap > 1) { gap =gap/ 3+1;//注意，这里的逻辑就是，每一次不断缩减gap的数值使其分组越来越细，当gap等于1时实际上即为插入排序的过程，得到的即为最后的排序，注意，gap过大时有时自己除自己不一定得到1，所以我们人为的补上一个1，保证其最后gap一定会等于1 int j = 0; for(j=0;j<gap;j++) { int i = 0;//上面的使用了j的是常规的希尔为分列希尔排序，下面我们采用并序希尔排序法，即从0到sz-gap进行插入排序 for (i = j; i < sz - gap; i+=gap)//这里便是一个常规的插入排序的过程，只不过插入的间隔是gap，如果是常规算法，这里就是i+=gap,反之连续希尔排序就是i++ { int end = i; int tmp = arr1[end + gap]; while (end >= 0) { if (tmp < arr1[end]) { arr1[end + gap] = arr1[end]; } else { break; } end -= gap; } arr1[end + gap] = tmp; } } } }
对于希尔排序我的理解是：希尔排序的说白了就是1变成gap的多插入排序，且希尔排序最终会gap==1即变为插入排序，它比插入排序快就快在它利用了插入排序的优点并利用到了极致，插入排序的优点就是对于局部有序的数据，数据越有序插入越快，而利用gap又缩减了插入一次的次数，因此希尔排序可以说是一种即为精妙的排序方式。
注意一个细节：希尔排序的gap=gap/3+1,这一步为什么要加一呢？因为我们的gap有可能经过不断的除法处理，变得小于3了，这个时候再/3，会导致gap变成0，这样希尔就进行不下去了，故我们加一让其强制变为1的插入排序，这样就不会出错了。
4.第三类排序：大数据速度排序方法:
1.快速排序-----时间复杂度O(N*log(N)) 空间复杂度O(log(N))
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left <= 1) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div+1, right) QuickSort(array, div+1, right); }
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。也就是说：快速排序的核心就是找到核心的中间位置将其摆在正确的位置，然后递归下去，最终就会细分到两个数据的排序，回归后就会将整个数据排列出来
对于这个key数值的单趟寻找，我们有三种方法：
