标签分类
技术文章
当前位置:主页 > 计算机编程 > java > 总结Java常用排序算法

Java常用排序算法整理分享

  • 发布时间:
  • 作者:码农之家原创
  • 点击:181

总结Java常用排序算法

这篇文章主要知识点是关于Java,排序算法,总结Java常用排序算法,Java 排序算法整合(冒泡,快速,希尔,拓扑,归并) 的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子书

Java设计模式深入研究
  • 类型:Java大小:49.2 MB格式:PDF出版:人民邮电出版社作者:刘德山
立即下载

更多相关的学习资源可以参阅 程序设计电子书Java电子书、等栏目。

排序算法常用的有冒泡排序,选择排序和插入排序,下面将用Java语言实现这三种排序方式,并且介绍一种由插入排序拓展出来的希尔排序。

1、冒泡排序(BubbleSort)是一种最简单的排序算法。它的基本思想是迭代地对输入序列的第一个元素到最后一个元素进行俩俩比较,当满足条件时交换这俩个元素的位置,该过程持续到不需要执行上述过程的条件时。

总结Java常用排序算法

2、我们自定义一个排序的函数为sorter(int[]array);

  private static void sorter(int[] array)     for(int i=0;i<array.length-1;i++) {      for(int j=0;j<array.length-i-1;j++) {        if(array[j]>array[j+1]) {          int temp = array[j];          array[j] = array[j+1];          array[j+1] = temp;        }      }    }  }

 

完整代码如下图:

总结Java常用排序算法

3、运行结果如下:

总结Java常用排序算法

1、选择排序

选择排序(SelectSort)是一种原地(in-place)排序算法,适用于小文件。选择排序是基于键值并且交换是发生在需要交换时才执行,所以选择排序常用于数值较大和键值较小文件。

总结Java常用排序算法

2、

private static void sorter(int[] array)     for(int i=0;i<array.length-1;i++) {      int index = i;      for(int j=index;j<array.length-1;j++) {        if(array[index]>array[j+1]) {          index = j+1;        }      }      int temp = array[index];      array[index] = array[i];      array[i] = temp;    }  }

  

总结Java常用排序算法

3、运行结果

总结Java常用排序算法

1、插入排序

插入排序(InsertionSort)是一种简单且有效的比较排序算法,在每次迭代过程中算法随机的从输入序列中移除一个元素,并将该元素插入到排序序列中正确的位置,重复该过程,知道所有元素都被选择一次。

总结Java常用排序算法

 

2、

 

private static void sorter(int[] array)     for(int i=1;i<array.length;i++) {      int temp = array[i];      int j = i;      while(j>0&&temp<array[j-1]) {        array[j] = array[j-1];        j--;      }      array[j] = temp;    }  }

总结Java常用排序算法

3、运行结果

总结Java常用排序算法

1、希尔排序

希尔排序(ShellSort)又称缩小增量排序,该算法是一个泛化的插入排序。

总结Java常用排序算法

2、

public static void sorter(int[]array) {    for(int gap=array.length/2;gap>0;gap/=2) {      for(int i=gap;i<array.length;i++) {        int temp = array[i];        int j = i;        if(array[j]<array[j-1]) {          while(j-gap>=0&&temp<array[j-gap]) {            array[j] = array[j-gap];            j-=gap;          }          array[j] = temp;        }      }    }  }

 

总结Java常用排序算法

3、运行结果

总结Java常用排序算法

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

冒泡排序介绍

冒泡排序(Bubble Sort),又被称为气泡排序或泡沫排序。

它是一种较简单的排序算法。它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小;如果前者比后者大,则交换它们的位置。这样,一次遍历之后,最大的元素就在数列的末尾! 采用相同的方法再次遍历时,第二大的元素就被排列在最大元素之前。重复此操作,直到整个数列都有序为止!

冒泡排序图文说明

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

/*
	  *   a -- 待排序的数组
	  *   n -- 数组的长度
	  */
	  public static void bubbleSort(int[] a, int n) {
	    int i,j;
 
	    for (i=n-1; i>0; i--) {
	      // 将a[0...i]中最大的数据放在末尾
	      for (j=0; j<i; j++) {
 
	        if (a[j] > a[j+1]) {
	          // 交换a[j]和a[j+1]
	          int tmp = a[j];
	          a[j] = a[j+1];
	          a[j+1] = tmp;
	        }
	      }
	    }
	   
	  }

