Java数据结构七大排序怎么使用
一、插入排序1、直接插入排序当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]与array[i-1],array[i-2],…进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。数据越接近有序，直接插入排序的时间消耗越少。时间复杂度：O(N^2)空间复杂度O(1)，是一种稳定的算法直接插入排序：publicstaticvoidinsertSort(int[]array){fo
一、插入排序
1、直接插入排序
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]与array[i-1],array[i-2],…进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
数据越接近有序，直接插入排序的时间消耗越少。
时间复杂度：O(N^2)
空间复杂度O(1)，是一种稳定的算法
直接插入排序：
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp=array[i];
int j=i-1;
for(;j>=0;--j){
if(array[j]>tmp){
array[j+1]=array[j];
}else{
break;
}
}
array[j+1]=tmp;
}
}2、希尔排序
希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的数分在同一组内，并对每一组内的数进行直接插入排序。然后取gap=gap/2，重复上述分组和排序的工作。当gap=1时，所有数在一组内进行直接插入排序。
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，直接插入排序会很快。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。
希尔排序 ：
public static void shellSort(int[] array){
int size=array.length;
//这里定义gap的初始值为数组长度的一半
int gap=size/2;
while(gap>0){
//间隔为gap的直接插入排序
for (int i = gap; i < size; i++) {
int tmp=array[i];
int j=i-gap;
for(;j>=0;j-=gap){
if(array[j]>tmp){
array[j+gap]=array[j];
}else{
break;
}
}
array[j+gap]=tmp;
}
gap/=2;
}
}二、选择排序
1、选择排序
在元素集合array[i]--array[n-1]中选择最小的数据元素
若它不是这组元素中的第一个，则将它与这组元素中的第一个元素交换
在剩余的集合中，重复上述步骤，直到集合剩余1个元素
时间复杂度：O(N^2)
空间复杂度为O(1)，不稳定
选择排序 ：
//交换
private static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
//选择排序
public static void chooseSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex=i;//记录最小值的下标
for (int j = i+1; j < array.length; j++) {
if (array[j]2、堆排序
堆排序的两种思路（以升序为例）：
创建小根堆，依次取出堆顶元素放入数组中，直到堆为空
创建大根堆，定义堆的尾元素位置key，每次交换堆顶元素和key位置的元素（key--），直到key到堆顶，此时将堆中元素层序遍历即为升序（如下）
时间复杂度：O(N^2)
空间复杂度：O(N)，不稳定
堆排序：
//向下调整
public static void shiftDown(int[] array,int parent,int len){
int child=parent*2+1;
while(childarray[child]){
child++;
}
}
if(array[child]>array[parent]){
swap(array,child,parent);
parent=child;
child=parent*2+1;
}else{
break;
}
}
}
//创建大根堆
private static void createHeap(int[] array){
for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
shiftDown(array,parent,array.length);
}
}
//堆排序
public static void heapSort(int[] array){
//创建大根堆
createHeap(array);
//排序
for (int i = array.length-1; i >0; i--) {
swap(array,0,i);
shiftDown(array,0,i);
}
} 三、交换排序
1、冒泡排序
两层循环，第一层循环表示要排序的趟数，第二层循环表示每趟要比较的次数；这里的冒泡排序做了优化，在每一趟比较时，我们可以定义一个计数器来记录数据交换的次数，如果没有交换，则表示数据已经有序，不需要再进行排序了。
时间复杂度：O(N^2)
空间复杂度为O(1),是一个稳定的排序
冒泡排序：
public static void bubbleSort(int[] array){
for(int i=0;iarray[j+1]){
swap(array,j,j+1);
count++;
}
}
if(count==0){
break;
}
}
} 2、快速排序
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
时间复杂度：最好O(n*logn):每次可以尽量将待排序的序列均匀分割
最坏O(N^2)：待排序序列本身是有序的
空间复杂度：最好O(logn)、 最坏O(N)。不稳定的排序
（1）挖坑法
当数据有序时，快速排序就相当于二叉树没有左子树或右子树，此时空间复杂度会达到O(N)，如果大量数据进行排序，可能会导致栈溢出。
public static void quickSort(int[] array,int left,int right){
if(left>=right){
return;
}
int l=left;
int r=right;
int tmp=array[l];
while(l=tmp&&l（2）快速排序的优化
三数取中法选key
关于key值的选取，如果待排序序列是有序的，那么我们选取第一个或最后一个作为key可能导致分割的左边或右边为空，这时快速排序的空间复杂度会比较大，容易造成栈溢出。那么我们可以采用三数取中法来取消这种情况。找到序列的第一个，最后一个，以及中间的一个元素，以他们的中间值作为key值。
//key值的优化，只在快速排序中使用，则可以为private
private int threeMid(int[] array,int left,int right){
int mid=(left+right)/2;
if(array[left]>array[right]){
if(array[mid]>array[left]){
return left;
}
return array[mid]array[right]?right:mid;
}
} 递归到小的子区间时，可以考虑用插入排序
随着我们递归的进行，区间会变的越来越小，我们可以在区间小到一个值的时候，对其进行插入排序，这样代码的效率会提高很多。
（3）快速排序的非递归实现
//找到一次划分的下标
public static int patition(int[] array,int left,int right){
int tmp=array[left];
while(left=tmp){
right--;
}
array[left]=array[right];
while(left stack=new Stack<>();
int left=0;
int right=array.length-1;
stack.push(left);
stack.push(right);
while(!stack.isEmpty()){
int r=stack.pop();
int l=stack.pop();
int p=patition(array,l,r);
if(p-1>l){
stack.push(l);
stack.push(p-1);
}
if(p+1四、归并排序
归并排序（MERGE-SORT）：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
时间复杂度：O(n*logN)（无论有序还是无序）
空间复杂度：O（N）。是稳定的排序。
//归并排序：递归
public static void mergeSort(int[] array,int left,int right){
if(left>=right){
return;
}
int mid=(left+right)/2;
//递归分割
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
//合并
merge(array,left,right，mid);
}
//非递归
public static void mergeSort1(int[] array){
int gap=1;
while(gap=array.length){
mid=array.length-1;
}
int right=left+2*gap-1;
if(right>=array.length){
right=array.length-1;
}
merge(array,left,right,mid);
}
gap=gap*2;
}
}
//合并：合并两个有序数组
public static void merge(int[] array,int left,int right，int mid){
int[] tmp=new int[right-left+1];
int k=0;
int s1=left;
int e1=mid;
int s2=mid+1;
int e2=right;
while(s1<=e1&&s2<=e2){
if(array[s1]<=array[s2]){
tmp[k++]=array[s1++];
}else{
tmp[k++]=array[s2++];
}
}
while(s1<=e1){
tmp[k++]=array[s1++];
}
while(s2<=e2){
tmp[k++]=array[s2++];
}
for (int i = left; i <= right; i++) {
array[i]=tmp[i-left];
}
} 五、排序算法的分析
排序方法 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性 直接插入排序 O(n) O(n^2) O(1) 稳定 希尔排序 O(n) O(n^2) O(1） 不稳定 直接排序 O(n^2) O(n^2) O(1) 不稳定 堆排序 O(nlog(2)n) O(nlog(2)n) O(1) 不稳定 冒泡排序 O(n) O(n^2) O(1) 稳定 快速排序 O(nlog(2)n) O(n^2) O(nlog(2)n) 不稳定 归并排序 O(nlog(2)n) O(nlog(2)n) O(n) 稳定
火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力，依托字节自研豆包多模态大模型，凭借火山方舟一站式平台，提供模型精调、推理部署、智能应用搭建等全链路服务，结合高性能AI算力，助力各行业快速落地大模型数字化与智能化应用。
AirBuddy 3 是面向 macOS 的蓝牙外设增强工具，可集中查看 AirPods、Beats 与苹果设备电量，提供快速连接、播放控制、电量提醒、桌面小组件和多台 Mac 外设接力等功能。
AirServer macOS版可把 Mac 转换为无线投屏接收端，通过 AirPlay 或 Google Cast 接收手机、平板和电脑画面，并支持多设备同时连接、高清镜像及会话录制，适合家庭娱乐、课堂教学、会议演示和应用展示。
火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力，依托字节自研豆包多模态大模型，凭借火山方舟一站式平台，提供模型精调、推理部署、智能应用搭建等全链路服务，结合高性能AI算力，助力各行业快速落地大模型数字化与智能化应用。
PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台，提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具，适合短剧、漫剧、广告及社交媒体内容制作。
Autodesk Maya 是面向影视、电视、动画和游戏行业的专业三维制作软件，集多边形与 NURBS 建模、角色绑定、关键帧和动作捕捉动画、Bifrost 特效模拟、材质开发及 Arnold 渲染于一体，