目录
1.冒泡排序
1.1 冒泡排序思路：
通过相邻两个元素之间的比较和交换，使较大的元素逐渐从前面移向后面（升序），就像水底下的气泡一样逐渐向上冒泡，所以被称为“冒泡”排序。
算法步骤：
- 比较相邻元素，如果第一个比第二个大就交换；
- 对每一个相邻的元素进行同样的工作，从开始直到最后一对，通过比较最大的数据会跑到本次的最后位置；
- 针对所有的元素进行同样的操作；
- 直到没有任何一对数字需要比较时排序结束。
1.2 冒泡排序分析：
- 时间复杂度：若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成，时间复杂度依然为O(n)；若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。
所以，其时间复杂度依然为O(n^2)
- 空间复杂度：使用常数个辅助单元：O(1)
- 稳定性：由于i>jA[i] = A[j]时， 不会发生交换，因此冒泡排序是一种稳定的排序方法。
1.3 冒泡排序代码：
import?java.util.Arrays;
public?class?Code_BubbleSort?{
????//冒泡1
public?static?void?bubbleSort1(int[]?arr){
if(arr?==?null?||?arr.length?<?2){
return;
}
for(int?end=arr.length-1;?end>0;?end--){//每次选出最大的放到最后，重复；
for(int?i=0;?i<end;?i++){
if(arr[i]?>?arr[i+1]){
swap1(arr,?i,?i+1);
}
}
}
}
//交换函数--中间变量
public?static?void?swap1(int[]arr,?int?i,?int?j){
int?tmp;
tmp?=?arr[i];
arr[i]?=?arr[j];
arr[j]?=?tmp;
}
???//冒泡2
public?static?void?bubbleSort2(int[]?arr){
if(arr?==?null?||?arr.length?<?2){
return;
}
for(int?i=0;?i<arr.length-1;?i++){
?? for(int?j=0;?j<arr.length-i-1;?j++){
???????????????? if(arr[j]?>?arr[j+1]){
???????????????????? swap2(arr,?j,?j+1);
???????????????? }
???????????? }
???????? }
}
//交换函数--位运算
public?static?void?swap2(int[]?arr,?int?i,?int?j)?{
arr[i]?=?arr[i]?^?arr[j];
arr[j]?=?arr[i]?^?arr[j];
arr[i]?=?arr[i]?^?arr[j];
}
public?static?void?main(String[]?args){
int[]?arr1=new?int[]{40,3,50,500,9,0,60,70,50,51,81,1,5,8,100};
bubbleSort1(arr1);
System.out.println(Arrays.toString(arr1));
int[]?arr2=new?int[]{40,3,50,500,9,0,60,70,50,51,81,1,5,8,100};
bubbleSort2(arr2);
System.out.println(Arrays.toString(arr2));
}
}
2. 快速排序
2.1 快速排序思路
快速排序(Quick?Sort)?是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，速度较快，故称为“快速排序”。
快速排序的基本思想是：
- 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
- 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
- 对左右两个分区重复以上步骤直到所有元素都是有序的。
2.2 快速排序分析
- 平均时间复杂度:O(N*log(N))
- 最坏时间复杂度:O(N*N)：一般当数据有序或者局部有序的时候会出现这种坏的情况，比如数组正序或者逆序，（数字完全相同的时候也是有序的特殊情况）。
1：平均复杂度： t(n)?=?cn?+?2t(n/2) =?cn?+?2(cn/2?+?2t(n/4))?=?2cn?+?4t(n/4) =?2cn?+?4(cn/4?+?2t(n/8))?=?3cn?+?8t(n/8) =?icn?+?2^i?*?t(n/(2^i)) 当?2^i?=?n时,?i?=?logn,?排序结束， t(n)?=?cnlogn?+?n*t(1)?=?o(nlogn) 2：最坏复杂度： t(n)?=?cn?+?t(n-1)?=?cn?+?c(n-1)?+?t(n-2)?.... =?cnn?-ck?+?t(1)?=?cn^2?=?0(n^2)
- 空间复杂度:?O(log(N))
- 稳定性：不稳定排序，在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。例如，表L={3,2,2},经过一趟排序后L= {2,?2,3}， 最终排序序列也是L= {2,2,3}，显然，2与2的相对次序已发生了变化。
2.3 快速排序代码
代码1：
import?java.util.Arrays;
public?class?Code_QuickSort?{
public?static?void?quickSort(int[]?arr,int?L,int?R){
if(L<R){
swap(arr,L+(int)(Math.random()*(R-L+1)),R);
????????????????????//加上就是随机快排,?Math.random返回>=0，小于R-L+1的数
???
int?[]?p=?paration(arr,L,R);
quickSort(arr,L,p[0]-1);
quickSort(arr,p[0]+1,R);
}
}
public?static?int[]?paration(int[]?arr,int?L,int?R){
int?less=L-1;
int?more=R;
int?current=L;//current作为遍历数组的下标
while(current<more){
if(arr[current]<arr[R]){
swap(arr,++less,current++);
}
else?if(arr[current]==arr[R]){
current++;
}
else{
swap(arr,--more,current);
}
}
swap(arr,more,R);
return?new?int[]{less+1,more};
}
public?static?void?swap(int[]?arr,int?i,int?j){
int?tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
public?static?void?main(String[]?args){
int[]?arr=new?int[]{40,3,50,500,9,0,60,70,50,51,81,1,5,8,100};
System.out.println(Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
代码2：
import?java.util.Arrays;
public?class?Code_QuickSort?{
/**
?????*?快速排序算法
?????*/
????public?static?void?quickSort(int[]?list,?int?left,?int?right)?{
????????if?(left?<?right)?{
????????????//?分割数组，找到分割点
????????????int?point?=?partition(list,?left,?right);
????????????//?递归调用，对左子数组进行快速排序
????????????quickSort(list,?left,?point?-?1);
????????????//?递归调用，对右子数组进行快速排序
????????????quickSort(list,?point?+?1,?right);
????????}
????}
????/**
?????*?分割数组，找到分割点
?????*/
????public?static?int?partition(int[]?list,?int?left,?int?right)?{
????????//?用数组的第一个元素作为基准数
????????int?first?=?list[left];
????????while?(left?<?right)?{
????????????while?(left?<?right?&&?list[right]?>=?first)?{
????????????????right--;
????????????}
????????????swap(list,?left,?right);
????????????while?(left?<?right?&&?list[left]?<=?first)?{
????????????????left++;
????????????}
????????????swap(list,?left,?right);
????????}
????????//?返回分割点所在的位置
????????return?left;
????}
????/**
?????*?交换数组中两个位置的元素
?????*/
????public?static?void?swap(int[]?list,?int?left,?int?right)?{
????????int?temp;
????????if?(list?!=?null?&&?list.length?>?0)?{
????????????temp?=?list[left];
????????????list[left]?=?list[right];
????????????list[right]?=?temp;
????????}
????}
????
????public?static?void?main(String[]?args){
int[]?arr=new?int[]{40,3,50,500,9,0,60,70,50,51,81,1,5,8,100};
System.out.println(Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
代码3：
public?class?QuickSort?{
????public?static?void?main(String[]?args)?{
????????int?[]?a?=?{1,6,8,7,3,5,16,4,8,36,13,44};
????????QKSourt(a,0,a.length-1);
????????for?(int?i:a)?{
????????????System.out.print(i?+?"?");
????????}
????}
????private?static?void?QKSourt(int[]?a,?int?start,?int?end)?{
????????if?(a.length?<?0){
????????????return?;
????????}
????????if?(start?>=?end){
????????????return?;
????????}
????????int?left?=?start;
????????int?right?=?end;
????????int?temp?=?a[left];
????????while?(left?<?right){
????????????while?(left?<?right?&&?a[right]?>=?temp){
????????????????right?--?;
????????????}
????????????a[left]?=?a[right];
????????????while?(left?<?right?&&?a[left]?<=?temp){
????????????????left?++?;
????????????}
????????????a[right]?=?a[left];
????????}
????????a[left]?=?temp;
????????System.out.println(Arrays.toString(a));
????????QKSourt(a,?start,?left?-1);
????????QKSourt(a,left+1,end);
????}
}
3. 选择排序
3.1 选择排序思路
基本思想为每一趟从待排序的数据元素中选择 最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。
- 第1趟比较：拿第1个元素依次和它后面的每个元素进行比较，如果第1个元素大于后面某个元素，交换它们，经过第1趟比较，数组中最小的元素被选出，它被排在第一位；
- 第2趟比较：拿第2个元素依次和它后面的每个元素进行比较，如果第2个元素大于后面某个元素，交换它们，经过第2趟比较，数组中第2小的元素被选出，它被排在第二位；
- ......
- 第n-1趟比较：第n-1个元素和第n个元素作比较，如果第n-1个元素大于第n个元素，交换它们；
3.2 选择排序分析
- 时间复杂度：
在最好情况下也就是数组完全有序的时候，无需任何交换移动；
在最差情况下，也就是数组倒序的时候，交换次数为n-1次，时间复杂度为O(n^2)；
- 空间复杂度：
O(1)，只需要一个附加程序单元用于交换
- 稳定性：
选择排序是不稳定的排序算法，因为无法保证值相等的元素的相对位置不变，例如 [3, 4, 3, 1, 5]这个数组，第一次交换，第一个3和1交换位置，此时原来两个3的相对位置发生了变化。
3.3 选择排序代码
import?java.util.Arrays;
public?class?Code_SelectionSort?{
public?static?void?selectionSort(int[]?arr){
if(arr?==?null?||?arr.length<2){
return;
}
for(int?i=0;?i<arr.length-1;i++){
int?minIndex=i;???//最小值的下标
for(int?j=i+1;j<arr.length;j++){
minIndex=arr[j]<arr[minIndex]???j?:?minIndex;??//更新下标
}
swap(arr,i,minIndex);
}
}
//交换函数
public?static?void?swap(int[]?arr,int?i,int?j){
int?tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
public?static?void?main(String[]?args){
int?[]?arr=new?int[]?{1,22,4,6,11,0};
System.out.print("排序前：");
System.out.println(Arrays.toString(arr));
System.out.print("排序后：");
selectionSort(arr);
System.out.println(Arrays.toString(arr));
}
}
4. 堆排序
4.1 堆排序思路
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
- 每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；
- 每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。
步骤：
a.将无序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，
d.继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
将无序数组构造成一个大根堆（升序用大根堆，降序就用小根堆）
- heapInsert和heapify
大根堆最重要的两个操作就是heapInsert和heapify，前者是当一个元素加入到大根堆时应该自底向上与其父结点比较，若大于父结点则交换；后者是当堆中某个结点的数值发生变化时，应不断向下与其孩子结点中的最大值比较，若小于则交换。下面是对应的代码：
4.2 堆排序分析
4.3 堆排序代码
import?java.util.Arrays;
public?class?Code_HeapSort?{
//升序
public?static?void?heapSort(int[]?arr){
if(arr?==?null?||?arr.length<2){
return;
}
for(int?i=0;i<arr.length;i++){
heapInsert(arr,i);?//构造完全二叉树
}
int?size?=?arr.length-1;
while(size>0){
swap(arr,0,size--);
heapify(arr,0,size);//?最后一个数与根交换
}
}
//判断该结点与父结点的大小，大结点一直往，建立大根堆
public?static?void?heapInsert(int[]?arr,int?index){
while(arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
//一个值变小往下沉的过程
public?static?void?heapify(int[]?arr,int?index,int?size){
int?left=index*2+1;
while(left<size){
int?largest?=?left?+?1?<?size?&&?arr[left+1]?>?arr[left]???left+1?:?left;
largest?=?arr[largest]?>?arr[index]???largest?:?index;
if(largest==index){
break;
}
swap(arr,largest,index);
index=largest;
left=index*2?+1;
}
}
//交换函数
public?static?void?swap(int[]?arr,?int?i,?int?j){
int?tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
public?static?void?main(String[]?args){
int?[]?arr=new?int[]?{1,22,4,2,2,11,6,11,0,1000};
System.out.print("排序前：");
System.out.println(Arrays.toString(arr));
System.out.print("排序后：");
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
5. 直接插入排序
5.1 直接插入排序思路
直接插入排序算法是一个对少量元素进行排序的有效算法。插入排序的工作原理与打牌时整理手中的牌的做法类似，开始摸牌时，我们的左手是空的，接着一次从桌上摸起一张牌，并将它插入到左手的正确位置。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左进行比较，无论什么时候手中的牌都是排序好的。
例子：插入排序的过程可以联想到打扑克时揭一张牌然后将其到手中有序纸牌的合适位置上。比如我现在手上的牌是7、8、9、J、Q、K，这时揭了一张10，我需要将其依次与K、Q、J、9、8、7比较，当比到9时发现大于9，于是将其插入到9之后。对于一个无序序列，可以将其当做一摞待揭的牌，首先将首元素揭起来，因为揭之前手上无牌，因此此次揭牌无需比较，此后每揭一次牌都需要进行上述的插牌过程，当揭完之后，手上的握牌顺序就对应着该序列的有序形式
5.2 直接插入排序分析
5.3 直接插入排序代码
import?java.util.Arrays;
/*
?*?插入排序
?*?基本思想：摸扑克牌排序
?*/
public?class?Code_InsertionSort?{
public?static?void?insertionSort(int[]?arr)?{
if?(arr?==?null?||?arr.length?<?2)?{
return;
}
for?(int?i?=?1;?i?<?arr.length;?i++)?{//从下标为i=1的开始，也就是第二个元素开始
for?(int?j?=?i?-?1;?j?>=?0?&&?arr[j]?>?arr[j?+?1];?j--)?{//判断是否交换
swap(arr,?j,?j?+?1);
}
}
}
//交换函数
public?static?void?swap(int[]?arr,?int?i,?int?j)?{
arr[i]?=?arr[i]?^?arr[j];
arr[j]?=?arr[i]?^?arr[j];
arr[i]?=?arr[i]?^?arr[j];
}
public?static?void?main(String[]?args){
int[]?arr=new?int?[]?{1,23,2,6,8};
System.out.print("排序前：");
System.out.println(Arrays.toString(arr));
System.out.print("排序后：");
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}
6. 折半插入排序
6.1 折半插入排序思路
折半插入排序是直接插入排序与折半查找二者的结合，仍然是将待排序元素插入到前面的有序序列，插入方式也是由后往前插，只不过直接插入排序是边比较边移位。而折半插入排序则是先通过折半查找找到位置后再一并移位，最终将待排序元素赋值到空出位置。
前面提到过折半插入排序是对直接插入排序的优化，其实只是相对地使用折半查找比较次数变少了，每趟比较次数由o(n)变成了o(log2(n))。然而并没有真正改变其效率，时间复杂度依然是o(n*n)。在所有内排序算法中依然是平均效率比较低的一种排序算法。
区别：在插入到已排序的数据时采用来折半查找（二分查找），取已经排好序的数组的中间元素，与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于前半部分，否则属于后半部分，依次不断缩小范围，确定要插入的位置。
例子：int[] arr={5,2,6,0,9};经行折半插入排序
初始状态：设5为有序，其中i为1，即：5 2 0 6 9
第一趟排序：low为0，high为0，则中间值下标为0（（low+high）/2，下文都是如此计算），即5大于2，则插入到5前面，然后i自增。即：2 5 6 0 9
第二趟排序：low为0，high为1，则中间值下标为0，即2小于6，然后low等于中间值得下标加1，继续找中间值为5小于6，则插入到5后面，然后i自增。即：2 5 6 0 9
第三趟排序：low为0，high为2，则中间值下标为1，即5大于0，然后high等于中间值得下标减1，继续找中间值为2大于0，则插入到2前面，然后i自增。即：0 2 5 6 9
第四趟排序：low为0，high为3，则中间值下标为1，即2小于9，然后low等于中间值得下标加上1，继续找中间值为5小于9，然后low等于中间值得下标加上1，继续找中间值为6小于9，则插入到6后面，然后i自增，即：0 2 5 6 9
最终的答案为：0 2 5 6 9
6.2 折半插入排序分析
- 折半插入，适用于记录较多的场景，但是记录的移动次数和直接插入排序一样，故时间复杂度一样。最好是O(n)，最差是 O(n2)，平均是 O(n2)。空间复杂度是 O(1)。
- 特点：折半插入排序的比较次数和初始的序列无关，因为折半的次数一定，折一次比较一次。和直接插入比较，仅减少了比较次数，移动次数不变。
- 折半插入排序是稳定排序;
6.3 折半插入排序代码
import?java.util.*;
public?class?Code_BinaryInsertionSort?{
public?static?void?BinaryInsertionSort(int[]?arr)?{
int?n=arr.length;
????????int?i,j;
????????for?(i=1;i<n;i++){
????????????int?temp=arr[i];
????????????int?low=0;
????????????int?high=i-1;
????????????while?(low<=high){
????????????????int?mid=low+(high-low)/2;
????????????????if(temp>arr[mid]){
????????????????????low=mid+1;
????????????????}else?if(temp<arr[mid]){
????????????????????high=mid-1;
????????????????}
????????????}
????????????for?(j=i-1;j>=low;j--){
????????????????arr[j+1]=arr[j];
????????????}
????????????arr[low]=temp;
????????????//打印每次循环的结果
????????????//System.out.print("第"+i+"次：");
????????????//System.out.println(Arrays.toString(arr));
????????}???
????}
public?static?void?main(String[]?args){
int[]?arr=new?int?[]?{1,23,2,6,8,100,25,45};
System.out.println("排序前：");
System.out.println(Arrays.toString(arr));
System.out.println("排序后：");
BinaryInsertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}
7. 希尔排序
7.1 希尔排序思路
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
希尔排序的步骤：
- 首先根据初始序列的长度，选定一个递减增量序列t1，t2，t3......tk，其中ti>tj，tk = 1。
- 根据选定的增量序列元素个数k，对初始序列进行k趟排序。
- 根据增量序列的值ti，每趟排序会把初始序列划分成若干个元素的子序列，然后对这些子序列使用插入排序，因为这是递减增量序列，所以第一趟的排序，增量值最大，那么划分的子序列数量也就最多，每个子序列的元素也就越少，可以看做是一个“几乎”已经排好序的序列，当增量值越来越小的时候，子序列数量也就越少，每个子序列的元素也就越多，但是，基于前几次的排序，这些子序列虽然元素多，但是已经是一个“几乎”排好序的序列了，当最后一次排序的时候，即增量序列的值为1时，就是对整个无序序列进行排序，这时整个序列已经是一个“几乎”排好序的序列了。
7.2 希尔排序分析
7.3 希尔排序代码
import?java.util.Arrays;
public?class?Code_ShellSort?{
public?static?void?ShellSort(int[]?arr)?{
????????//?i表示希尔排序中的第n/2+1个元素（或者n/4+1）
????????//?j表示希尔排序中从0到n/2的元素（n/4）
????????//?r表示希尔排序中n/2+1或者n/4+1的值
????????int?i,?j,?r,?tmp;
????????//?划组排序
????????for(r?=?arr.length?/?2;?r?>=?1;?r?=?r?/?2)?{
????????????for(i?=?r;?i?<?arr.length;?i++)?{
????????????????tmp?=?arr[i];
????????????????j?=?i?-?r;
????????????????//?一轮排序
????????????????while(j?>=?0?&&?tmp?<?arr[j])?{
????????????????????arr[j+r]?=?arr[j];
????????????????????j?-=?r;
????????????????}
????????????????arr[j+r]?=?tmp;
????????????}
????????}
????}
public?static?void?main(String[]?args){
int[]?arr=new?int?[]?{1,23,2,6,8,100,25,45};
System.out.println("排序前：");
System.out.println(Arrays.toString(arr));
System.out.println("排序后：");
ShellSort(arr);
System.out.println(Arrays.toString(arr));
}
}
8. 归并排序
8.1 归并排序思路
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
归并排序的核心思想是先让序列的左半部分有序、再让序列的右半部分有序，最后从两个子序列（左右两半）从头开始逐次比较，往辅助序列中填较小的数。
例子2：
8.2 归并排序分析
- 归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。
- 从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
- 空间复杂度：O(n)
8.3 归并排序代码
import?java.util.Arrays;
public?class?Code_MergeSort?{
public?static?void?mergeSort(int?[]?arr){
if(arr==null?||?arr.length<2){
return;
}
mergeSort(arr,0,arr.length-1);
}
public?static?void?mergeSort(int[]?arr,int?l,int?r){
if(l==r){
return;
}
int?mid?=?l+((r-l)>>1);?//中点位置，即(l+r)/2
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}
public?static?void?merge(int[]?arr,int?l,int?mid,int?r){
int?[]?help=?new?int[r-l+1]; //辅助数组
int?i=0;
int?p1=l;?//左半数组的下标
int?p2=mid+1;?//右半数组的下标
//判断是否越界
while(p1<=mid?&&?p2<=r){
help[i++]=arr[p1]<arr[p2]???arr[p1++]?:?arr[p2++];
}
//p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
while(p1<=mid){
help[i++]=arr[p1++];
}
//p2没有越界，说明p1越界了
while(p2<=r){
help[i++]=arr[p2++];
}
//将辅助数组元素拷贝会原数组
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
}
public?static?void?main(String[]?args){
int[]?arr?=?new?int[]{10,1,25,100,95,15,45};
System.out.print("排序前：");
System.out.println(Arrays.toString(arr));
System.out.print("排序后：");
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
}
9. 基数排序
9.1 基数排序思路
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
算法步骤：
- 首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶中（注意：个位数值与桶号一一对应）
- 分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到仍然无序的数据序列；
- 接着，再进行一次分配，这次根据十位数值来分配（原理同上）
9.2 基数排序分析
9.3 基数排序代码
import?java.util.*;
public?class?Code_RadixSort?{
public?static?void?main(String[]?args)?{
????????int[]?arr?=?{63,?157,?189,?51,?101,?47,?141,?121,?157,?156,194,?117,?98,?139,?67,?133,?181,?12,?28,?0,?109};
????????System.out.print("排序前：");
????????System.out.println(Arrays.toString(arr));
????????System.out.print("排序后：");
???????radixSort(arr);
???????System.out.println(Arrays.toString(arr));
????}
????/**
?????*?高位优先法
?????*?@param?arr?待排序列，必须为自然数
?????*/
????private?static?void?radixSort(int[]?arr)?{
????????//待排序列最大值
????????int?max?=?arr[0];
????????int?exp;//指数
????????//计算最大值
????????for?(int?anArr?:?arr)?{
????????????if?(anArr?>?max)?{
????????????????max?=?anArr;
????????????}
????????}
????????//从个位开始，对数组进行排序
????????for?(exp?=?1;?max?/?exp?>?0;?exp?*=?10)?{
????????????//存储待排元素的临时数组
????????????int[]?temp?=?new?int[arr.length];
????????????//分桶个数
????????????int[]?buckets?=?new?int[10];
????????????//将数据出现的次数存储在buckets中
????????????for?(int?value?:?arr)?{
????????????????//(value?/?exp)?%?10?:value的最底位(个位)
????????????????buckets[(value?/?exp)?%?10]++;
????????????}
????????????//更改buckets[i]，
????????????for?(int?i?=?1;?i?<?10;?i++)?{
????????????????buckets[i]?+=?buckets[i?-?1];
????????????}
????????????//将数据存储到临时数组temp中
????????????for?(int?i?=?arr.length?-?1;?i?>=?0;?i--)?{
????????????????temp[buckets[(arr[i]?/?exp)?%?10]?-?1]?=?arr[i];
????????????????buckets[(arr[i]?/?exp)?%?10]--;
????????????}
????????????//将有序元素temp赋给arr
????????????System.arraycopy(temp,?0,?arr,?0,?arr.length);
????????}
????}
}
10. 桶排序
10.1 桶排序思路
桶排序的基本思想是将一个数据表分割成许多buckets，然后每个bucket各自排序，或用不同的排序算法，或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。它是一个分布式的排序，介于MSD基数排序和LSD基数排序之间。
基本流程
- 建立一堆buckets；
- 遍历原始数组，并将数据放入到各自的buckets当中；
- 对非空的buckets进行排序；
- 按照顺序遍历这些buckets并放回到原始数组中即可构成排序后的数组。
划分多个范围相同的区间，每个子区间自排序，最后合并。
10.2 桶排序分析
时间复杂度O(N)，额外空间复杂度O(N)，稳定
桶排序不是基于比较的排序，与被排序的样本的实际数据状况有关，所以实际中并不经常使用，桶排序是一个大的逻辑概念，桶可以是很多东西，如双向链表，数组等
桶排序有两个体现：
- 计数排序：如以词汇出现频率排序的词频排序
- 基数排序：改进了计数排序，以数的区域划分桶的接收范围
10.3 桶排序代码
import?java.util.*;
public?class?Code_BucketSort?{
public?static?void?bucketSort(int[]?arr){
????
????//?计算最大值与最小值
????int?max?=?Integer.MIN_VALUE;
????int?min?=?Integer.MAX_VALUE;
????for(int?i?=?0;?i?<?arr.length;?i++){
????????max?=?Math.max(max,?arr[i]);
????????min?=?Math.min(min,?arr[i]);
????}
????
????//?计算桶的数量
????int?bucketNum?=?(max?-?min)?/?arr.length?+?1;
????ArrayList<ArrayList<Integer>>?bucketArr?=?new?ArrayList<>(bucketNum);
????for(int?i?=?0;?i?<?bucketNum;?i++){
????????bucketArr.add(new?ArrayList<Integer>());
????}
????
????//?将每个元素放入桶
????for(int?i?=?0;?i?<?arr.length;?i++){
????????int?num?=?(arr[i]?-?min)?/?(arr.length);
????????bucketArr.get(num).add(arr[i]);
????}
????
????//?对每个桶进行排序
????for(int?i?=?0;?i?<?bucketArr.size();?i++){
????????Collections.sort(bucketArr.get(i));
????}
????
????//?将桶中的元素赋值到原序列
int?index?=?0;
for(int?i?=?0;?i?<?bucketArr.size();?i++){
for(int?j?=?0;?j?<?bucketArr.get(i).size();?j++){
arr[index++]?=?bucketArr.get(i).get(j);
}
}??
}
public?static?void?main(String[]?args){
int[]?arr?=?new?int[]{10,1,25,100,95,15,45};
System.out.print("排序前：");
System.out.println(Arrays.toString(arr));
System.out.print("排序后：");
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
}
11. 计数排序
11.1 计数排序思路
计数排序不是一个比较排序算法，该算法于1954年由 Harold H. Seward提出，通过计数将时间复杂度降到了O(N)。根据获得的数据表的范围，分割成不同的buckets，然后直接统计数据在buckets上的频次，然后顺序遍历buckets就可以得到已经排好序的数据表。
计数排序算法步骤：
- 找出原数组中元素值最大的，记为max。
- 创建一个新数组count，其长度是max加1，其元素默认值都为0。
- 遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
- 创建结果数组result，起始索引index。
- 遍历count数组，找出其中元素值>0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值<=0，依次处理count中剩下的元素。
- 返回结果数组result。
11.2?计数排序分析
- 时间复杂度为O(n)。
- 稳定排序。
可以将排序算法的时间复杂度降低到O(N)，但是有两个前提需要满足：一是需要排序的元素必须是整数，二是排序元素的取值要在一定范围内，并且比较集中。只有这两个条件都满足，才能最大程度发挥计数排序的优势。
11.3 计数排序代码
import?java.util.Arrays;
public?class?Code_CountSort?{
public?static?void?main(String[]?args){
int?[]?arr=new?int[]?{10,23,1,5,2,0,1};
System.out.print(Arrays.toString(arr));
System.out.println();
countSort(arr);
System.out.print(Arrays.toString(arr));
}
public?static?void?countSort(int[]?arr){
if(arr?==?null?||?arr.length<2){
return;
}
int?max?=?Integer.MIN_VALUE;???//最小的整数
for(int?i=0;?i<arr.length;?i++){
max=Math.max(max,?arr[i]);
}
int?[]?bucket=new?int[max+1];//桶的下标代表数组中数值的大小，所以桶的长度要为数组中的最大值
for(int?i=0;i<arr.length;i++){
bucket[arr[i]]++;//记数排序，相同值出现的次数
}
int?i=0;
for(int?j=0;j<bucket.length;j++){?//将排好的数存会原数组
while(bucket[j]-->0){
arr[i++]=j;
}
}
}
}
12. 比较?器
方法1： 使用lambda表达式
Collections.sort(List,?(a,b)?->?x1?-?x2);
方法2： 自定义Comparator方法
Collections.sort(List,?new?Comparator<E>(){
????public?int?compare(int?a,?int?b){
??????return?a?-?b;
????}
});
public?static?class?IdAscendingComparator?implents?Comparator<Student>?{
????
????@Override
????public?int?compare(Student?o1,?Student?o2)?{
????????//?返回负值o1排前面，返回正值o2排前面
????????return?o1.id?-?o2.id;
????}
????
}
Arrays.sort(students,?new?IdAscendingComparator());
优先级队列：小根堆
PriorityQueue<Integer>?queue=new?PriorityQueue<>(new?Comparator<Integer>(){
????????public?int?compare(Integer?a,Integer?b){
????????????return?a.compareTo(b);
????????}
????});
//??PriorityQueue<Integer>?queue?=?new?PriorityQueue();
最小k个数：大根堆
PriorityQueue<Integer>?maxHeap=new?PriorityQueue<Integer> (k,new?Comparator<Integer>(){
????????@Override
????????public?int?compare(Integer?o1,Integer?o2){
????????????????return?o2.compareTo(o1);
????????????}
????????});
PriorityQueue<Integer>?maxHeap=new?PriorityQueue<Integer>(k,(a,b)->b.compareTo(a));?
13. 总结及应用
实际工程中的排序算法一般会将?归并排序、插入排序、快速排序综合起来，集大家之所长来应对不同的场景要求：
- 当要排序的元素为基本数据类型且元素个数较少时，直接使用?插入排序。因为在样本规模较小时（比如60），O(NlogN)的优势并不明显甚至不及O(N^2)，而在O(N^2)的算法中，插入排序的常数时间操作最少。
- 当要排序的元素为对象数据类型（包含若干字段），为保证稳定性将采用?归并排序。
- 当要排序的元素为基本数据类型且样本规模较大时，将采用?快速排序。
13.1 荷兰国旗问题：快速排序
问题：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
//利用快速排序的思想；
思路：利用两个指针L、R，将L指向首元素之前，将R指向尾元素之后。从头遍历序列，将当前遍历元素与num比较，若<num，则将其与L的右一个元素交换位置并遍历下一个元素、右移L；若=num则直接遍历下一个元素；若>num则将其和R的左一个元素交换位置，并重新判断当前位置元素与num的关系。直到遍历的元素下标到为R-1为止。
说明：L代表小于num的数的右界，R代表大于num的左界，partition的过程就是遍历元素、不断壮大L、R范围的过程。这里比较难理解的地方可能是为什么arr[i]<num时要右移L而arr[i]>num时却不左移R，这是因为对于当前元素arr[i]，如果arr[i]<num进行swap(arr[i],arr[L+1])之后对于当前下标的数据状况是知晓的（一定有arr[i]=arr[L+1]），因为是从头遍历到i的，而L+1<=i。但是如果arr[i]>num进行swap(arr[i],arr[R-1])之后对于当前元素的数据状况是不清楚的，因为R-1>=i，arr[R-1]还没遍历到。
public?class?Code_08_NetherlandsFlags?{
public?static?int[]?partition(int[]?arr,int?L,int?R,int?p){
int?less=L;//左边下标从0开始
int?more=R;//右边下标从arr.length-1开始
int?current=L;//current作为遍历数组的下标
while(current<more){
if(arr[current]<p){
swap(arr,less++,current++);
????????????????????????????//less右移动一位,current++
}
else?if(arr[current]>p){
swap(arr,more--,current);
???????????????????????????//more左移动一位，current不移动，因为current还要继续比较
}
else{
current++;
???????????????????????????//不做任何处理，current++继续向右遍历
}
}
return?new?int[]?{less+1,more-1};
}
//交换函数
public?static?void?swap(int[]arr,int?i,int?j){
int?tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
//打印数组
public?static?void?printArray(int[]arr){
if(arr?==?null){
return;
}
for(int?i=0;i<arr.length;i++){
System.out.print(arr[i]+"?");
}
}
public?static?void?main(String[]?args){
int[]?arr=new?int[]{2,1,8,5,3,9,7,4,10};
int?num=5;
Code_08_NetherlandsFlags.partition(arr,0,arr.length-1,num);
printArray(arr);
}
13.2 小和问题：归并排序
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
对于数组[1,3,4,2,5]? 1左边比1小的数，没有；? 3左边比3小的数，1；? 4左边比4小的数，1、3；? 2左边比2小的数，1；? 5左边比5小的数，1、3、4、2；? 所以小和为1+1+3+1+1+3+4+2=16
方法一：暴力求解
??public?static?int?smallSum(int[]?arr){
????????if(arr==null||arr.length<=0)
????????????return?0;
????????int?sum=0;
????????for(int?i=0,len=arr.length;i<len;i++){
????????????for(int?j=0;j<i;j++){
????????????????if(arr[j]<arr[i])
????????????????????sum+=arr[j];
????????????}
????????}
????????return?sum;
????}
方法二：利用归并排序的并入逻辑：
简单的做法就是遍历一遍数组，将当前遍历的数与该数之前数比较并记录小于该数的数。易知其时间复杂度为O(n^2)（0+1+2+……+n-1）。
更优化的做法是利用归并排序的并入逻辑：
public?class?Code_SmallSum?{
public?static?long?smallSum(int[]?arr){
if(arr?==?null?||?arr.length<2){
return?0;
}
return?mergeSort(arr,0,arr.length-1);
}
public?static?long?mergeSort(int[]?arr,int?l,int?r){
if(l?==?r){?//结束条件
return?0;
}
int?mid=l+(?(r-l)?>>?1);//?中点位置，即(l+r)/2
return?mergeSort(arr,l,mid)+mergeSort(arr,mid+1,r)+merge(arr,l,mid,r);
//左边排序+右边排序+合并?产生的小和?相加在一起；
}
public?static?long?merge(int[]?arr,int?l,int?mid,int?r){
int[]?help?=?new?int[r-l+1];?//辅助数组
int?i=0;
int?p1=l;?//左半数组的下标
int?p2=mid+1;//右半数组的下标
long?res=0;?//小和的值
//判断是否越界
//如果左边指向的值小于右边指向的值，那么p1位置的值一定小于p2以后的所有值，因为是有序的，这时候产生小和
while(p1<=mid?&&?p2<=r){?
res+=arr[p1]<arr[p2]???arr[p1]*(r-p2+1)?:?0;?//计算小和
help[i++]=arr[p1]<arr[p2]???arr[p1++]?:?arr[p2++];?//?排序
}
//p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
while(p1<=mid){
help[i++]=arr[p1++];
}
//p2没有越界，说明p1越界了
while(p2<=r){
help[i++]=arr[p2++];
}
//将辅助数组元素拷贝会原数组
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
return?res;
}
????public?static?void?main(String[]?args)?{
????????//?TODO?Auto-generated?method?stub
????????Scanner?sc?=?new?Scanner(System.in);
????????int?N?=?sc.nextInt();
????????int[]?arr?=?new?int[N];
????????for(int?i?=?0;?i?<?N;?i++)?{
????????????arr[i]?=?sc.nextInt();
????????}
????????System.out.print(smallSum(arr));
????}
}
13.3 逆序对问题：归并排序
在一个数组中， 左边的数如果比右边的数大， 则这两个数构成一个逆序对， 请打印所有逆序对。
思路：所谓逆序对就是[4,2],[4,1],[5,1]…,也就是左边比右边大，那么有多少个逆序对就是,中间位置mid减去左指针下坐标P1+1个逆序对，也就是(mid-P1+1)个逆序对，把逆序对相加进行返回就是共有多少逆序对。
public?static?void?reverseOrder(int[]?arr)?{
????if?(arr==null?||?arr.length<2)?{
????????return?;
????}
????mergeSort(arr,0,arr.length-1);
}
public?static?int?mergeSort(int[]?arr,?int?l,?int?r)?{????????
????if?(l?==?r)?{
????????return?0;
????}
????int?mid?=?(l+r)/2;
????int?k?=?mergeSort(arr,?l,?mid)+mergeSort(arr,?mid+1,?r)+merge(arr,l,mid,r);
????System.out.println("merge总逆序数："+k);
????return?k;
}
public?static?int?merge(int[]?arr,?int?l,?int?mid,?int?r)?{
????int?merge_res=0;
????int[]?help?=?new?int[r?-?l?+?1];???//help的长度不是一个大的N?而是每次分治?的长度
????int?i=0;
????int?p1?=?l;
????int?p2?=?mid+1;
????
????while(p1?<=?mid?&&?p2?<=?r)?{
????????if?(?arr[p2]?<?arr[p1]?)?{????//说明p2此时比p1中剩下的元素都小????
????????????merge_res?+=?(mid-p1+1);??//核心?
????????????for(int?k=0;k<mid-p1+1;k++)?//打印此时的逆序对
????????????????????System.out.println(arr[p1+k]+"?"+arr[p2]);
????????}
????????help[i++]?=?arr[p1]?<?arr[p2]???arr[p1++]?:?arr[p2++]?;
????}
????while(p1<=mid)?{
????????help[i++]?=?arr[p1++];
????}
????while?(p2<=r)?{
????????help[i++]?=?arr[p2++];
????}
????//拷贝到?arr数组
????for?(int?j?=?0;?j?<?help.length;?j++)?{
????????arr[l+j]?=?help[j];
????}
????System.out.println("merge_res:"+merge_res);
????return?merge_res;
}
13.4 TopK问题：堆排序
TopK大：力扣
TopK小：力扣
- 冒泡排序的改进：冒K次
也就是说不用全部排序；只挑出符合提议的K个就可以；
冒泡排序的思想，只不过最外层循环K次就可以了；
13.5 相邻两数的最大值：桶排序
题目：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(n),且要求不能用非基于比较的排序
思路：首先为这N个数准备N+1个桶，然后以其中的最小值和最大值为边界将数值范围均分成N等分，然后遍历数组将对应范围类的数放入对应的桶中，下图以数组长度为9举例
题目问的是求如果排序后，相邻两数的最大差值。该算法巧妙的借助一个空桶（N个数进N+1个桶，必然有一个是空桶），将问题转向了求两个相邻非空桶
（其中可能隔着若干个空桶）之间前桶的最大值和后桶最小值的差值，而无需在意每个桶中进了哪些数（只需记录每个桶入数的最大值和最小值以及是否有数）
public?static?int?getMaxGap(int[]?nums){
if(nums?==?null?||?nums.length<2){
return?0;
}
int?len=nums.length;
int?min=Integer.MAX_VALUE;//数组中最小的元素
int?max=Integer.MIN_VALUE;//数组中最大的元素
for(int?i=0;i<len;i++){
min=Math.min(min,?nums[i]);
max=Math.max(max,?nums[i]);//找到最小值和最大值
}
if(min==max){
return?0;//说明只有一种数，返回0；
}
boolean?[]?hasNum=new?boolean[len+1];//表示桶里是否有数字
int?[]?maxs?=?new?int[len+1];
int?[]?mins?=?new?int[len+1];//?一个桶的三组信息hasNum、?maxs、?mins
int?index?=?0;//桶的下标
for(int?i=0;?i<len;?i++){?//nums[i]应该放到哪个桶里
index=bucket(nums[i],len,min,max);
mins[index]?=?hasNum[index]???Math.min(mins[index],?nums[i])?:?nums[i];
maxs[index]?=?hasNum[index]???Math.max(maxs[index],?nums[i])?:?nums[i];
hasNum[index]?=?true;
}
?//计算相邻非空桶中左桶的最大值和右桶的最小值的差值，找到最大的返回
int?res=0;
int?lastMax=maxs[0];?//非空左桶的最大值
int?i=1;
for(;i<=len;i++){
if(hasNum[i]){
res=Math.max(res,?mins[i]-lastMax);
lastMax=maxs[i];
}
}
return?res;
}
???
public?static?int?bucket(long?num,long?len,long?min,long?max){//计算num应该存放在哪个桶,long防止溢出
return?(int)((num-min)*len/(max-min));
}
public?static?void?main(String[]?args){
????????Scanner?sc=new?Scanner(System.in);
????????int?n=sc.nextInt();
????????int[]?arr=new?int[n];
????????for(int?i=0;i<n;i++){
????????????arr[i]=sc.nextInt();
????????}
System.out.print(getMaxGap(arr));
}
}