十大排序算法：
首先定义通用的工具方法，交换两个数字，用位运算的写法，不行可以背下来
^ 运算可以理解为无进位的相加
性质：
1.0^N=N; N^N=0;
2.a^b=b^a; a^b^c=a^(b^c);
3.同一批数^的结果与顺序无关，最后都是一样的结果。
!!!可以调用交换的原因是因为arr[i]和arr[j]的不是同一个内存空间，所以可以这样操作，如果是同一块内存空间，那么由于^性质可以得到自己和自己的^操作之后这个数字会变为0!!!
//定义新的交换方式
public static void swap(int[] arr,int i,int j){
arr[i] = arr[i] ^ arr[j]; //arr[i] = A^B ;
arr[j] = arr[i] ^ arr[j]; //B= A^B^B = A^0 = A;
arr[i] = arr[i] ^ arr[j]; //A = A^B^A = A^A^B=0^B=B;
}
异或的相关应用，对应于力扣的剑指offer第56-1题。在此之前的可以做一道引子题目：1.一个数组中只有一种数出现了奇数次，其他的数字出现了偶数次，求出这个数字。2.如果一个数组中有两个数出现了奇数次，其他的数字出现了偶数次，求出这个数字。
对于题目一：主要用的是性质1和2，那么可以得到以下结论。偶数次的数字相互抵消为0。最后剩下的一个数字和0异或操作就可以得到自身。
public static void main(String[] args) {
int[] nums ={1,1,2,3,2,3,4,4,2};
System.out.println(singleNumbers(nums));
}
public static int singleNumbers(int[] nums) {
int temp=0;
for(int i=0;i<nums.length;i++){
temp =temp^nums[i];
}
return temp;
}
结果为：
2
对于题目二就绕了一点弯路：
public static int[] singleNumbers1(int[] nums){
int temp = 0;
//就会出现temp是a^b;
//因为a^b不相等，所以a和b一定在某一位上不同，我们需要找到这一位的不同。
//以此来区分a和b。比如我们分类后有一些数字第n位上位1，有一些数字第n位不为1
//这样我们将a和b分为了两堆。（但是每一堆中由于其他数字是偶数个，所以这堆数字异或下来只剩下a或者b了，记为m）
//那么 temp和m再异或，相当于两个相同的和一个不同的异或，就可以再次区分出另外一个数字
for(int i=0;i<nums.length;i++) temp=temp^nums[i]; //eor
/*
举例子：
a: 1010111100
~a: 0101000011
~a+1: 0101000100
&： 0000000100 即可找出最右侧的1
*/
int rightone = temp & (~temp+1);
int onlyone = 0; //eor'
for(int cur:nums){
/*
(cur & rightone) ==0 为什么可以分开？
记住这里的rightone只有某一位是1其他的都是0
那么&运算的结果就值取决于cur这一位是0或者是1，因为其他位与rightone做&运算只能是0
这样就可以将这一位是1的分开。注意a！=b。这一位就是分界线，必然可以将其区分开
最后onlyone必然是a或者b中的一个，而temp是a^b
两者再次异或，就可以得到另外一个值
*/
if((cur & rightone) ==0) onlyone=onlyone^cur;
}
return new int[]{onlyone,temp^onlyone};
}
例如测试数组为[1,1,2,2,3,4]
结果为：
[4, 3]
以上是对异或运算的一点补充。
接下来是排序所用的数组例子：
int array[]={6,1,2,7,9,3,4,5,10,8};
基于比较的排序
1.冒泡排序
因为冒泡排序是每次排序之后最值到最后一位，所以最后的排序次数逐渐减少，这一点体现在i的递减上。j每次从开始遍历到i，比较相邻两位的大小即可
//冒泡排序算法
public static void bubbleSort(int array[]) {
for (int i = array.length - 1; i > 0; i--) //需要比较的次数
{
for (int j = 0; j < i; j++) { //arr[i]和arr[j]不会是一块内存
if (array[j] > array[j + 1]) {
swap(array,j,j+1);
}
}
//遍历完一趟之后打印结果
System.out.println("第" + (array.length-i) + "趟排序结果");
for (int x : array) {
System.out.print(x + " ");
}
System.out.println();
}
}
结果示例:
第1趟排序结果
1 2 6 7 3 4 5 9 8 10
第2趟排序结果
1 2 6 3 4 5 7 8 9 10
第3趟排序结果
1 2 3 4 5 6 7 8 9 10
第4趟排序结果
1 2 3 4 5 6 7 8 9 10
第5趟排序结果
1 2 3 4 5 6 7 8 9 10
第6趟排序结果
1 2 3 4 5 6 7 8 9 10
第7趟排序结果
1 2 3 4 5 6 7 8 9 10
第8趟排序结果
1 2 3 4 5 6 7 8 9 10
第9趟排序结果
1 2 3 4 5 6 7 8 9 10
2.选择排序算法
每次遍历一轮，选择数组中的最值放在数组的固定位置，每一趟结束都有一个数字拍好顺序。比如第一趟排序结束后会将最值放在下标为0的位置，第二趟排序结束后会将最值放在下标为1的位置，以此类推。。。。可以结合排序结果看出排序算法的特点。
public static void selectsort(int array[]) {
for (int i = 0; i < array.length - 1; i++) { //需要排序的次数
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
} //找到最小位置的下标
//优化,如果初始下标不变时，那就是不需要交换的，节省时间
if (min != i) { //arr[i]和arr[min]不会是一块内存
swap(array,min,i);
}
System.out.println("第" + (i+1) + "趟排序结果");
for (int x : array) {
System.out.print(x + " ");
}
System.out.println();
}
}
结果示例：
第1趟排序结果
1 6 2 7 9 3 4 5 10 8
第2趟排序结果
1 2 6 7 9 3 4 5 10 8
第3趟排序结果
1 2 3 7 9 6 4 5 10 8
第4趟排序结果
1 2 3 4 9 6 7 5 10 8
第5趟排序结果
1 2 3 4 5 6 7 9 10 8
第6趟排序结果
1 2 3 4 5 6 7 9 10 8
第7趟排序结果
1 2 3 4 5 6 7 9 10 8
第8趟排序结果
1 2 3 4 5 6 7 8 10 9
第9趟排序结果
1 2 3 4 5 6 7 8 9 10
3.插入排序
需要注意的是这个算法最好的时间复杂度是O（N）复杂度，当数组有序时，内部循环不工作，所以是O(N)复杂度，如果数组逆序时，每次都要进行内层for循环，那么就是O(N^2)复杂度。每一趟都会将0-i的区间保证有序。再对i+1进行排序处理。
public static void Insertsort(int array[]) {
for (int i = 1; i < array.length; i++) { //模拟0-i这个范围是有序的
/*
因为0~i-1已经就是有序的了，所以需要判断当前位置和前一个位置的大小，如果是逆序那么
需要将两者交换，j--继续比较知道找到顺序的位置停止，或者越停止访问
*/
for (int j=i-1;j>=0 && array[j]>array[j+1];j--){
swap(array,j,j+1);
}
System.out.printf("第%d次排序结果为:", i);
for (int x : array) {
System.out.print(x + " ");
}
System.out.println();
}
}
结果示例：
第1次排序结果为:1 6 2 7 9 3 4 5 10 8
第2次排序结果为:1 2 6 7 9 3 4 5 10 8
第3次排序结果为:1 2 6 7 9 3 4 5 10 8
第4次排序结果为:1 2 6 7 9 3 4 5 10 8
第5次排序结果为:1 2 3 6 7 9 4 5 10 8
第6次排序结果为:1 2 3 4 6 7 9 5 10 8
第7次排序结果为:1 2 3 4 5 6 7 9 10 8
第8次排序结果为:1 2 3 4 5 6 7 9 10 8
第9次排序结果为:1 2 3 4 5 6 7 8 9 10
4.归并排序
分而治之，将原数组不断二分，最后直到数组被划分为只剩下一个数字为止，这时候这个子数组天然有序。然后不断的将有序的子数组通过mergesort这个代码（就是一种类似于两个有序的数组或者链表合并为一个更大的有序数组或者链表）。
通过master公式可以得知
T(N) = 2T(N/2)+O(N);
2个子递归所以a=2（系数），每一个子递归规模一致，并且每次子问题数组规模减少一半，所以是N/2(分母b=2)，logb(a) = 1;O(N)是归并排序的操作时O(N),次幂是1，相等，由公式得归并排序最后得时间复杂度是O(NlogN).但是空间复杂度是O(N)(MergeSort那块开辟的数组占空间)。
(推导讲解可以参考左神P2 50:00 那块的视频讲解)。
//分解算法,归并排序分而治之
public static void mrege(int arr[],int left,int right)
{
if(left<right)
{
//int mid=(left+right)/2;
int mid = left+((right-left)>>1); //比上面的写法好
//向左递归分解
mrege(arr,left,mid);
//向右递归分解
mrege(arr,mid+1,right);
//合并
mergesort(arr,left,mid,right);
System.out.println("排序结果为：");
for (int x : arr) {
System.out.print(x + " ");
}
System.out.println();
}
}
//类似单链表合并排序
public static void mergesort(int array[],int left,int mid,int right)
{
int i=left; //i左边有序序列
int j=mid+1; //j表示右边有序序列
int t=0; //i指向temp
int[] temp =new int[right-left+1]; //辅助空间
//先把两边有序序列填充temp，结束后将剩余数组直接copy过去
while (i<=mid && j<=right)
{
if(array[i]<=array[j]) //将较小值填入temp数组
{
temp[t]=array[i];
t++;
i++;
}
else{
temp[t]=array[j];
t++;
j++;
}
}
while(i<=mid){
temp[t]=array[i];
t++;
i++;
}
while(j<=right){
temp[t]=array[j];
t++;
j++;
}
//将temp拷贝到array数组，将归并之后的数组拷贝到原数组之后使得有序
t=0;
int templeft=left;
while (templeft<=right){
array[templeft++]=temp[t++];
}
}
结果示例+(分析)：
排序结果为： //left=0,right=1 ,[1,6]子数组排序有序
1 6 2 7 9 3 4 5 10 8
排序结果为： //left=0,right=2 ,[1,2,6]子数组排序有序
1 2 6 7 9 3 4 5 10 8
排序结果为：//left=3,right=4 ,[7,9]子数组排序有序
1 2 6 7 9 3 4 5 10 8
排序结果为： //left=0,right=4 ,[1,2,6,7,9]子数组排序有序
1 2 6 7 9 3 4 5 10 8
排序结果为： //left=5,right=6 ,[3,4]子数组排序有序
1 2 6 7 9 3 4 5 10 8
排序结果为：//left=5,right=7 ,[3,4,5]子数组排序有序
1 2 6 7 9 3 4 5 10 8
排序结果为：//left=8,right=9 ,[8,10]子数组排序有序
1 2 6 7 9 3 4 5 8 10
排序结果为：//left=5,right=9 ,[3,4,5,8,10]子数组排序有序
1 2 6 7 9 3 4 5 8 10
排序结果为：//left=0,right=9 ,[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ]子数组排序有序,至此排序结束
1 2 3 4 5 6 7 8 9 10
归并排序的应用（小数问题和逆序对问题）
1.题目描述为：在一个数组中，每一个数左边比当前数小的数字累加起来，叫做这个数字的小数和，那么所有的小数和加起来就叫做数组的小数和。例如[1,3,4,2,5]的小数和为1+1+3+1+1+3+4+2=16。
public class SmallSum {
public static void main(String[] args) {
int[] nums={1,3,4,2,5};
System.out.println(Process(nums,0,nums.length-1));
}
public static int Process(int[]arr,int left,int right){
if(left==right) return 0; //一个数没有小数和可以直接返回
int mid = left + ((right-left)>>1);
return Process(arr,left,mid)
+Process(arr,mid+1,right)
+merge(arr,left,mid,right);
//返回左边排序产生的小数和+右边排序的小数和+当前归并产生的小数和
}
public static int merge(int[]arr,int left,int mid,int right){
int res =0;
int i = left;
int j = mid+1;
int k =0;
int[] temp = new int[right-left+1];
while (i<=mid && j<=right){
if(arr[i]<arr[j]){ //注意不能等于，等于的话右侧数组先移动，直到严格大于左边才可以
//当前左侧数字小，那么对于右侧的有序数组，这个数就是右侧所有数字的小数，数量就是right-j+1。所以小数和就是arr[i]*(right-j+1)。
res += arr[i]*(right-j+1);
temp[k++]=arr[i++];
}else{
temp[k++]=arr[j++];
}
}
while (i<=mid) temp[k++]=arr[i++];
while (j<=right) temp[k++]=arr[j++];
k=0;
int templeft = left;
while (k<temp.length){
arr[templeft++] = temp[k++];
}
return res;
}
}
5.快速排序
每次都找一个基准线，每次排序后可以保证基准左边的都小于基准，大于基准的都在右边。平均时间复杂度时O(NlogN)，最坏是O(N2)。空间复杂度是O(logN)的。
public static void quiksort(int array[],int left,int right){
int i,j,t,temp;
if(left>right) return;
int tempindex = left+(int)(Math.random()*(right-left+1)); //随机选则一个数字作为基准,对极端顺序数组不敏感，增加一点鲁棒性。
swap1(array,left,tempindex);
temp=array[left]; //选择最左边的作为基准线
i=left;
j=right;
while(i!=j){ //i,j是动态变化的lreft和right只是一个参考
//从右向左找到第一个比temp小的数,少一个等于号差别太大
while(array[j]>=temp && i<j){
j--;
}
//从做向右找到第一个比temp大的数
while (array[i]<=temp && i<j){
i++;
}
//交换两者的位置
if(i<j){
swap1(array,i,j);
}
}
//最后将基准线归位
array[left]=array[i];
array[i]=temp;
System.out.println("选择的中间数是"+temp+" 排序结果为");
for (int x : array) {
System.out.print(x + " ");
}
System.out.println();
//再次对基准左边的递归排序
quiksort(array,left,i-1);
quiksort(array,i+1,right);
}
结果示例：
选择的中间数是3 排序结果为
2 1 3 7 9 6 4 5 10 8
选择的中间数是1 排序结果为
1 2 3 7 9 6 4 5 10 8
选择的中间数是2 排序结果为
1 2 3 7 9 6 4 5 10 8
选择的中间数是5 排序结果为
1 2 3 4 5 6 9 7 10 8
选择的中间数是4 排序结果为
1 2 3 4 5 6 9 7 10 8
选择的中间数是8 排序结果为
1 2 3 4 5 7 6 8 10 9
选择的中间数是7 排序结果为
1 2 3 4 5 6 7 8 10 9
选择的中间数是6 排序结果为
1 2 3 4 5 6 7 8 10 9
选择的中间数是9 排序结果为
1 2 3 4 5 6 7 8 9 10
选择的中间数是10 排序结果为
1 2 3 4 5 6 7 8 9 10
6.堆排序
1.构建堆的操作
//现在插入数字的下标是index，需要比较index和父节点的位置，不断调整。是一个不断向上比较的过程
//log(N)
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; //移动当前节点到父节点上面继续比较
} //end while ,没有当前的父节点大就结束循环
}
2.每次将顶部最值和堆的最末尾元素交换顺序，这样可以使得最值固定在末尾，这样每次循环都会有一个最值固定在末尾，并且同时使得堆元素的范围-1，使得下次交换时不考虑已近固定的元素，最后经过多次循环使得每一个元素归位，完成排序即可。在交换最大值的同时需要将剩下的元素调整顺序维持堆特性，这样在每次交换堆顶和末尾的时候才能保证是最值的交换
//删除数字使得继续为大根堆，把堆末尾节点直接放在大根堆上面，然后size--，表示最大的节点在末尾已近有序了啊
//最后不断向下调整堆的结构即可（直到所在的index大于两个孩子或者没有孩子可以比较时停止）
//index 表示从当前位置开始向下调整
//log(N)的复杂度
public static void heapify(int[]arr,int index,int heapSize){
int left = 2*index+1;
/*
left<heapSize 没有越界说明我有左孩子，左孩子越界了，不用说右孩子肯定也就越界了
*/
while(left<heapSize){
//选择两个孩子中的较大者准备和父节点比较
int large = left+1<heapSize && arr[left+1] >arr[left] ? left+1:left;
//判断孩子和父节点的大小
large = arr[large]>arr[index] ? large:index;
//如果当前的index比两个孩子大，到此为止，结束
if(large==index) break;
//如果孩子节点大，那么交换
swap(arr,index,large);
//继续向下走循环判断,那么需要更新index以及左孩子
index = large;
left = index*2+1;
}
}
3.最后调用即可.
public static void heapSort(int[] arr){
if(arr==null || arr.length<2){
return;
}
int heapSize =0;
// for(int i=0;i<arr.length;i++){ //O(N)
// heapInsert(arr,i); //O(logN)
// heapSize++; //堆的数量加1
//}
//建立堆,这里是从堆的底部自下向上来调整堆的结构
//对比之前的一个一个插入也是一种其他的办法。
heapSize = arr.length
for(int i=arr.length-1;i>=0;i--){
heapify(arr,i,heapSize);
}
swap(arr,0,--heapSize); //每次交换堆顶和堆的尾部，这样最值不断在尾部固定
System.out.println("排序结果为");
for(int temp:arr){
System.out.print(temp+" ");
}
System.out.println();
while (heapSize>1){ //堆中只有1个数据时天然有序
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
System.out.println("排序结果为");
for(int temp:arr){
System.out.print(temp+" ");
}
System.out.println();
}
}
结果示例:
可以看到,每次循环,都会有一个最大值到末尾,比冒泡排序高级,因为比较查找的顺序是log(N)的,总体算法性能是O(NlogN).空间复杂度是O(1).
排序结果为
3 9 6 7 8 2 4 1 5 10
排序结果为
5 8 6 7 3 2 4 1 9 10
排序结果为
1 7 6 5 3 2 4 8 9 10
排序结果为
4 5 6 1 3 2 7 8 9 10
排序结果为
2 5 4 1 3 6 7 8 9 10
排序结果为
2 3 4 1 5 6 7 8 9 10
排序结果为
1 3 2 4 5 6 7 8 9 10
排序结果为
2 1 3 4 5 6 7 8 9 10
排序结果为
1 2 3 4 5 6 7 8 9 10
堆排序的应用：将数组排序，每个元素移动的距离不能超过k。
//将数组排序，每个元素移动的距离不能超过k。
public static int[] sortedArrDistanceLessK(int[]arr,int k){
//直接使用java内部的数据结构，优先级队列底层就是堆结构
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index =0;
for(;index<=Math.min(arr.length,k);index++){
heap.add(arr[index]); //需要将前k+1个数放在堆里面
}
int i=0;
for(;index<arr.length;i++,index++){
heap.add(arr[index]); //弹出一个数
arr[i] = heap.poll(); //
}
while (!heap.isEmpty()){ //最后加入不了数字了直接顺序弹出即可
arr[i++] = heap.poll();
}
return arr;
}
知识点：自定义比较器
public class HeapTest {
public static class ASCpmp implements Comparator<Integer>{
/*
返回负数表示第一个参数排前面
返回正数的表示第二个参数排在前面
返回0表示无所谓
*/
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1; //从大到小排序
}
}
//默认是小根堆，但是加入人为构造的比较器之后就是可以构造大根堆
public static void main(String[] args) {
PriorityQueue<Integer> heap =new PriorityQueue<>(new ASCpmp());
heap.add(2);
heap.add(10);
heap.add(4);
heap.add(9);
while (!heap.isEmpty()){
System.out.println(heap.poll());
}
}
结果：加入人为的构造器就可以改变顺序，构造大根堆，否组默认是小根堆。并且其他的复杂数据也可以用自己定义的构造器进行处理。
10
9
4
2
不基于比较的排序
1.基数排序 时间复杂度虽然比较低，但是空间复杂度高
public static void radixSort(int[]arr,int L,int R,int digit){
final int radix =10; //基数，一般数字排序就是设置0-9这九个桶
int i=0,j=0;
int[] bucket =new int[R-L+1]; //准备和原数组一样的辅助空间即可
for(int d=1;d<=digit;d++){ //原数组有多少位，就需要进行多少次排序
int[] count = new int[radix]; //count[0...9] 表示计数
for(i=L;i<=R;i++){
j=getDigit(arr[i],d);
count[j]++; //计数器记录多少位数字
}
for(i=1;i<radix;i++){ //处理为前缀和数组
count[i] =count[i]+count[i-1];
}
//倒序处理就是因为模拟的是后入桶的后出桶的规则
for(i=R;i>=L;i--){
j=getDigit(arr[i],d);
bucket[count[j]-1] =arr[i];
count[j]--;
}
for(i=L,j=0; i<=R;i++,j++){
arr[i] = bucket[j];
}
System.out.println("第"+d+"趟排序结果为");
for(int temp:arr){
System.out.print(temp+" ");
}
System.out.println();
}
}
//d=1 取出个位数字，d=2 取出十位数字以此类推
public static int getDigit(int num,int d){
for(int i=1;i<d;i++){
num = num /10;
}
return num%10;
}
结果示例：
第1趟排序结果为 //第一趟将个位数排序好
11 21 12 22 42 3 43 14
第2趟排序结果为 //第一趟将十位数排序好
3 11 12 14 21 22 42 43
注： 排序算法的稳定性需要理解一个排序算法的原理来举出反例（P4）
不稳定算法有：
选择排序：反例 3,3,3,1,3,3,3 （第一个3和1交换，破坏了相同数字的次序）
快速排序：反例：6,7,6,6,3 （num=5，快速排序时指针到3的时候需要和<=区域的下一个交换，也就是元素6，交换后相同数字的顺序已经变了）
堆排序：5 4 4 6 堆调整的时候就会破坏。
左神排序总结