运行:

int[] a = {20,40,30,10,60,50,70};
    String aa = "冒泡排序";
    bubbleSort(a,a.length);
 
 System.out.print(aa);
 for (int d : a) {
  System.out.print(d+",");
}

快速排序介绍

快速排序(Quick Sort)使用分治法策略。

它的基本思想是:选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序流程:

  1. 从数列中挑出一个基准值。
  2. 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边);在这个分区退出之后,该基准就处于数列的中间位置。
  3. 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
  4. 图文介绍

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

代码实现:

/**
	  *
	  * 参数说明:
	  *   a -- 待排序的数组
	  *   l -- 数组的左边界(例如,从起始位置开始排序,则l=0)
	  *   r -- 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)
	  */
	  public static void quickSort(int[] a, int l, int r) {
 
	    if (l < r) {
	      int i,j,x;
 
	      i = l;
	      j = r;
	      x = a[i];
	      while (i < j) {
	        while(i < j && a[j] > x)
	          j--; // 从右向左找第一个小于x的数
	        if(i < j)
	          a[i++] = a[j];
	        while(i < j && a[i] < x)
	          i++; // 从左向右找第一个大于x的数
	        if(i < j)
	          a[j--] = a[i];
	      }
	      a[i] = x;
	      quickSort(a, l, i-1); /* 递归调用 */
	      quickSort(a, i+1, r); /* 递归调用 */
	    }
	   
	  }

运行:

      String aa = "快速排序";
	    quickSort(a,0,a.length-1);
	    
 
	    
	    System.out.print(aa);
	    for (int d : a) {
	  	  System.out.print(d+",");
		  }

直接插入排序介绍

直接插入排序(Straight Insertion Sort)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

直接插入排序图文说明

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

代码实现:

 /**
	  * @param 
	  *   a -- 待排序的数组
	  *   n -- 数组的长度
	  */
	  public static void insertSort(int[] a, int n) {
    int i, j, k;
 
    for (i = 1; i < n; i++) {
 
      //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
      for (j = i - 1; j >= 0; j--)
        if (a[j] < a[i])
          break;
 
      //如找到了一个合适的位置
      if (j != i - 1) {
        //将比a[i]大的数据向后移
        int temp = a[i];
        for (k = i - 1; k > j; k--)
          a[k + 1] = a[k];
        //将a[i]放到正确位置上
        a[k + 1] = temp;
      }
    }
  }

运行和冒泡一样。。。。。

希尔排序:

希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。该方法因DL.Shell于1959年提出而得名。

希尔排序的基本思想是:

把记录按步长 gap 分组,对每组记录采用直接插入排序方法进行排序。

随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。

我们来通过演示图,更深入的理解一下这个过程。

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

在上面这幅图中:

初始时,有一个大小为 10 的无序序列。

在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组。接下来,按照直接插入排序的方法对每个组进行排序。

在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。按照直接插入排序的方法对每个组进行排序。

在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。

需要注意一下的是,图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到,在排序过程中,两个元素位置交换了。

所以,希尔排序是不稳定的算法。

代码实现:

/**
	  	 * 希尔排序
	  	 * @param list
	  	 */
	  public static void shellSort(int[] a) {
	    int gap = a.length / 2;
 
	    while (1 <= gap) {
	      // 把距离为 gap 的元素编为一个组,扫描所有组
	      for (int i = gap; i < a.length; i++) {
	        int j = 0;
	        int temp = a[i];
 
	        // 对距离为 gap 的元素组进行排序
	        for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {
	          a[j + gap] = a[j];
	        }
	        a[j + gap] = temp;
	      }
 
	      System.out.format("gap = %d:\t", gap);
	      printAll(a);
	      gap = gap / 2; // 减小增量
	    }
	  }
	  // 打印完整序列
	  public static void printAll(int[] a) {
	    for (int value : a) {
	      System.out.print(value + "\t");
	    }
	    System.out.println();
	  }

运行参考冒泡、、、、、

拓扑排序介绍

