Java常用排序算法（插入排序，快速排序，归并排序）

插入排序

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

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 {publicstatic 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