您现在的位置是：首页 > Java 当前栏目 排序算法Java JAVA 算法 排序 递归 2023-03-02 11:03:30 时间 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 ![这里写图片描述][70] 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； ## 1.冒泡排序 ## ![这里写图片描述][70 1] 关键代码： import java.util.Arrays; /*冒泡排序： 每趟结果将最大的数选择出来，放在数组的最后*/ public class BubbleSort { public static void main(String[] args) { int[] test = { 1,2,4,5,6,2,3}; int[] sort = sort(test); System.out.println(Arrays.toString(sort)); } public static int[] sort(int[] A){ for(int i = 0; i<A.length; i++){ for(int j= i+1; j<A.length; j++){ if(A[i] > A[j]){ int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } } } return A; } } 分析： 冒泡排序是一种稳定的排序方法。 •若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n) •若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2) •起泡排序平均时间复杂度为O(n2) ## 2.快速排序 ## 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。 /*快速排序： 选择一个基准，将数组分成两部分；比基准大的一部分，比基准小的一部分； 然后重复此过程*/ public class QuickSort { public static void main(String[] args) { int[] a = { 2,8,4,5,3,5,4,8,14,54,23}; sort(a,0,a.length-1); System.out.println(Arrays.toString(a)); } //做递归 public static void sort(int[] a, int left, int right){ if(left < right){ //如果不加这个判断递归会无法退出导致堆栈溢出异常 int mid = partion(a, left, right); sort(a, left, mid - 1);//递归对低子表递归排序 sort(a, mid + 1, right); //递归对高子表递归排序 } } private static int partion(int[] a, int low, int high) { int key = a[low];//基准元素，排序中会空出来一个位置 while(low<high){ while(low<high && a[high]>=key){ //从high开始找比基准小的，与low换位置 high--; } a[low]=a[high]; while(low<high && a[low]<=key){ //从low开始找比基准大,放到之前high空出来的位置上 low++; } a[high]=a[low]; } a[low]=key;//此时low=high 是基准元素的位置，也是空出来的那个位置 return low; } } ## 3、折半插入排序（二分法插入排序） ## 折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。 private static void binaryInsertSort(int[] array) { for(int i=1;i<array.length;i++){ int tempData=array[i]; int low=0; int high=i-1; while(low<=high){ int middle=(low+high)/2; if(array[middle]<tempData) low=middle+1; else high=middle-1; } System.arraycopy(array,low,array,low+1,i-low); array[low]=tempData; } } [70]: /images/20220525/661d4071a5b44ac19cf5ccd6926c4fec.png [70 1]: /images/20220525/acf7cabea64742a48ebbe86356be64bb.png 本文地址： 排序算法Java 相关文章 Java学习 java学习 Java学习 Java BitSet Java 监听器 Java Calendar Java Calendar Java变量 java 变量 Java变量 Java：变量 Java变量 【Java】变量 java类 Java--类 Java 类 jchq java Java随机数 Java随机数 java随机数