拓扑排序(Topological Order)是指,将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

这样说,可能理解起来比较抽象。下面通过简单的例子进行说明!

例如,一个项目包括A、B、C、D四个子部分来完成,并且A依赖于B和D,C依赖于D。现在要制定一个计划,写出A、B、C、D的执行顺序。这时,就可以利用到拓扑排序,它就是用来确定事物发生的顺序的。

在拓扑排序中,如果存在一条从顶点A到顶点B的路径,那么在排序结果中B出现在A的后面。

拓扑排序的算法图解

拓扑排序算法的基本步骤:

1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological);

2. 把所有没有依赖顶点的节点放入Q;

3. 当Q还有顶点的时候,执行下面步骤:

3.1 从Q中取出一个顶点n(将n从Q中删掉),并放入T(将n加入到结果集中);

3.2 对n每一个邻接点m(n是起点,m是终点);

3.2.1 去掉边<n,m>;

3.2.2 如果m没有依赖顶点,则把m放入Q;

注:顶点A没有依赖顶点,是指不存在以A为终点的边。

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

以上图为例,来对拓扑排序进行演示。

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

第1步:将B和C加入到排序结果中。

顶点B和顶点C都是没有依赖顶点,因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储,因此先访问B,再访问C。访问B之后,去掉边<B,A>和<B,D>,并将A和D加入到队列Q中。同样的,去掉边<C,F>和<C,G>,并将F和G加入到Q中。

将B加入到排序结果中,然后去掉边<B,A>和<B,D>;此时,由于A和D没有依赖顶点,因此并将A和D加入到队列Q中。

将C加入到排序结果中,然后去掉边<C,F>和<C,G>;此时,由于F有依赖顶点D,G有依赖顶点A,因此不对F和G进行处理。

第2步:将A,D依次加入到排序结果中。

第1步访问之后,A,D都是没有依赖顶点的,根据存储顺序,先访问A,然后访问D。访问之后,删除顶点A和顶点D的出边。

第3步:将E,F,G依次加入到排序结果中。

因此访问顺序是:B -> C -> A -> D -> E -> F -> G

拓扑排序的代码说明

拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。

1. 基本定义

public class ListDG {
  // 邻接表中表对应的链表的顶点
  private class ENode {
    int ivex;    
    // 该边所指向的顶点的位置
    ENode nextEdge; 
    // 指向下一条弧的指针
  }
 
  // 邻接表中表的顶点
  private class VNode {
    char data;     
    // 顶点信息
    ENode firstEdge;  
    // 指向第一条依附该顶点的弧
  };
 
  private VNode[] mVexs; 
  // 顶点数组
 
  ...
}
  1. ListDG是邻接表对应的结构体。 mVexs则是保存顶点信息的一维数组。
  2. VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据,而firstEdge是该顶点所包含链表的表头指针。
  3. ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引,而nextEdge是指向下一个节点的。

2. 拓扑排序

/*
* 拓扑排序
*
* 返回值:
*   -1 -- 失败(由于内存不足等原因导致)
*   0 -- 成功排序,并输入结果
*   1 -- 失败(该有向图是有环的)
*/
public int topologicalSort() {
  int index = 0;
  int num = mVexs.size();
  int[] ins;        
  // 入度数组
  char[] tops;       
  // 拓扑排序结果数组,记录每个节点的排序后的序号。
  Queue<Integer> queue;  
  // 辅组队列
 
  ins  = new int[num];
  tops = new char[num];
  queue = new LinkedList<Integer>();
 
  // 统计每个顶点的入度数
  for(int i = 0; i < num; i++) {
 
    ENode node = mVexs.get(i).firstEdge;
    while (node != null) {
      ins[node.ivex]++;
      node = node.nextEdge;
    }
  }
 
  // 将所有入度为0的顶点入队列
  for(int i = 0; i < num; i ++)
    if(ins[i] == 0)
      queue.offer(i);         
      // 入队列
 
  while (!queue.isEmpty()) {       
  // 队列非空
    int j = queue.poll().intValue();  
    // 出队列。j是顶点的序号
    tops[index++] = mVexs.get(j).data; 
    // 将该顶点添加到tops中,tops是排序结果
    ENode node = mVexs.get(j).firstEdge;
    // 获取以该顶点为起点的出边队列
 
    // 将与"node"关联的节点的入度减1;
    // 若减1之后,该节点的入度为0;则将该节点添加到队列中。
    while(node != null) {
      // 将节点(序号为node.ivex)的入度减1。
      ins[node.ivex]--;
      // 若节点的入度为0,则将其"入队列"
      if( ins[node.ivex] == 0)
        queue.offer(node.ivex);  
        // 入队列
 
      node = node.nextEdge;
    }
  }
 
  if(index != num) {
    System.out.printf("Graph has a cycle\n");
    return 1;
  }
 
  // 打印拓扑排序结果
  System.out.printf("== TopSort: ");
  for(int i = 0; i < num; i ++)
    System.out.printf("%c ", tops[i]);
  System.out.printf("\n");
 
  return 0;
}

