冒泡排序（Bubble Sort）： 对于一串数字，如3 2 5 9 6 4 1 从3的位置开始往后进行 如果被比较数比3小，那么那个数就“浮上去”，即与3进行交换，此时变成 2 3 5 9 6 4 1 再从第二个位置开始，即3和5比，顺序正常 第三个位置，5和9比，顺序正常 第四个位置，9和6比，6比9小，所以6“浮上去”，此时变成2 3 5 6 9 4 1 第五个位置，9和4比，4比9小，所以4“浮上去”，此时变成2 3 5 6 4 9 1 第六个位置，9和1比，变成2 3 5 6 4 1 9 这样结束了第一轮冒泡，能确定的是，数组最后一位已经被调成最大的数了 第二轮冒泡，继续从头开始遍历，但是这次到“1”的位置就可以了，因为最后一位已经确定，可以不用管它。至少可以确定，冒泡排序至多需要进行N轮，即数字总数 接下来的数字变化是： 2 3 5 4 6 1 9 2 3 5 4 1 6 9 第三轮： 2 3 4 5 1 6 9 2 3 4 1 5 6 9 第四轮： 2 3 1 4 5 6 9 第五轮： 2 1 3 4 5 6 9 第六轮： 1 2 3 4 5 6 9 第七轮： 1 2 3 4 5 6 9 如果将数字顺序变更为： 2 3 5 6 9 4 1 10 11 12，那么冒泡排序理论上需要进行10轮，但实际上到第七轮的时候顺序就已经是正确顺序了，后面三轮循环没有必要，因此可以直接退出循环，这就是冒泡排序的剪枝 时间复杂度： 最好情况，全是顺序，至少要全部遍历一遍。O（N） 最坏情况，全是倒序，(n-1) + (n-2) + … + 1 = n*(n-1) / 2 = O（N²）
void Bubble_Sort(int *A,int N){ for(int i = N-1; i >= 0; i--){ int flag = 1;//剪枝 for(int j = 0; j < i; j++){ if(A[j] > A[j+1]){ int temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; flag = 0; } } if(flag) break;//全程无交换BREAK; } }动画演示： 插入排序 用抽扑克牌举例子 先抽到一张J 再抽到一张K，K比J大，所以按顺序放在J的后面 又抽到一张A，A比K大，按顺序放在K的后面 抽到一张Q，Q比A、K都要小，所以放在K的前面，Q比J大，所以在J的后面 ↑这句话的操作应该是这样的：Q比A小，所以A把自己的位置挪出来，自己向右移动一个单位，Q放在A的前面（也就是腾出来的这个空位置）；Q比K小，K也把位置挪出来，自己向右移动，Q放在K的位置上；Q比J大，不需要挪动了，结束插入。 最好情况：抽到的牌都是顺序的，那至少还需要遍历一次，因此是O（N） 最坏情况：抽到的牌是倒序，为O（N²）
void Insertion_Sort(int *A,int N){ int i,j; for(i = 1; i < N; i++){ int temp = A[i];//取出数据（抽牌 for(j = i; j > 0 && A[j-1] > temp; j--){ A[j] = A[j-1];//向右移出空位 } A[j] = temp;//到达指定位置，放入数据 } }动画演示： 时间复杂度下界：
希尔排序 举例：81 94 11 96 12 35 17 95 28 58 41 75 15 先取出以5为间隔（中间隔了4个数字，下标差为5）的所有数： 第一组：81_ _ _ _ 35 _ _ _ _ 41 _ _ 插入排序 → 35_ _ _ _ 41 _ _ _ _ 81 _ _ 第二组：94 17 75 → 35 17 _ _ _ 41 75 _ _ _ 81 94 _ 第三组：11 95 15 →35 17 11 _ _ 41 75 15 _ _ 81 94 95 第四组：96 28 → 35 17 11 28 _ 41 75 15 96 _ 81 94 95 第五组： 12 58 → 35 17 11 28 12 41 75 15 96 58 81 94 95 以3间隔、1间隔的不多赘述
大致思想：给定一个乱序数组，每次选定一个间隔数X，从每X个取出数字并进行插入排序，结果子数组放回原来的位置上 再选定一个比X小的间隔数，做同样的动作，到最后间隔数选择1，进行插入排序，此时的序列逆序对已经非常少了，所以用插入排序会非常快捷 一般地，最初希尔增量序列X为size/2，随后的为X/=2,直到1，组成一个增量序列，这样的话它的时间复杂度为Θ（N²），这表示的是最坏情况，Θ表示上界=下界，恒定为N²的时间复杂度，下面举个例子： 这表示了前三次使用间隔数进行排序都是白费功夫，完全没必要做 因此最初希尔增量序列就不怎么起作用了，因此有人提出了更多的增量序列 代码实现：（普通希尔增量）
void Shell_Sort(int *A,int N){ int D,P,i,temp; for(D = N/2; D > 0; D/=2){//希尔增量序列 一直到1为止 for(P = D; P < N; P++){//插入排序 temp = A[P]; for(i = P; i >= D && A[i-D] > temp;i-=D){ A[i] = A[i-D];//向有跨度的右边移出空位 } A[i] = temp;//到达指定位置，放入数据 } } }选择排序 算法思路：从N组数据中找到最小的数，放到首项，再从除了首项的N-1组数据中找到最小的，放到第二位，以此类推。 代码实现：
void Selection_Sort(int *A,int N){ for(int i = 0; i < N; i++){ int MinPosition = FindMin(A,i,N); int temp = A[i]; A[i] = A[MinPosition]; A[MinPosition] = temp; } } int FindMin(int *A,int i,int N){ int min = INT_MAX,pos = i; for(i; i < N; i++){ if(A[i] <= min){ min = A[i]; pos = i; } } return pos; }对于FindMin()，每次执行时都需要O（N）复杂度进行查找，但是我们有更快的方法——用最小堆只需O（logN）
堆排序 堆排序就是优化后的插入排序，在插入排序中，每次都是寻找一个最小值放到数组前位，如果是使用堆的话，找到最小值放到数组前面这样对堆的结构会有一个比较大的影响，因此最好选择把最大值放到数组末尾，这样对于1~N-i 这样的堆依然能够较好的进行操作。 因此对于一个需要结果为递增数组的堆排序，选择使用最大堆的DeleteMax
思路以及疏忽点： 1.堆排序中的数组下标是从0开始，因此儿子节点的下标是2n+1和2n+2 2.结果为递增数组，选择最大堆；递减数组选择最小堆 3.基本思路（递增数组，size = N）：将A[0→N-1]构建最大堆，并将A[0]放到A[N-1]处，再将A[0→N-2]构建最大堆，将A[0]放到A[N-2]处，一直到N-i=0即完成堆排序 参考博客：
图解排序算法-堆排序 by dreamcatcher-cx
伪代码：
void Heap_Sort(int *A,int N){ for(int i = N/2 - 1; i >= 0; i--)//初始是10，父节点在4，可以画个二叉树就知道了(别忘了是从0开始 adjustHeap(A,i,N); for(int i = N-1; i > 0 ; i--){ int temp = A[i]; A[i] = A[0]; A[0] = temp; adjustHeap(A,0,i); } }这里再简要讲一下最大堆的调整： （最小堆同理）最大堆的定义是左右子树依然是最大堆，因此将原堆细分为多个小的最大堆组成最大堆 这里就是先从43-9调节，再是72-30-49，再是79-55-66，然后一层一层回溯进行堆的调整，这样组成最大堆，具体可以回顾我的博文树-堆，以及网上参考 最大堆by凌云壮志几多愁 结合上述代码，完整的堆排序代码如下：
void Heap_Sort(int *A,int N){ for(int i = N/2 - 1; i >= 0; i--)//初始是10，父节点在4，可以画个二叉树就知道了(别忘了是从0开始 adjustHeap(A,i,N); for(int i = N-1; i > 0 ; i--){ int temp = A[i]; A[i] = A[0]; A[0] = temp; adjustHeap(A,0,i); } } void adjustHeap(int *A,int pos,int N){//调整最大堆，从最后开始的每一个小堆（即非叶节点调整 int temp = A[pos]; for(int i = pos*2+1; i < N; i=i*2+1){//从小的堆一步一步向上调整，并一直往下寻找比它更大的 if(i+1 < N && A[i] < A[i+1]){//右子节点更大就选右子节点 i++; } if(A[i] > temp){//够大，放到父节点 A[pos] = A[i]; pos = i;//pos的位置变为子节点的位置 }else{ break; } } A[pos] = temp;//最后pos的位置是更新后的新子节点位置（若有） }归并排序 归并排序的核心就是有序数列的归并（合并），就类似最开始学链表的时候，要用两个有序链表合并成一个新的有序链表，这其中的思想的是一样的 Aptr比Bptr小，Aptr放入，A++，C++，然后再比较，再放入以此类推。 如果一个到头了，那么把另一个数组直接嚯的一声丢进去就好了——这是“并”的精髓
接下来就是要根据“并”来做下面的操作，把一串数组进行NNN次分割，出来2个非常非常小的数组进行合并。 当然最小情况就是2个数组，每个数组里面仅有1个元素（就1个元素肯定是有序的），给你一个4和3，怎么排你懂的吧.jpg，然后这一组的2个并完了，接下来就要并隔壁另外2个元素，这样我们就有了2个数组，这两个数组都是有序的，长度为2个数组，如：1，13；2，15.再像上面一样的方法把它并进去就是一个长度为4且有序的新数组了。 一层一层由“小”的“2组有序数组”，变成“大”的“2组有序数组”，最后合并在一起，这就是归并排序。 对归并排序的具体详解我之前也有写过博客-归并排序 欢迎阅读 代码实现：
void Merge(int *A,int *TempA,int L,int R,int Rightend){//合并精华部分 int Leftend = R-1;//1号数组结束的位置 int elenum = Rightend - L + 1;//此次数字总数（因为要从TempA中放回去 int tempos = L;//归并的起始位置（临时存放TempA的位置，这个位置需与A严格对齐 int i; while(L<=Leftend && R<=Rightend){ if(A[L] < A[R]){ TempA[tempos++] = A[L++]; }else TempA[tempos++] = A[R++]; } while(L<=Leftend){ TempA[tempos++] = A[L++]; } while(R<=Rightend){ TempA[tempos++] = A[R++]; } for(i = 0; i<elenum; i++,Rightend--){ A[Rightend] = TempA[Rightend]; } } void Msort(int *A,int *TempA,int L,int R){//分而治之精华部分 int center = (L+R)/2; if(L < R){ Msort(A,TempA,L,center);//向左分割 Msort(A,TempA,center+1,R); Merge(A,TempA,L,center+1,R);//数组1的起点为L，数组2的起点为center+1。极端情况L=center就是最左边2个数 开始归并 } } void Merge_Sort(int *A,int N){ int *TempA = new int[N];//先声明tempA,防止递归的时候重复声明数组导致浪费 Msort(A,TempA,0,N-1);//传进去的是数组最左和最右的下标 }表排序（大部分用作一种辅助工具） 待排元素不是单纯的整数，而是一个结构体 算法概述 ·间接排序 定义一个指针数组作为“表”（table） table数组里面最初标记的是A的下标 后来经过比较只改变table所指的位置 如table[0] = 3 就表示最小的是在A[3]处 因此如果仅要求按顺序输出，则输出：A[ table[0] ], A[ table[1] ], ……, A[ table[N-1] ]
如有需要，再将其进行物理排序 原理：N个数字的排列由若干个独立的环组成 如：table[0]的值是3，table[3]是1，table[1]是5，table[5]是0，回到table[0]组成一个环
这样就可以仅在每一个环内进行物理上的排序了，不需要换一个就要进行N次循环 用temp记录初值 ，每次换位子修改table值，用if ( table[i] == i )判断一个环的结束 然后其中的交换方式用插入排序也好其它的也好，都行
复杂度 最好情况：初始即有序 最坏情况： 有[N / 2]向下取整 个环，每个环包含2个元素 需要[N / 2]向下取整 次元素移动 T = O( m N ) ，m 是每个A元素的复制时间。
基数排序 桶排序 桶排序：假设我们有N 个学生，他们的成绩是0到100之间的整数（于是有M = 101 个不同的成绩值）。如何在线性时间内将学生按成绩排序？ 事实上就是开一个101的数组，数组下标作为一个指标 T(N, M) = O( M+N ) 当M>>N时，桶排序不合算，需要用到基数排序
假设我们有N = 10 个整数，每个整数的值在0到999之间（于是有M = 1000 个不同的值）。
输入序列: 64, 8, 216, 512, 27, 729, 0, 1, 343, 125 用“次位优先”（Least Significant Digit） 模拟（对于最多是三位数的数字来讲）： 1.开一个0~9的数组，然后将所有的数字，以它们的个位数为基准放入第一轮的桶中，pass 1中存储的就是一个链表，可能不够明显，见pass2 2.再开一个0~9的数组，再将所有的数字以它们的十位数为基准放入第二轮的桶中，如果前面没有那就是0.这样对于pass2，里面保存的的链表就是0→1→8→NULL 3.再开一个记录百位数，这样就保存完毕了。输出就从pass[i]，然后将里面的链表悉数输出即可。 设元素个数为N，整数进制为B，LSD的趟数为P，则最坏时间复杂度是：T=O(P(N+B))
多关键字的排序 一副扑克牌是按2种关键字排序的 如果按照花色排序，将卡片全都按花色放置后，还需要在其内部进行面值的排序，再并起来这样是一个完整的有顺序的手牌。这样实际上也就快了那么一点点。
用次位优先的方法，直接按照数字大小进行保存（也就是开13个桶），再从小到大，不需要排序，将这些牌直接按照花色放到新的“花色桶”中，再合并，这样也能得到一个完整的有顺序的手牌。速度相比主谓优先要快不少。
快速排序 是在现实生活中应用最广泛的排序算法 核心：分而治之、找主元（pivot） 算法思想：随便找一个主元65，然后将数组分成2组：比65小的，比65大的 然后对于左边和右边再用同样的方法递归实现：找一个主元，分成比这个主元小的一组和大的一组以此类推下去，最后结束就形成了一个有序数组。 具体描述： 1.选主元 取主元不能太小，也不能太大，最好是取中间的那个数，否则给一个序列1、2、3、4、5、6、7、8，每次都取第一个的话，时间复杂度是O（N²）太慢了。不同的pivot取法对运行速度影响各不相同。 一般地，我们主元可以取数组中头、中、尾的中位数。 顺便取完中位数后，最好对它们的位置进行一个交换，方便接下来的操作：比中位数小的在中位数的左边区域，比它大的在其右边区域 代码实现：
int GetMidNum(int *A,int left,int right){ int mid = (left+right)/2; if(A[left] > A[mid]){ Swap(A[left],A[mid]); } if(A[left] > A[right]){ Swap(A[left],A[right]); } //保证了左边的是最小的 if(A[mid] > A[right]){ Swap(A[mid],A[right]); } //顺序安排结束，left<=mid<=right Swap(A[mid],A[right-1]); //接下来的步骤是组成 小 mid 大 这样的数组 //把mid放到right-1的位置 //因为right已经肯定比mid要大了,省安排一个元素 return A[right-1]; } void Swap(int &a,int &b){ int temp = b; b = a; a = temp; }2.子集划分 准备工作完毕后，可以开始进行子集划分了，最终目标是实现 小 pivot 大 的数组序列 给定一串数组，这里的特征是最后一位是之前选取的pivot（因此这时候的传参是A，left（=0），right（N-1）） 从left和right-1位置开始设置一个i和j。 1.i=left ,a[i] = 8 > 6 讲道理i这边出现的应该都是比6要小的值，因此 i不动; 2.转向j, j = right -1.a[right] = 7 > 6正确，j向左移动 3.j = right - 2,a[j] = 2 < 6，出问题了，因此此时将a[i]和a[j]的数据进行对调，然后重新从i出发
4.i = left + 1 ,a[i] = 1 < 6 √；i++ 5. i = left + 2, a[i] = 4 < 6 √ i++ 6. i = left + 3, a[i] = 9 > 6 ×，转到j 7. j–, a[j] = 5 < 6 ×，此时j也是×，因此数据对调，再从i开始 8.a[i] = 0 < 6 √ ；–> i++ 9. a[i] = 3 < 6√ ；–> i++ 10.a[i] = 9 > 6 ×，转向j 11.j–,a[j] = 3 < 6 ×，此时i > j 那么将a[i]与a[right]换位，即完成划分。 这样的特点是，划分完元素之后，6所处的位置就是它在排序后的正确位置。
如果有元素正好等于pivot怎么办： 停下来交换：会产生很多不必要的交换。(一串相等的序列) 不理它，继续移动指针：pivot位置靠近一段，最糟糕会在最右边端，和pivot取A[0]一样，O( N^2 ) 综合考虑，选第一种，停下来交换。 小规模数据的处理 快速排序的问题 用递归，内存消耗大 对小规模的数据（例如N不到100）可能还不如插入排序快 解决方案 当递归的数据规模充分小，则停止递归，直接调用简单排序（例如插入排序） 在程序中定义一个Cutoff的阈值
代码实现：
void Quick_Sort(int *A,int N); void QSort(int *A,int left,int right); int GetMidNum(int *A,int left,int right); void Swap(int &a,int &b); void Quick_Sort(int *A,int N){ QSort(A,0,N-1); } void QSort(int *A,int left,int right){ // if(cutoff < len) if(left >= right) return; int pivot = GetMidNum(A,left,right); int i = left,j = right - 1; //right - 1 : pivot的位置 while(i<j){//出口就是i<j，while(1)稀烂 while(A[++i] < pivot){}//一直移动i while(A[--j] > pivot){}//i出问题了移动j if(i<j){ Swap(A[i],A[j]); } } Swap(A[i],A[right-1]);//pivot放到i处，形成小 pivot 大 QSort(A,left,i-1);//pivot在i的位置上，所以不能碰i QSort(A,i+1,right); //数据量太小： //if(cutoff > right-left) Insertion_Sort(A+left,right-left+1); } int GetMidNum(int *A,int left,int right){ int mid = (left+right)/2; if(A[left] > A[mid]){ Swap(A[left],A[mid]); } if(A[left] > A[right]){ Swap(A[left],A[right]); } //保证了左边的是最小的 if(A[mid] > A[right]){ Swap(A[mid],A[right]); } //顺序安排结束，left<=mid<=right Swap(A[mid],A[right-1]); //接下来的步骤是组成 小 mid 大 这样的数组 //把mid放到right-1的位置 //因为right已经肯定比mid要大了,省安排一个元素 return A[right-1]; } void Swap(int &a,int &b){ int temp = b; b = a; a = temp; }各种排序算法的比较 一些小注解：希尔排序中的d，最坏情况d=2，好情况1<d<2 堆排序看上去很美，但实际上它的O（NlogN）里的O常数比快排和归并都要大，因此相比这几个NlogN的要慢一些 快排的O常数是这几个中最小的，因此实际应用也最广
