一.插入排序
(一).直接插入排序
1.思路：
直接插入排序，先假定前end个是有序的，把第end+1个插入到前end个元素当中，插入完之后end++。那么怎么插入呢？当然是从后往前一个一个比的呀，判断这个数是否小于前面这end个，如果小于，就把前面的数挪到后一个,然后这个数比完了就end--；如果大于，就把这个数放到end+1的位置上。一个数就插完啦
2.代码：
public static void insertSort(int[] array) { for (int i = 0; i < array.length-1; i++) { int end = i; //因为end每次放完一个，要往后走所以要循环++ int tmp = array[end+1];//先将要比较的这个数字保存起来 while(end >= 0){ //如果end没走完队头就继续向前比 if(tmp<=array[end]){//如果tmp小，就把这个元素往后挪 array[end+1] = array[end]; end--; //然后继续向前比 }else{ break; //因为end可能是走到头了出循环，也可能 } //是tmp找到了自己的位置出循环，无论如何都要 } //放在end+1的位置上，所以直接break array[end+1] = tmp;//出了循环放tmp } }
3.时间复杂度
直接插入排序的时间复杂度是多少呢？
最坏的情况下：如果数组本身是逆序，你要排成升序，则次数为1+2+3+...+n-1=(n*(n-1))/2
所以时间复杂度为O(N2)
(二)希尔排序
1.思路：
希尔排序，是在直接插入排序基础上的优化。就是先进行分组直接插入排序（预排序），然后随着分组的越来越细，数组也越来越接近于有序。
多组间隔为gap的预排序，gap由大变小。gap越大，大的数越快的到后面，小的数越快的到前面。gap越大，排完越不接近于有序；gap越小，排完越接近于有序。当gap==1时，就变成了直接插入排序。
2.代码：
public static void shellSort(int[] array){ int gap = array.length; while(gap > 0){ gap/=2;//间隔每次/2 也可以gap=gap/3+1; //把间隔为gap的多组数据同时插入排序（把1换成gap） for (int i = 0; i < array.length - gap; i++) { int end = i; int tmp = array[end+gap]; while(end >= 0){ if(tmp < array[end]){ array[end+gap] = array[end]; end-=gap; }else{ break; } } array[end+gap] = tmp; } } }
3.时间复杂度
public static void shellSort(int[] array){ int gap = array.length; while(gap > 0){//这个循环的时间复杂度为logN 因为每次都除2 gap/=2; //如果gap特别大，此循环时间复杂度为O(N) //如果gap特别小，此时数组已经块接近有序了，所以时间复杂度还是O(N) for (int i = 0; i < array.length - gap; i++) { int end = i; int tmp = array[end+gap]; while(end >= 0){ if(tmp < array[end]){ array[end+gap] = array[end]; end-=gap; }else{ break; } } array[end+gap] = tmp; } } }
所以，时间复杂度为：O(N*logN) 或者 O(N*log3N)
平均的时间复杂度是O(N^1.3)
二.选择排序
(一).直接选择排序(优化版)
1.思路：
普通的直接选择排序是遍历一遍选出最大（小）的数放在最后（前）边，然后再遍历一遍，再选出次大的数，依次往下走...
优化版的的直接选择排序是遍历一次选出两个（一个最大值，一个最小值），然后begin++，end--
再次遍历选出次大，次小的数，依次往下走...
2.代码：
public static void selectSort(int[] array){ int begin = 0; int end = array.length - 1; while(begin < end){ int mini = begin; int maxi = begin; for (int i = begin; i <= end; i++) { if(array[i] < array[mini]){ mini = i; } if(array[i] > array[maxi]){ maxi = i; } } //交换最小值和begin，使得最小值在前 int tmp = array[mini]; array[mini] = array[begin]; array[begin] = tmp; if(maxi == begin){//如果刚刚被交换的begin刚好是最大值 maxi = mini; //那么需要调整一下 } //交换最大的和end，使得最大值在后 tmp = array[maxi]; array[maxi] = array[end]; array[end] = tmp; begin++; //找完一遍，begin++ end-- end--; } }
3.时间复杂度
N N-2 N-4 N-6...
所以，时间复杂度为：O(N^2)
由此可见，直接选择排序的效率最低
(二).堆排序
1.堆的铺垫
如图所示，堆的逻辑结构是一颗完全二叉树。堆的物理结构是一个数组。
通过下标访问父子关系的结点，下标关系如下：
leftchild = parent*2 + 1
rightchild = parent*2 + 2
parent = (child - 1) / 2
大堆要求：树中所有的父亲都大于等于孩子 ——>根是最大的
小队要求：树中所有的父亲都小于等于孩子 ——>根是最小的
2.向下调整算法（建小堆为例）
前提：如果小堆的向下调整算法，前提左右子树必须都是小堆才能使用—>最多调整高度次，
时间复杂度为O(logN)
思路：从根节点开始，选出左右孩子中小的那个，跟父亲比较，如果比父亲小就交换。然后在继续往下调，调到叶子结点或都比父亲大就终止
代码：
//向下调整算法 public static void adjustDown(int[] array ,int n ,int root){ int parent = root; int child = parent *2 + 1;//默认是左孩子小 while(child < n){ //选出左右孩子中小的那个 if(child+1 < n && array[child+1]<array[child]){ child++;//因为是连续空间，所以++child就为右孩子 } //孩子与父亲比较 if(array[child] < array[parent]){ //孩子小，交换父子值 int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; //此时的父亲向下走，孩子也跟着走 parent = child; child = parent *2 + 1; }else{ //孩子比父亲大，说明排完序了 break; } } }
3.建堆
思路：用向下调整算法就可以进行排序，但是如果左右子树不是小堆就不能用向下调整算法了。怎么办？
所以，我们想出了对策，倒着从最后一颗子树开始调（即根从下往上走），这样就可以保证，从下往上依次都是小堆。
再分析倒着走，叶子没有孩子不需要调，所以我们从最后一个非叶子子树开始调（即最后一个元素的父亲），下标为 (n-1-1) / 2，然后root依次变小
代码：
public static void heapSort(int[] array,int n){ //建堆 for (int i = (n-1-1)/2; i >= 0; i--) { adjustDown(array,n,i);//根从下往上走（变小） } }
时间复杂度：O(N)
建堆的时间复杂度(计算次数)计算是个很复杂的过程，要列出公式错位相减，
最后推出t(n)=N-logN , 所以其时间复杂度为O(N)
注：如果建大堆，就把向下调整算法中，选孩子中小的改为大的，然后孩子大于父亲才交换，就可以了。
4.排升序建大堆还是建小堆？
排升序要建大堆！！！！！
因为每次建大堆的根为最大的数，把他放到最后面，然后n--，把前n-1个数继续向下调整，找出次大的数，在把他放到倒数第二的位置上，以此类推...时间复杂度可以为O(N*logN)
如果要建小堆，那么你第一个根虽然是最小的，但是你除去第一个数，后面的n-1个数怎么找出最小的数呢？还是得重新建堆，那么时间复杂度就是O(N^2)了,效率很低
5.排升序整体代码
//向下调整算法 建大堆 public static void adjustDown(int[] array ,int n ,int root){ int parent = root; int child = parent *2 + 1;//默认是左孩子大 while(child < n){ //选出左右孩子中大的那个 if(child+1 < n && array[child+1]>array[child]){ child++;//因为是连续空间，所以++child就为右孩子 } //孩子与父亲比较 if(array[child] > array[parent]){ //孩子大，交换父子值 int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; //此时的父亲向下走，孩子也跟着走 parent = child; child = parent *2 + 1; }else{ //孩子比父亲小，说明排完序了 break; } } } public static void heapSort(int[] array,int n){ //建堆 for (int i = (n-1-1)/2; i >= 0; i--) { adjustDown(array,n,i); //先建一个大堆，选出最大的数 } int end = n - 1; //end表示进入下一次堆排序的元素个数，也表示最后的下标 while(end > 0){ int tmp = array[0];//先把最大的数挪到最后 array[0] = array[end]; array[end] = tmp; adjustDown(array,end,0);//再继续向下调整，元素个数为end个 --end; //进堆的个数-- } }
6.整体时间复杂度：
堆的时间复杂度主要是有两部分组成：初始化建堆（O(N)）+排序重建堆（N*O(logN)）
三.交换排序
(一).冒泡排序
1.思路：
冒泡排序的思路非常简单，就是从头把第i个数与第i+1个数比较，如果比他大就交换位置，然后i++。以此类推，就把最大的数放到了最后面。然后再继续从头一个一个比较，到倒数第二个数停，这时次大的数就被交换到这个位置了，依次类推...
2.代码：
public static void bubbleSort(int[] array){ for (int i = 0; i < array.length - 1; i++) {//冒泡排序的趟数 int exchange = 0;//作为某一趟是否交换的标志 for (int j = 0; j < array.length - 1 - i; j++) {//每趟要比较多少次 if(array[j] > array[j+1]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; exchange = 1; } } if(exchange == 0){//说明这一趟没交换 break; } } }
3.时间复杂度：
N-1 N-2 N-3 N-4 ...
所以时间复杂度为：O(N^2)
4.冒泡与直接插入排序相比谁更优？
先说结果，直接插入排序更强
他俩对于一般的都是O(N^2)，但是对于有序、接近有序或局部有序，插入排序的适应性更强
例：1 2 3 5 4 6
冒泡：N+1 + N+2 插入排序：N
(二).快速排序
单趟排序的不同方法
1.挖坑法
a.思路：
先拿一趟说思路，一个数怎么才能找到自己排完序时的位置呢？我们可以想到，当排完序时，一个数的左边都是比他小的数，右边都是比他大的数。所以我们可以让一个数的左边都是小于它的，右边都是大于它的，来找到它应该在的位置。那么应该怎样做到呢？我们可以先排第一个数，把第一个数设为key，此时这个位置就可以被覆盖，即挖了个坑。让end从右边往左找比他小的，找到了放到坑里，end作为新的坑。让begin从左边找比他大的，找到了放到右边的坑里，形成新的坑，以此类推下去...最终当begin==end时，此时的坑就是key应该在的位置，key就找到了自己的位置。
那么这是一个数找到了位置，我们怎么排下去呢？这就用到了分治算法（递归）。我们可以把key左边看成一段新的数组，右边看成一段新的数组。继续找新的key...直到不能再分下去为止...
如图所示：
（借用一张图）
b.代码：
public static void quickSort(int[] array,int left,int right){ if(left>=right){//如果只剩1个，就不用再分 return; } int begin = left; int end = right; int pivot = begin; int key = array[begin]; while(begin < end){//如果begin小于end才继续 //从右往左找比key小的 while(begin<end && array[end]>=key){//因为循环里面begin与end也会改变，所以需要再次判断 end--;//如果不比key小end就-- } array[pivot] = array[end];//比key小就放到坑里 pivot = end; //end形成新的坑 //从左往右找比key大的 while(begin<end && array[begin]<=key){ begin++; } array[pivot] = array[begin]; pivot = begin; } array[pivot] = key; //[left,right]——>[left,pivot-1] pivot [pivot+1,right] //所以递归下去 quickSort(array,left,pivot-1); quickSort(array,pivot+1,right); }
c.时间复杂度：
其单趟排序，虽然是两个while，但是只遍历一遍，所以是O(N)
那么快排要排几趟呢？最理想的情况下就是pivot每次都把数组二分
那么就需要logN次
所以，整体的时间复杂度是：O(N*logN)
d.快排什么情况下最坏？
答：有序的情况下。因为如果数组有序，那么快排每趟排序只将一个数与数组分离，只安排好了一个数。此时的时间复杂度为O(N^2)
e.三数取中
我们刚刚发现，如果快排的key总取最值的话，会使快排退化到O(N^2)，所以我们采取一种解决方式：三数取中
思路：我们让key等于下标为left，right和mid这三个数的中间值。这样可以保证key每次都取不到最值
f.优化快排
三数取中快排代码：
//三数取中 public static int getMid(int[] array,int left,int right){ int mid = (left + right)/2; if(array[left]>array[mid]){ if(array[right]>array[left]){ return left; }else if(array[mid]>array[right]){ return mid; }else{ return right; } }else{//array[left]<array[mid] if(array[mid]<array[right]){ return mid; }else if(array[left]>array[right]){ return left; }else{ return right; } } } public static void quickSort(int[] array,int left,int right){ if(left>=right){//如果只剩1个，就不用再分 return; } //得到中数下标 int mid = getMid(array,left,right); //交换一下第一个数和中间值，使得begin取的数是中间值 if(mid!=left) { int tmp = array[mid]; array[mid] = array[left]; array[left] = tmp; } int begin = left; int end = right; int pivot = begin; int key = array[begin]; while(begin < end){//如果begin小于end才继续 //从右往左找比key小的 while(begin<end && array[end]>=key){//因为循环里面begin与end也会改变，所以需要再次判断 end--;//如果不比key小end就-- } array[pivot] = array[end];//比key小就放到坑里 pivot = end; //end形成新的坑 //从左往右找比key大的 while(begin<end && array[begin]<=key){ begin++; } array[pivot] = array[begin]; pivot = begin; } array[pivot] = key; //[left,right]——>[left,pivot-1] pivot [pivot+1,right] //所以递归下去 quickSort(array,left,pivot-1); quickSort(array,pivot+1,right); }
g.小区间优化：
我们知道递归调用每次把数据分段，如果调到最后几层，会把1000000个数分成好多份，会产生大量的递归调用。我们主要的递归调用次数就是在最后几层。所以我们采用小区间优化的方法
思路：就是如果区间小于某一值我们就不用递归排序，而是选择直接插入排序排这几个数
代码：
鄙人还没有能力用Java写出小区间优化，所以只能用C顶一下(个_个)
2.左右指针法
a.思路：单趟排序的第二种方法，左右指针法。与挖坑法有一些相同之处，也是先定一个key，然后begin找大，end找小。只不过，当begin和end找到时直接把他俩交换。因为一开始begin这边就少一个数（key），根据一一对应的原则，当end与begin相遇时，这里的值一定小于key。所以直接把key与begin的值交换一下
b.代码：
//左右指针法 public static int partSort2(int[] array,int left,int right){ //得到中数下标 int mid = getMid(array,left,right); //交换一下第一个数和中间值，使得begin取的数是中间值 if(mid!=left) { int tmp = array[mid]; array[mid] = array[left]; array[left] = tmp; } int begin = left; int end = right; int keyi = begin; int key = array[begin]; while(begin<end){ //end找小 while(begin<end && array[end]>=key){ end--; } //begin找大 while(begin<end && array[begin]<=key){ begin++; } //左右一交换 int tmp = array[end]; array[end] = array[begin]; array[begin] = tmp; } //begin与keyi的值一交换 int tmp = array[begin]; array[begin] = array[keyi]; array[keyi] = tmp; return begin; } public static void quickSort(int[] array,int left,int right){ if(left>=right){//如果只剩1个，就不用再分 return; } int keyIndex = partSort2(array,left,right); //[left,right]——>[left,keyIndex-1] keyIndex [keyIndex+1,right] //所以递归下去 quickSort(array,left,keyIndex-1); quickSort(array,keyIndex+1,right); }
3.前后指针法
a.思路：同样的先定一个key。然后定义两个变量prev，cur做下标，cur从头开始找比key小的。在cur找的过程中，cur与prev中间间隔的数字就是比key大的。cur找到了，prev++，然后他俩交换。如果没找到cur就继续++。只到走到头，这时候prev的值是比key小的，所以把keyi与prev的值交换。
b.代码：
public static int partSort3(int[] array,int left,int right){ //得到中数下标 int mid = getMid(array,left,right); //交换一下第一个数和中间值，使得begin取的数是中间值 if(mid!=left) { int tmp = array[mid]; array[mid] = array[left]; array[left] = tmp; } int keyi = left; int prev = left; int cur = left+1; while(cur <= right){ if(array[cur]<array[keyi] && ++prev!=cur){//如果prev++之后还是cur int tmp = array[prev]; //++肯定要++，但是自己和自己交换没意义 array[prev] = array[cur]; array[cur] = tmp; } cur++; } int tmp = array[keyi]; array[keyi] = array[prev]; array[prev] = tmp; return prev; } public static void quickSort(int[] array,int left,int right){ if(left>=right){//如果只剩1个，就不用再分 return; } int keyIndex = partSort3(array,left,right); //[left,right]——>[left,keyIndex-1] keyIndex [keyIndex+1,right] //所以递归下去 quickSort(array,left,keyIndex-1); quickSort(array,keyIndex+1,right); }
四.归并排序
(一).归并排序
1.思路：
先假设一个前提，把一个数组分成两半区间，如果左半区间有序，右半区间有序。那么我们就可以采用归并算法，依次对比取小的放到新的临时数组中。然后再拷贝回来。
那么再归并之前，左右子区间没有序怎么办？那就先递归分到区间只剩一个元素的时候，再合并，在left和right新的数组下标内排序。最后一起拷贝到array中
逻辑类似于二叉树的后序
2.代码：
#include<stdlib.h> void _mergeSort(int* a, int left, int right, int* tmp) { if (left >= right) return; int mid = (left + right) >> 1;//相当于/2 //把数组二分进行递归 //把数组分为[left,mid]和[mid+1,right]两个区间 _mergeSort(a, left, mid, tmp); _mergeSort(a, mid + 1, right, tmp); //分好 进行归并 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; //一个个比较在tmp里排序 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //有一个走完，把另一个全部拷过去 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //所有数已经在tmp内排完啦，最后把tmp拷贝到a中 for (int i = left; i <= right; i++) { a[i] = tmp[i]; } } void mergeSort(int array[], int n) { int* tmp = (int*)malloc(sizeof(int) * n);//动态开辟一个数组，把数拷贝到这里交换 //因为如果在这个函数里递归，那么就会动态开辟很多个数组，所以要另一个子函数 _mergeSort(array, 0, n - 1, tmp);//把两个数组给它，还有数组的下标 free(tmp); }
3.对文件中的数据排序：
归并排序又叫外排序。可以对文件中的数据进行排序。因为文件中数据的读取不支持随机访问，所以别的排序失效。
问题：假设10G的数据放在硬盘的文件中，要排序，如何排呢？(可能内存不够，假设有1G内存可以用)
思路：把10G的文件切分成10个1G的文件，用归并排序把这些1G的文件排有序。最后再磁盘上将这些1G的文件进行归并
五.非递归的归并排序与快排
此内容有待开发...过段时间会补上的！！
六.计数排序
(一).计数排序
1.思路：
计数排序是一种非比较排序，顾名思义就是先malloc一块新的数组，然后每个数字对应一个位置，这个位置存放数字出现的次数，利用相对映射，再讲array中的数重新输入。
2.代码：
void countSort(int a[], int n) { int min = a[0]; int max = a[0]; for (int 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 //开始计数 for (int i = 0; i < n; i++) { count[a[i] - min]++;//相对映射 } //开始将计数转化成数 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } }
3.时间/空间复杂度：
时间复杂度：O(N+range) 说明它适用于集中一组整形数据排序
空间复杂度：O(range)
七.七大排序的总结对比
注：快排带有三数取中的时候最坏情况基本不会出现
稳定性： 如果你排序的数据中有相同的数字，当排完序之后这两个相同的数字相对顺序不会变，就是稳定的；否则就是不稳定的。（假设要求成绩相同时，先提交的在前，这时候就得用稳定的排序了）
