【基础算法】排序算法

一、冒泡排序

【简述】相邻位置前面数 > 后面数 ---》交换 n-1 【每次换好一个数】


public static void bubbleSort(int[] str){
  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]){
        swap(arr,i,i+1);
      }
    }
  }
}

时间复杂度：O(N^2)

二、选择排序

【简述】1~n中找最小数，与第1位置交换，然后从2~n中找最小数，与2位置交换


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 insertSort(int[] arr){
  if(arr == null || arr.length < 2){
    return;
  }
  for(int i = 1 ; i < arr.length;i++){
    for(int j = i-1 ; j>=0 &&arr[j] >arr[j+1] ; j--){
      swap(arr,j,j+1)
    }
  }
}

时间复杂度：最好情况：O(N^2) 最差情况：O(N) 平均情况：O(N^2)

交换两数方法：

方式一：


public static void swap(int[] arr, int j , int j){
   int tmp = arr[i];
   arr[i] = arr[j];
   arr[j] = tmp;
}

方式二：


public static void swap(int[] arr, int j , int j){
   arr[i] = arr[i] ^ arr[j]
   arr[j] = arr[i] ^ arr[j]
   arr[i] = arr[i] ^ arr[j]
}

四、归并排序

【简述】先左侧部分排好序，再右侧部分排好序，两头都是有序的，准备一个有序数组，用外排序的方式，小的填依次动，一个结束后，另一个没动到末尾部分拷贝到辅助数组，再整体拷贝到原数组，完成排序。

T(N) = 2T(n/2) +O(N)

时间复杂度 O(N*logN) ; 额外空间复杂度O（N）


public static void sortProcess(int[] arr, int L , int R){
  if(L==R){
    return;
  }
  int mid = L + ((R-L) >>1); //L 和 R中点的位置(L+R)/2
  sortProcess(arr , L , mid); //T(n/2)
  sortProcess(arr, mid+1, R); // T(n/2)
  merge(arr,L,mid,R);   //O(N)
  //T(N) = 2*T(N/2) +O(N)
}
public static void merge(int[] arr , int L , int mid , int R){
  int [] help = new int [R-L+1];
  int p0 = 0;
  int p1 = L;
  int p2 = mid +1;
  while(p1 <= mid && p2 <=R){
    help[i++] = arr[p1] <arr[p2] ? arr[p1++] : arr[p2++];
  }
  // 两个必有且有一个越界
  while(p1<=mid){
    help[i++] = arr[p1++];
  }
  while(p2<=R){
    help[i++] = arr[p2++];
  }
  for(i = 0;i<help.length;i++){
    arr[L+i] = help[i];
  }
  
}

五、快速排序

荷兰🇳🇱问题：

【算法思想】数组两端设置less和more指针，使用cur指针从左向右遍历，小于num时与较小数区域的下一个数交换，less和cur右移；等于num时，cur右移，大于num时，和more指针数交换，more左移；以此类推


public static int[] partition(int[] arr,int L,int R, int num){
  int less = L - 1;
  int more = R + 1;
  int cur = L;
  while(cur < more){
    if(arr[cur]>num){
      swap(arr,++less,cur++);
    }else if (arr[cur]>num){
      swap(arr,--more,cur);
    }else{
      cur++;
    }
  }
  return new int[] {less+1 , more -1};
}

经典快排：


public static void quickSort(int[] arr , int L , int R){
  //划分左右部分
  if(L < R){
    int p = partition(arr,L,R);
    quickSort(arr,L, p-1);
    qickSort(arr,p+1,R);
  }
  
}
 
public static int[] partition(int[] arr,int L , int R){
  int less = L-1;
  int more = R;
  while(L < more){
    if(arr[L] < arr[R]){  //less小于区域，L为curr ，more为大于区域
      swap(arr,++less,L++);
    }else if (arr[L] > arr[R]){
      swap(arr,--more,L);
    }else{
      L++;
    }
  }
  swap(arr,more,R);
  return more;
}

时间复杂度: 最好情形O(N * logN) 最坏情形 O(N)

荷兰🇳🇱思想改进快速排序：


public static void quickSort(int[] arr , int L , int R){
  if(L < R){
    //随机快排加上下面代码
    //swap(arr,L + (int)(Math.random() * (R - L + 1)), R);
    int[] P = partition(arr,L, R);
    quickSort(arr, L , p[0]-1);
    quickSort(arr,p[1]+1, R);
  }
}
 
public static int[] partition(int[] arr , int L , int R){
  int less = L - 1;   //less为小于区域，more为大于区域
  int more = R;
  while(L<more){
    if(arr[L] < arr[R]){
      swap(arr,++less , L++);
    }else if(arr[L] > arr[R]){
      swap(arr,--more , L);
    }else{
      L++;
    }
  }
  swap(arr,more,R);   //最后将R数与大于区域前一个数交换位置
  return new int[] { less +1 ， more};
}

时间复杂度：最好情形O(N * logN) ，额外空间复杂度 O(logN) --> 二分断点记录所需要的空间。

打乱源数据样本分部使用1）随机打乱 2）哈希函数；工程上通常不使用递归形式的算法，一般改成非递归。

六、堆排序

数组结构：完全二叉树：节点关系：

2*i + 1 i节点的左孩子
2*i + 2 i节点的右孩子
(i-1) /2 i节点的父节点

大根堆 ---》完全二叉树


public static void heapSort(int[] arr){
  if(arr == null  || arr.length < 2){
    return;
  }
  //构建堆
  for (int i =0; i < arr.length ; i++){
    heapInsert(arr , i); // 0 ~ i   
  }
  int heapSize = arr.length;
  //将排好序的数放置末尾
  swap(arr , 0 , --heapSize);
  while(heapSize > 0){
    //调整堆
    heapify(arr, 0 , heapSize);
    //将顶部排好序的数放置末尾
    swap(arr, 0 , --heapSize);
  }
}
 
