未加星标

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

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二03 | 时间 20161001 | 作者 红领巾 ] 0人收藏点击收藏
插入排序

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

public class InsertSort {
publicstaticvoidinsertSort(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;
}
}
publicstaticvoidmain(String[] args){
int[] a={1,5,9,4,10,8,7};
insertSort(a);
for(int i= 0;i<a.length;i++){System.out.print(a[i]+",");
}
}
}
快速排序

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

public class QuickSort {
publicstaticintgerMark(int[] a, int left ,int right){
int mark = a[left];
while(left<right){while(left<right&&mark<a[right]){ right--;}a[left]=a[right];while(left<right&&mark>a[right]){ left++;}a[right]=a[left];
}
a[left]= mark;
return left;
}

publicstaticvoidquickSort(int[] a, int left ,int right){
if(left<right){int middle = gerMark(a,left,right);quickSort(a,left,middle-1);quickSort(a,middle+1,right);
}
}

publicstaticvoidmain(String[] args){

int[] a={7,2,5,4,12};
quickSort(a,0,a.length-1);
for(int i= 0;i<a.length;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<right){mergeSort(a,left,middle);mergeSort(a,middle+1,right);merge(a,left,middle,right);
}
return a;
}

publicstaticvoidmerge(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]<a[j]){ 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<temp.length;m++){a[left+m] = temp[m];
}
}

publicstaticvoidmain(String[] args){
int[] a={8,99,37,10,51,109};
mergeSort(a,0,a.length-1);
for(int i= 0;i<a.length;i++){System.out.print(a[i]+",");
}
}
}

本文地址:http://www.linuxidc.com/Linux/2016-10/135740.htm


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

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: 算法JavaLinux数据
分页:12
转载请注明
本文标题:Java常用排序算法(插入排序,快速排序,归并排序)
本站链接:http://www.codesec.net/view/483430.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(15)