说明:

  1. queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的Q相对应。
  2. tops的作用就是用来存储排序结果。它与前面所说的T相对应。

归并排序

基本思想

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

分而治之

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

合并相邻有序子序列

再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)

代码实现

package sortdemo;
 
import java.util.Arrays;
 
/**
* Created by chengxiao on 2016/12/8.
*/
public class MergeSort {
 public static void main(String []args){
   int []arr = {9,8,7,6,5,4,3,2,1};
   sort(arr);
   System.out.println(Arrays.toString(arr));
 }
 public static void sort(int []arr){
   int []temp = new int[arr.length];
   //在排序前,先建好一个长度等于原数组长度的临时数组,
   //避免递归中频繁开辟空间
   sort(arr,0,arr.length-1,temp);
 }
 private static void sort(int[] arr,int left,int right,int []temp){
   if(left<right){
     int mid = (left+right)/2;
     sort(arr,left,mid,temp);
     //左边归并排序,使得左子序列有序
     sort(arr,mid+1,right,temp);
     //右边归并排序,使得右子序列有序
     merge(arr,left,mid,right,temp);
     //将两个有序子数组合并操作
   }
 }
 private static void merge(int[] arr,int left,int mid,int right,int[] temp){
   int i = left;//左序列指针
   int j = mid+1;//右序列指针
   int t = 0;//临时数组指针
   while (i<=mid && j<=right){
     if(arr[i]<=arr[j]){
       temp[t++] = arr[i++];
     }else {
       temp[t++] = arr[j++];
     }
   }
   while(i<=mid){//将左边剩余元素填充进temp中
     temp[t++] = arr[i++];
   }
   while(j<=right){//将右序列剩余元素填充进temp中
     temp[t++] = arr[j++];
   }
   t = 0;
   //将temp中的元素全部拷贝到原数组中
   while(left <= right){
     arr[left++] = temp[t++];
   }
 }
}

最后

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

以上就是本次给大家分享的全部知识点内容总结,大家还可以在下方相关文章里找到儿童python编程入门书籍推、 解决axios.interceptors.respon、 vue项目中使用md5加密以及、 等java文章进一步学习,感谢大家的阅读和支持。

上一篇:Java获取文件路径出现乱码的问题的解决方法

下一篇:Spring Cloud几行配置完成单点登录开发实例讲解

展开 +

收起 -

学习笔记
网友NO.854760

java排序算法之_选择排序(实例讲解)

