疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java常用排序算法


 

  

  Java常用排序算法(插入排序,快速排序,归并排序)

  插入排序

  插入排序的概念比较简单,就像平时玩扑克一样,将后面来的数插入到前面序列中,在插入的时候我们默认前面的序列已经是有序的。

  public class InsertSort {

  public static void insertSort(int[] a){

  int i, j;

  int n =a.length;

  int target;

  for (i = 1; i < n; i++) {

  j = i;

  target = a[i];

  while (j > 0 && target < a[j-1])

  {

  a[j] = a[j-1];

  j--;

  }

  a[j] = target;

  }

  }

  public static void main(String[] args){

  int[] a={1,5,9,4,10,8,7};

  insertSort(a);

  for(int i= 0;i

  System.out.print(a[i]+",");

  }

  }

  }

  快速排序

  快速排序是一种选择排序,在序列中选取一个中间值,是左边的数全部不大于(不小于)这个中间值,右边的数全部不小于(不大于)这个数。使整个序列分成左右两个分序列,然后以递归的方式,使两边的数据集按上述规则处理,直到数据集的元素数不少于一个。

  public class QuickSort {

  public static int gerMark(int[] a, int left ,int right){

  int mark = a[left];

  while(left

  while(left

  right--;

  }

  a[left]=a[right];

  while(left

  left++;

  }

  a[right]=a[left];

  }

  a[left]= mark;

  return left;

  }

  public static void quickSort(int[] a, int left ,int right){

  if(left

  int middle = gerMark(a,left,right);

  quickSort(a,left,middle-1);

  quickSort(a,middle+1,right);

  }

  }

  public static void main(String[] args){

  int[] a={7,2,5,4,12};

  quickSort(a,0,a.length-1);

  for(int i= 0;i

  System.out.print(a[i]+",");

  }

  }

  }

  归并排序

  归并排序也是以递归的方式进行排序,但是它是插入排序的延伸,我们要以递归的逆过程和插入排序的二维插入(插入排序是一个一个插入,归并排序是一组数据插入另一组数据)来思考,首先可以想象,整个序列相当于一个根节点,经过不断地递归划分成为一个二叉树,直到每个节点都只有一个元素,再一层一层地向上进行二维的插入排序。

  public class MergeSort {

  public static int[] mergeSort(int[] a, int left,int right){

  int middle = (left+right)/2;

  if(left

  mergeSort(a,left,middle);

  mergeSort(a,middle+1,right);

  merge(a,left,middle,right);

  }

  return a;

  }

  public static void merge(int[] a ,int left ,int middle,int right){

  int[] temp = new int[right-left+1];

  int i=left;

  int j=middle+1;

  int k=0;

  while(i<=middle&&j<=right){

  if(a[i]

  temp[k++]=a[i++];

  }

  else{

  temp[k++]=a[j++];

  }

  }

  while(i<=middle){

  temp[k++]=a[i++];

  }

  while(j<=right){

  temp[k++]=a[j++];

  }

  for(int m=0;m

  a[left+m] = temp[m];

  }

  }

  public static void main(String[] args){

  int[] a={8,99,37,10,51,109};

  mergeSort(a,0,a.length-1);

  for(int i= 0;i

  System.out.print(a[i]+",");

  }

  }

  }