Java常用的排序算法及其优缺点 |21xrx.com

Java常用的排序算法及其优缺点

2023-06-16 17:09:19 深夜i -- --

冒泡排序时间复杂度排序算法

Java作为一门广泛应用的编程语言，其常用的排序算法也是非常重要的。下面我们一起来了解Java常用的排序算法有哪些以及它们的优缺点。

1. 冒泡排序

冒泡排序是一种基础的排序算法，在Java中也是被广泛应用的。该算法的基本思想是从头到尾依次比较相邻两个元素的大小，如果前者大于后者则交换位置。经过一轮比较后，最大的元素就会被排到最后。重复此过程，直到所有元素都排好序。

算法优点：代码简单易懂，容易实现。

算法缺点：实际应用中比较低效，时间复杂度为O(n^2)。

以下是冒泡排序的代码实现：


public static void bubbleSort(int[] arr){
  int temp;
  for(int i=0; i
    for(int j=0;j
      if(arr[j]>arr[j+1]){
        temp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
      }
    }
  }
}

2. 快速排序

快速排序是一种基于分治的排序算法，在Java中也是十分流行的。该算法的基本思想是在序列中选取一个基准值，将序列分为比基准值小的部分和比基准值大的部分。然后对两部分分别进行快速排序，递归进行直到排序完成。

算法优点：排序效率较高，时间复杂度为O(nlogn)。

算法缺点：排序的稳定性不高。

以下是快速排序的代码实现：


public static void quickSort(int[] arr, int low, int high){
  if(low
    int pivotIndex=getPivotIndex(arr,low,high);//获取基准值的索引
    quickSort(arr, low, pivotIndex-1);
    quickSort(arr,pivotIndex+1, high);
  }
}
public static int getPivotIndex(int[] arr, int low, int high){
  int pivot=arr[low];//取第一个元素为基准值
  while(low
    while(low
  pivot) high--;
 
    arr[low]=arr[high];//找到小于等于基准值的元素
    while(low
  <=pivot) low++;
 
    arr[high]=arr[low];//找到大于基准值的元素
  }
  arr[low]=pivot;//将基准值插入到合适的位置
  return low;
}

关键词：快速排序、时间复杂度、排序算法

3. 归并排序

归并排序也是十分常用的一种排序算法。该算法的基本思想是将序列不断划分为子序列，对子序列进行排序，然后逐步合并得到完整的有序序列。

算法优点：整个排序过程比较稳定，时间复杂度为O(nlogn)。

算法缺点：空间复杂度较高，需要较多的额外空间。

以下是归并排序的代码实现：


public static void mergeSort(int[] arr,int low, int high){
  if(low
    int mid=(low+high)/2;
    mergeSort(arr,low,mid);//递归排序前半部分
    mergeSort(arr,mid+1,high);//递归排序后半部分
    merge(arr,low,mid,high);//合并有序序列
  }
}
public static void merge(int[] arr, int low, int mid, int high){
  int[] temp=new int[arr.length];//创建临时数组
  int k=low;//排序后数组的索引
  int i=low;//前半部分数组的索引
  int j=mid+1;//后半部分数组的索引
  while(i<=mid&&j<=high){
    if(arr[i]
      temp[k++]=arr[i++];
    }else{
      temp[k++]=arr[j++];
    }
  }
  while(i<=mid){//将前半部分数组的剩余元素放入临时数组
    temp[k++]=arr[i++];
  }
  while(j<=high){//将后半部分数组的剩余元素放入临时数组
    temp[k++]=arr[j++];
  }
  for(int p=low;p<=high;p++){//将临时数组中排好序的元素复制到原数组中
    arr[p]=temp[p];
  }
}

关键词：归并排序、空间复杂度、排序算法

上一篇: idea打包java可执行jar包

下一篇: Java文件上传支持的格式有哪些

评论区

()

相似文章