选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列。整个排序过程只需要遍历 n-1 趟便可排好,最后一个元素自动为最大(最小)值。 举个小例子: arr[] = {3,1,2,6,5,4} 第 1 趟排序: index = 0, min = 1, 交换后 -- 1,3,2,6,5,4 第 2 趟排序: index = 1, min = 2, 交换后 -- 1,2,3,6,5,4 第 3 趟排序: index = 2, min = 2, 交换后 -- 1,2,3,6,5,4 第 4 趟排序: index = 3, min = 5, 交换后 -- 1,2,3,4,5,6 第 5 趟排序: index = 4, min = 4, 交换后 -- 1,2,3,4,5,6 核心代码如下: /** * 选择排序,从小到大排序 */ public static void selectsort(int[] arr) { int min = 0; //记录最小值的索引 //遍历 n-1 轮,最后一个数不用遍历比较 for(int i = 0; i arr.length - 1; i++) { min = i; //初始最小值为每轮循环的第一个数 //遍历初始最小值后的所有数 for(int j = i + 1; j arr.length; j++) { if(arr[min] arr[j]) { //判断是否存在比最小值小的数 min = j; //记录下标 } } if(min != i) { //判断最小值的索引是否等于初始最小值的索引 int temp = arr[min]; //不是则进行最小值交换 arr[min] = arr[i]; arr[i] = temp; } } } 选择排序算法是一种不稳定的算法,它的时间……

网友NO.494244

图文详解Heap Sort堆排序算法及JavaScript的代码实现

1. 不得不说说二叉树 要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点;深度为 k 的二叉树至多有 2k - 1 个结点;对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1。 树和二叉树的三个主要差别: 树的结点个数至少为 1,而二叉树的结点个数可以为 0 树中结点的最大度数没有限制,而二叉树结点的最大度数为 2 树的结点无左、右之分,而二叉树的结点有左、右之分 二叉树又分为完全二叉树(complete binary tree)和满二叉树(full binary tree) 满二叉树:一棵深度为 k,且有 2k - 1 个节点称之为满二叉树 (深度为 3 的满二叉树 full binary tree) 完全二叉树:深度为 k,有 n 个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时,称之为完全二叉树 (深度为 3 的完全二叉树 complete binary tree) 2. 什么是堆? 堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的……

网友NO.264135

基于JavaScript实现的希尔排序算法分析

本文实例讲述了基于JavaScript实现的希尔排序算法。分享给大家供大家参考,具体如下: 通过对直接插入排序的分析,可知其时间复杂度为O(n2),但是,如果待排序序列为正序时,其时间复杂度可提高至O(n)。希尔排序正是对此进行改进的排序。 希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻元素。通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔 。 下图演示了希尔排序中间隔序列是如何运行的: 下面我们通过js来实现希尔排序,代码如下: !DOCTYPE htmlhtmlheadmeta charset="utf-8"titleJavaScript希尔排序/title/headbodyscript type="text/javascript" function shellSort(nums){//希尔排序 var gaps=[5,3,1];//定义间隔区间 for(var g=0;ggaps.length;g++){//一个一个间隔值开始 for(var i=gaps[g];inums.length;i++){//以间隔值遍历 var temp=nums[i];//选中元素 for(var j=i;j=gaps[g]nums[j-gaps[g]]temp;j-=gaps[g]){//如果前面一个大于后面一个 nums[j]=nums[j-gaps[g]];//后移 } nums[j]=temp;//填补 } } } function show(nums){//显示数组 for(var i=0;inums.length;i++){ document.write(nums[i]+' '); } document.write('br'); } var nums=[6,0,2,9,3,5,8,0,5,4]; show(nums);//6 0 2 9 3 5 8 0 5 4 shellSort(nums);//希尔排序 show(nums);//0 0 2 3 4 5 5 6 8 9/script/body/html 其排序过程如下: 希尔排序根据间隔序列的选取不……

网友NO.928314

Java排序算法之归并排序简单实现

算法描述:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到 n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列。 package sorting;/** * 归并排序 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂 * @author zeng * */public class MergeSort {public static void merge(int[] a, int start, int mid, int end) {int[] tmp = new int[a.length];System.out.println("merge " + start + "~" + end);int i = start, j = mid + 1, k = start;while (i != mid + 1 j != end + 1) {if (a[i] a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++];}while (i != mid + 1) tmp[k++] = a[i++];while (j != end + 1) tmp[k++] = a[j++];for (i = start; i = end; i++) a[i] = tmp[i];for (int p : a) System.out.print(p + " ");System.out.println();}static void mergeSort(int[] a, int start, int end) {if (start end) {int mid = (start + end) / 2;mergeSort(a, start, mid);// 左边有序mergeSort(a, mid + 1, end);// 右边有序merge(a, start, mid, end);}}public static void main(String[] args) {int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };mergeSort(b, 0, b.length - 1);}} 运行结果看一下: 总结 以上就是本文关于Java排序算法之归并排序简单实现的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持! ……

<
1
>

Copyright 2018-2019 xz577.com 码农之家

版权责任说明