//构建堆方法
public static void heapInsert(int[] arr, int index){
  while(arr[index] > arr[(index - 1)/2]){
    swap(arr,index , (index - l) / 2);
    index = (index - 1) /2;
  }
}
 
public static void heapify(int[] arr, int index , int heapSize){
  int left = index  * 2 +1;
  while(left < heapSize){
    int largest = left + 1 < heapSize  && arr[left + 1] >          arr[left] ?left + 1: left;
    if(largest == index){
      break;
    }
    swap(arr , largest , index);
    index = largest;
    left = index * +1;
  }
}

堆的用途：

解决找中位数问题。（初识一个大根堆和一个小根堆，新增数字>大根堆顶就放小根堆，小于小根堆顶就放小根堆，始终保持两个堆size不超过1，动态调整堆）

堆排序就是利用堆结构进行排序。

使数组变成大根堆
将堆顶元素和最后一个元素交换，heapSize-1，调整堆，每次排好一个堆尾以此类推

时间复杂度：O(N*logN) , 额外空间复杂度O(1)

堆结构非常重要

1、堆结构的heapInsert 与 heapify

2、堆结构的增大和减少

3、如果只是建堆的过程，时间复杂度为O(N)

4、优先级队列结构，就是堆结构

七、排序总结与稳定性

稳定性：在排序过程中，相同值的相对次序在排序前后保存不变。

稳定排序：冒，插，归

不稳定排序：选，快，堆

稳定性意义：排序前的序列信息很重要需要保留，后续排序只有稳定的才能不打乱前面顺序信息。

工程中排序通常是进行混合使用：

🌰：

在数据量样本较小的情形下，通过快速排序中混入插入排序，当样本数量小于某一个阈值时使用插入排序，其余情形使用快速排序。当样本量小时，插入排序的量级系数较小。
在样本数据为基本数据类型数据时，通常使用快排，不考虑算法的稳定性。
在需要保留原来样本信息顺序，则选用稳定排序。

有关排序排序问题的补充：

1、归并排序的额外空间复杂度可以变成O(1),但是非常难，不需要掌握，可以搜索“归并排序，内部缓存法”

2、快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜索“01 stable sort”

3、有一道题目，是奇数放在数组坐标，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官，面试官非良人。

4、荷兰🇳🇱问题在空间复杂度O(1) 时间复杂度O(N)的情形下，做不到稳定性。

八、桶排序、计数排序、基数排序

非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用
时间复杂度O(N) , 额外空间复杂度O(N)
稳定的排序

桶排序：桶就是容器，将待排序元素依次归属到桶里去，然后将地位置的桶依次倒到高位置的桶。

计数排序：申请n+1个额外空间，记录元素出现的次数，然后依次倒出记录即可。

基数排序：按照元素的位数，从权重位较小位依次向权重高位进行排序。

❓给定一个数组，如果排序之后，相邻两数的最大差值，要求时间复杂度O(N),且要求不能用非基于比较的排序。

简述思想：使用桶排序，将N个数的min~max等分N+1份放入N+1个桶。左右两侧必定有值，中级必定有空桶，相邻最大差值的两数必定不在一个桶中，所以，本题只需要知道哪些桶为空，和有值桶的最大值和最小值。计算每一个非空桶的最小值与前一个非空桶的最大值的差，便是解。

【注意】有空桶存在，只能说明相邻最大差值的两数必定不在一个桶中，并不能推得最大差值来自空桶两边的非空桶。

🌰：桶1(10~19):19 ；桶2(20~29)：空；桶3(30~39):桶4(40~49):49 最大差值:19

【思想】：通过题目中信息，推出某些特定条件，来进行全局可能性剪枝。


public static int maxGap(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;
      }
			boolean[] hasNum = new boolean[len+1];
      int[] maxs = new int[len + 1];
      int[] mins = new int[len + 1];
			int bid=0;
      for(int i =0;i<len ;i++){
        //确定当前数属于几号桶
        bid = bucket(nums[i] ,len,min,max);
        //更新该桶最小值
        mins[bid] = hasNum[bid] ? Math.min(mins[bid] , nums[i]):nums[i];
        maxs[bid] = hesNum[bid] ? Math.max(maxs[bid], nums[i]):nums[i];
        hasNum[bid] = true;
      }
			int res = 0;
			int lastMax = maxs[0];
			int i =1;
  //计算每一个非空桶的最小值与前一个非空桶的最大值的差
			for(;i<=len;i++){
        if(hasNum[i]){
          res = Math.max(res,min[i]-lastMax);
          lastMax = maxs[i];
        }
      }
      return res;  
}
 
//判断当前数在哪个桶
public static int bucket(long num,long len ,long min , long max){
  return (int)((num -min)*len/(max-min));
}

相关阅读:
什么是全员生产维护TPM？
C语言-魔方阵
 算法训练营第三天 | 203.移除链表元素、707.设计链表、206.反转链表
 华为云API自然语言处理的魅力—AI情感分析、文本分析
 全国的科技创新情况数据分享，涵盖2020-2022年三年情况
 【老生谈算法】matlab实现线性分组码编译源码——线性分组码编译
 ppt忘记保存怎么恢复？
链表——反转链表
 java-net-php-python-jsp学生创新项目系统计算机毕业设计程序
 小程序添加悬浮在线客服源码
原文地址：https://blog.csdn.net/ckq707718837/article/details/125627585

【基础算法】 排序算法