1. 概述
排序概念：就是将一串记录按照其中某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：通俗的将就是数据元素不发生有间隔的交换，例如：
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能一次加载到内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
注意：以下的排序默认排升序。默认待排序列为：2，5，1，3，8，6，9，4，7，0，6
2. 插入排序
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
2.1 直接插入排序
1. 思想：
对于一个元素，将其与前面元素进行比较，将其插入到合适的位置。
排升序：将待排元素依次与序列中元素从右往左比，若待排元素小，则继续往前比，找到合适位置插入，原来元素的位置按顺序往后搬移。
2. 画图说明：
说明：第一个元素默认它有序，所以从第二个元素开始进行比较然后插入，5比2大，继续下一个，将1依次比较插入2前面，将3依次比较插入5前面，8比5大，不用管，继续下一个，将6依次比较插在8面，9比8大，不用管，将7依次比较，插在8前面，将0依次比较插在1前面，将6依次比较插在7前面，插入完成。
3.代码展示：
public class InsertSort { public static void insertSort(int[] array){ for(int i = 1;i < array.length;i++){ //让从1下标开始，因为如果只有一个元素，它自己默认有序 int key = array[i]; //从数组中的第二个元素开始比较，进行插入 int end = i-1; //end的位置是要插入元素的前一个位置 while(end >= 0 && key < array[end]){ //end不能越界，找待插入的位置，此处注意：key不能小于等于array[end]，否则为不稳定 array[end+1] = array[end]; end--; } array[end+1] = key; //找到位置进行插入，因为上面end--了，所以这里要插入的位置为end+1 } } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; insertSort(array); for(int i : array){ System.out.print(i+" "); } } }
结果：
4.特性总结：
时间复杂度：循环嵌套，O(N^2)，最优情况：当序列接近有序，插入的元素比较少，为O(N)
空间复杂度：不借助辅助空间，O(1)
稳定性：数据元素不发生有间隔的交换，稳定
应用场景：数据量小，接近有序
2.2 希尔排序（缩小增量排序）
1. 思想：
选一个整数为数据元素的间隔，将间隔相同的数据元素分为一组，分别对这些组进行插入排序，间隔减小，重复上述操作，当间隔减少到1的时候，数据元素即排好序了。
2. 画图说明：
说明：gap为间隔，这里依次将gap=4，2，1，先把间隔为4的数据元素用插入排序排好序，再利用插入排序排gap=2 的数据元素，依次重复上述操作，即可。
3. 代码展示：
public class ShellSort { public static void shellSort(int[] array){ int gap = array.length; while(gap > 1){ gap = gap/3+1; for(int i = gap;i < array.length;i++){ //跟插入排序一样，都从一组数的第二个元素开始，因为第一个数默认有序 int key = array[i]; int end = i - gap; //end的位置也是代排数的前一个，但这里间隔为gap，所以前一个位置为i-gap while(end >= 0 && key < array[end]){ //与插入排序保持不变,找待插入的位置 array[end+gap] = array[end]; // key小于前一个数，让end位置的元素往后移一位， end -= gap; //end每次向左走的时候一次走gap的间隔 } array[end+gap] = key; //找到待排位置将key插入相应位置 } } } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; shellSort(array); for(int i : array){ System.out.print(i+" "); } } }
结果：
4. 特性总结：
希尔排序是对直接插入排序的优化。
当gap>1时都是预排序，目的是让数组元素接近有序，当gap==1时，数组已经接近有序了，这样插入排序将会很快，整体而言，达到了优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。
gap的取法有多种，最初shell提出取gap=n/2，gap=gap/2，直到gap=1，后来，Kunth提出取gap = [gap/3]+1。在Kunth所著的《计算机程序设计技巧》第3卷中，利用大量的实验统计资料得出，当n很大时，关键码的平均比较次数和对象平均移动次数大约在n^1.25到1.6n^1.25范围内，这是利用直接插入排序作为子序列排序方法的情况下得到的。
故时间复杂度暂记为：O(N^1.25)~O(1.6N^1.25)
空间复杂度：没有借助辅助空间，O(1)
稳定性：数据元素发生了有间隔的交换，不稳定
应用场景：数据比较随机
3. 选择排序
每一次从待排数据元素中选出最小（最大）的元素，存放在序列的起始（末尾）位置，直到全部待排序的数据元素全部排完。
3.1 直接选择排序
1. 思想：
思路1：
找出序列中的最大的元素，若它不在序列的末尾，将它与末尾元素交换位置，依次循环。
思路2：
每次找元素的时候，找一个最大的和一个最小的，最大的和最后一个交换位置，最小的和第一个交换位置，依次循环
2. 画图说明：
思路1：
说明：先找到序列的最大元素与序列最后一个元素交换，序列的最后的位置朝前移一个，再找新序列的最大元素再与最后一个交换位置，依次循环。
思路2：
说明：这种方法是一次找两个元素，跟上面那种本质上一样，只是一次交换了两个元素，将最大的与最后一个交换，将最小的与第一个交换
3. 代码展示：
public class SelectSort { public static void selectSort1(int[] array){ int size = array.length; for(int i = 0;i < size-1;i++){ //选择的趟数，size-1是因为当选择到序列剩一个元素时就不用选了 int pos = 0; //pos标记最大元素的位置，刚开始是默认为第一个位置 for(int j = 1;j < size-i;j++){ //j=1是因为默认第一个元素的位置为最大元素的位置，所以从第二个元素的位置开始比较 //size-i是因为每趟选择完后，序列都要减少一个 if(array[j] > array[pos]){ pos = j; //找到最大元素位置，更新pos } } if(pos != size-i-1){ //如果最大元素的位置刚好是最后一个位置，则不需要交换，反之进行交换 swap(array,pos,size-i-1); } } } public static void selectSort2(int[] array){ int left = 0; //序列的左边界 int right = array.length-1; //序列的右边界 while(left < right){ //当序列中至少存在俩元素时 int minPos = left; //刚开始将最小元素的位置设定为序列的第一个位置 int maxPos = left; //刚开始将最大元素的位置也设定为序列的第一个位置 int index = left+1; //从序列的第二个元素开始找最大元素和最小元素的位置 //找最大元素和最小元素的位置 while(index <= right){ if(array[index] < array[minPos]){ minPos = index; } if(array[index] > array[maxPos]){ maxPos = index; } index++; } if(minPos != left){ //当最小的元素不在序列的最左端时交换位置 swap(array,minPos,left); } //这里我是先交换最小的元素，但是如果最大的元素在最左侧，那么会将maxPos位置的元素更新为最小的元素，导致后面 //交换最大元素的时候maxPos标记的元素不准确，所以下面将maxPos的位置更新了一下 //注意：如果是先交换最大的元素，则更新minPos的位置 if(maxPos == left){ maxPos = minPos; } // if(minPos == right){ // minPos = maxPos; // } if(maxPos != right){ //当最大元素不在序列的最右端时交换位置 swap(array,maxPos,right); } left++; //左边界+1 right--; //右边界-1 } } public static void swap(int[] array,int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } public static void main(String[] args) { int[] array = {9,5,1,3,8,6,2,4,7,6,0}; selectSort1(array); for(int i : array){ System.out.print(i+" "); } System.out.println(); selectSort2(array); for(int i : array){ System.out.print(i+" "); } } }
4：特性总结：
时间复杂度：找元素，交换元素是循环嵌套，O(N^2)
空间复杂度：没有借助辅助空间，O(1)
稳定性：数据元素存在有间隔的交换，不稳定
缺陷：找最大元素或者最小元素的时候重复比较
3.2 堆排序
1. 思想：
堆排序是利用堆积树（堆）这种数据结构设计的一种算法，它是选择排序的一种，它是通过堆来进行选择数据。
注意：排升序，建大根堆，排降序，建小根堆。
堆排序分为两部分：建堆，利用向下调整建堆，再利用堆删除的思想排序。
向下调整：
前提：要调整的节点的两个左右子树都已满足堆的特性
方法：建大堆，将根的元素与左右孩子较大的元素交换，建小堆，将根的元素与左右孩子较小的元素交换
堆删除思想：
将堆顶元素与最后一个元素交换位置
堆中有效元素减少一个
再对堆顶元素向下调整
2. 画图说明：
因为数据元素多，二叉树的图看着不太清晰，所以我用以下序列：0，5，3，4，1，2
建堆：
利用堆删除思想排序：
3. 代码展示：
public class HeapSort { //向下调整 public static void shiftDown(int[] array,int parent,int size){ int child = parent*2+1; //默认将左孩子设为parent的孩子，因为不知道右边孩子是否存在 while(child<size){ if(child+1<size && array[child+1]>array[child]){ //如果右孩子存在，比较哪个孩子值大 child += 1; //将child设为较大的孩子 } if(array[parent]<array[child]){ //如果parent小，将parent与child交换 swap(array,parent,child); parent = child; //更新parent child = parent*2+1; //更新child }else{ //如果已经满足堆特性则直接返回 return; } } } //堆排序 public static void heapSort(int[] array){ //建堆 int size = array.length; int lastLeaf = ((size-1)-1)/2; //找到倒数第一个非叶子节点 for(int root=lastLeaf;root>=0;root--){ //从该结点开始，依次向下调整直到根节点 shiftDown(array,root,size); } //利用堆删除思想排序,从最后一个元素开始与堆顶元素交换，然后对堆顶元素进行向下调整 int end = size-1; while(end>0){ swap(array,0,end); shiftDown(array,0,end); end--; } } public static void swap(int[] array,int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; heapSort(array); for(int i : array){ System.out.print(i+" "); } } }
结果：
4. 特性总结：
时间复杂度：n个元素进行比较，而且太向下调整，调整的深度为完全二叉树的深度，故时间复杂度为：O(NlogN),logN是log以2为底的N
空间复杂度：没有借助辅助空间，O(1)
稳定性：元素发生了有间隔的交换，不稳定
应用场景：求前k个最小或者最大，可以和其他排序结合起来增加效率
4. 交换排序
基本思想就是根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
4.1 冒泡排序
1. 思想：
依次将序列元素进行比较，若array[i]>array[i+1],交换两个元素的位置，直到最后一个元素，从中可以得出，每躺冒泡只能确定一个元素的位置，若序列有n个元素，则需要进行n-1躺冒泡，因为序列最后一个元素的位置不用确定。
从比较的次数可以看出：第一躺比较的次数为n-1，第二躺的比较次数为n-2.....即每趟冒泡比较的次数在递减，即比较次数是为n-1-i，i为冒泡的趟数。
2. 画图说明：
3. 冒泡排序的优化：
从上图可以看出第10躺冒泡没有进行，因为序列已经有序，即数据元素不在发生交换。
优化：在每趟进行的开始给一个标记isChage=false，如果该躺冒泡发生了元素交换，将isChange=true，在每趟冒泡完进行判断，如果是Change==false，即没有发生交换，说明序列已经有序，即不用在继续冒泡，直接返回即可。
4. 代码展示：
public class BubbleSort { public static void bubbleSort(int[] array){ int size = array.length; for(int i = 0;i < size-1;i++){ boolean isChange = false; //为了优化冒泡排序给的标记，当元素不发生交换的时候说明已经有序 for(int j = 0;j < size-1-i;j++){ if(array[j+1] < array[j]){ swap(array,j,j+1); isChange = true; } } if(isChange == false){ //如果元素不发生交换，直接返回 return; } } } public static void swap(int[] array,int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; bubbleSort(array); for(int i : array){ System.out.print(i+" "); } } }
结果：
5. 特性总结：
时间复杂度：冒泡的趟数，每趟的比较次数，O(N^2)
空间复杂度：不借助辅助空间，O(1)
稳定性：数据元素虽然发生了交换，但是没有间隔交换，稳定
4.2 快速排序
4.2.1. 思想
快速排序是Hoare提出的一种二叉树结构的交换排序方法。
基本思想为：任取待排元素序列中的某个元素作为基准值（这里我们取最右侧元素为基准值），按照该基准值将序列划分为两个区间，左侧比基准值小，右侧比基准值大，再分别用快速排序递归排左区间和右区间。
参考代码：
public static void quickSort(int[] array,int left,int right){ //左闭右开 if(right-left > 1){ //递归的返回条件，区间最少得有两个元素 int div = partition(array,left,right); quickSort(array,left,div); //递归排左侧 quickSort(array,div+1,right); //递归排右侧 } }
故只要实现分割方法即可。
4.2.2 三种分割方式
1. Hoare法
思想：在左边找比基准值大的，右边找比基准值小的，两个交换位置，最后将较大一侧的第一个元素与基准值交换位置。
画图说明：
参考代码：
//分割区间方法1：hoare：左边找比基准值大的，右边找比基准值小的，两个交换位置,最后再将基准值放到中间的位置 public static int partition1(int[] array,int left,int right){ int key = array[right-1]; //找基准值，以最右侧元素为基准值 int begin = left; //在左侧找的下标 int end = right-1; //在右侧找的下标 while(begin < end){ while(array[begin] <= key && begin < end){ //左侧找大的，不能越界 begin++; } while(array[end] >= key && end > begin){ //右侧找小的，不能越界 end--; } if(begin != end){ swap(array,begin,end); //begin与end不在同一位置的时候交换，否则没有交换的必要 } } if(begin != right-1){ swap(array,begin,right-1); //将基准值与begin位置的元素交换，begin或者end都行 } return end; //将分割的位置返回，begin与end都可以 }
2. 挖坑法
思想：将基准值存入key中，基准值的位置为第一个坑位，在左侧找比基准值大的，放到第一个坑位上，此时这个元素的原始位置又形成了一个新的坑位，再从右侧找比基准值小的，放到前面的坑位上，依次循环，即将序列分割为两部分。
画图说明：
参考代码：
//分割区间方法二：挖坑法：基准值是一个坑位，左侧找大的放到基准值的坑位上，此时形成了新的坑位，再在右侧找小的放到上一个坑位，依次循环 public static int partition2(int[] array,int left,int right){ int key = array[right-1]; //取最右侧元素为基准值，end的位置形成了第一个坑位 int begin = left; int end = right-1; while(begin < end){ while(begin < end && key >= array[begin]){ //在左侧找比基准值大的 begin++; } if(begin < end){ array[end] = array[begin]; //填end坑位，重新生成begin坑位 } while(begin < end && key <= array[end]){ //在右侧找比基准值小的 end--; } if(begin < end){ array[begin] = array[end]; //填begin坑位，重新生成end坑位 } } array[begin] = key; //将基准值填充在最后一个坑位 return end; }
3. 前后标记法
思想：给两个标记cur，pre，pre标记cur的前一个，cur开始标记第一个元素，依次往后走，cur小于区间的右边界，如果cur小于基准值并且++pre不等于cur交换cur与pre位置的元素，最后交换++pre与基准值位置的元素。
画图说明：
参考代码：
//分割区间方法三：前后标记法 public static int partition3(int[] array,int left,int right){ int key = array[right-1]; int cur = left; int pre = cur-1; while(cur < right){ if(array[cur] < key && ++pre != cur){ //当cur位置的元素小于基准值并且++pre！=cur的时候，交换 swap(array,cur,pre); } cur++; } if(++pre != right-1){ //++pre为与基准值交换的位置，所以当++pre！=right-1的时候，交换基准值的位置 swap(array,pre,right-1); } return pre; }
4.2.3 快速排序的优化
快速排序的优化：对基准值的选取进行优化，这样做是为了选取的基准值尽可能的将区间的左右侧分的均匀一点儿。
优化方法：三数取中法取基准值，三数：区间的中间元素，最左侧元素，最右侧元素，取它们三个的中间值。
参考代码：
//快排优化：三数取中法来取基准值，左侧，右侧，中间这三个数的中间值来作为基准值,这里返回的是基准值下标 public static int getIndexOfMid(int[] array,int left,int right){ int mid = left+((right-left)>>1); if(array[left] < array[right-1]){ //最右侧的下标为right-1 if(array[mid] < array[left]){ return left; }else if(array[mid] > array[right-1]){ return right-1; }else{ return mid; } }else{ if(array[mid] < array[right-1]){ return right-1; }else if(array[mid] > array[left]){ return left; }else{ return mid; } } } 具体与之前代码结合方式，我这里选取一种分割方法来进行优化： 参考代码： //分割区间方法三：前后标记法 public static int partition3(int[] array,int left,int right){ int index = getIndexOfMid(array,left,right); //用三数取中法获得基准值的下标 if(index != right-1){ swap(array,index,right-1); //如果下表不在最右侧就交换 } int key = array[right-1]; int cur = left; int pre = cur-1; while(cur < right){ if(array[cur] < key && ++pre != cur){ //当cur位置的元素小于基准值并且++pre！=cur的时候，交换 swap(array,cur,pre); } cur++; } if(++pre != right-1){ //++pre为与基准值交换的位置，所以当++pre！=right-1的时候，交换基准值的位置 swap(array,pre,right-1); } return pre; }
4.2.4 快速排序的非递归方式
非递归的快速排序借助栈这一数据结构
参考代码：
//非递归的快速排序，利用栈来保存分割的区间，传参只需要传数组即可 public static void quickSort(int[] array){ Stack<Integer> s = new Stack<>(); s.push(array.length); s.push(0); while(!s.empty()){ int left = s.pop(); int right = s.pop(); if(right - left == 0){ continue; } int div = partition(array,left,right); s.push(right); s.push(div+1); s.push(div); s.push(left); } }
4.2.5 快速排序的特性总结
时间复杂度：有比较，递归，O(NlogN)
空间复杂度：存在递归，递归的深度为完全二叉树的深度，O(logN)
稳定性：数据元素发生有间隔的交换，不稳定
应用场景：数据凌乱且随机
5. 归并排序
1. 思想：
归并排序是将两个有序序列进行合并，但是我们拿到是一个数组，所以得先将数组递归均分为两部分，再将两部分进行合并。
2. 画图说明：
递归均分：
从下往上合并：
3. 代码展示：
public class MergeSort { public static void mergeSort(int[] array,int left,int right,int[] temp){ if(right - left > 1){ int mid = left+((right-left)>>1); mergeSort(array,left,mid,temp); //递归均分左侧 mergeSort(array,mid,right,temp); //递归均分右侧 mergeData(array,left,mid,right,temp); //合并两个序列，[left,mid) , [mid,right) System.arraycopy(temp,left,array,left,right-left); //拷贝到原数组，源，起始位置，新，起始位置，长度 } } public static void mergeData(int[] array,int left,int mid,int right,int[] temp){ //[begin1,end1),[begin2,end2),为两个合并的区间 int begin1 = left; int end1 = mid; int begin2 = mid; int end2 = right; int index = left; //辅助数组的下标 while(begin1 < end1 && begin2 < end2){ if(array[begin1] <= array[begin2]){ temp[index++] = array[begin1++]; }else{ temp[index++] = array[begin2++]; } } while(begin1 < end1){ temp[index++] = array[begin1++]; } while(begin2 < end2){ temp[index++] = array[begin2++]; } } //重新包装一下，便于用户传参 public static void mergeSort(int[] array){ int[] temp = new int[array.length]; mergeSort(array,0,array.length,temp); } }
4. 非递归的归并排序
给一个间隔，用间隔来表示区间
参考代码：
//非递归的归并排序 public static void mergeSortNor(int[] array){ int size = array.length; int[] temp = new int[size]; int gap = 1; //先每两个元素归并 while(gap < size){ for(int i = 0;i < size;i+=gap*2){ int left = i; int mid = i+gap; int right = mid+gap; if(mid > size){ //防止mid越界 mid = size; } if(right > size){ //防止right越界 right = size; } mergeData(array,left,mid,right,temp); } System.arraycopy(temp,0,array,0,size); gap <<= 1; } }
5. 特性总结：
时间复杂度：O(NlogN)
空间复杂度：借助了辅助空间，为辅助数组的大小，O(N)
稳定性：数据元素不发生有间隔的交换，稳定
应用场景：适合外部排序
6. 计数排序（非比较类型的排序）
1. 思想：
计数排序又称鸽巢原理，是对哈希直接定址法的变形应用
步骤：
统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中
2. 画图说明：
3. 代码展示：
public class CountSort { public static void countSort(int[] array){ //找出数组的最大值与最小值 int maxNum = array[0]; int minNum = array[0]; for(int i = 1;i < array.length;i++){ if(array[i] > maxNum){ maxNum = array[i]; } if(array[i] < minNum){ minNum = array[i]; } } int range = maxNum - minNum + 1; //序列元素的范围大小 int[] count = new int[range]; //new一个范围大小的数组 for(int i = 0;i < array.length;i++){ count[array[i]-minNum]++; //读取 } int index = 0; //存入原数组的下标 for(int i = 0;i < range;i++){ while(count[i] > 0){ array[index] = i + minNum; index++; count[i]--; } } } }
4. 性能总结：
时间复杂度：O(N)
空间复杂度：O(M),M为数据范围的大小
稳定性：数据元素没有进行有间隔的交换，稳定
应用场景：数据元素集中在某个范围
7. 排序算法总结
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) | 不稳定 |
| 归并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 稳定 |
