十种排序算法理解（前五）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
算法描述：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
代码
package sort.bubbling;
/**
* 冒泡排序
* @author LENOVO
*/
public class Bubbling {
public static void main(String[] args) {
int a[]= {2,1,3,9,5,6,4,7,8};
for(int i=0;i<a.length;i++)
for(int j=i+1;j<a.length;j++)
if(a[i]>a[j]) {
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
for(int i=0;i<a.length;i++)
System.out.print(a[i] + " ");
}
}选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
代码
package sort.chose;
/**
* 选择排序
* @author LENOVO
*/
public class Chose {
public static void main(String[] args) {
int a[]= {2,1,3,9,5,6,4,7,8},index=-1,step;
for(int i=0;i<a.length;i++) {
step=a[i];
for(int j=i+1;j<a.length;j++)
if(step>a[j]) {
step=a[index=j];
}
if(index!=-1) {
a[i]=a[i]+a[index];
a[index]=a[i]-a[index];
a[i]=a[i]-a[index];
}
index=-1;
}
for(int i=0;i<a.length;i++)
System.out.print(a[i] + " ");
}
}插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
代码
package sort.insert;
/**
* 插入排序
* @author LENOVO
*/
public class Insert {
public static void main(String[] args) {
int a[]= {2,1,3,9,5,6,4,7,8},index, current;
for (int i = 1; i < a.length; i++) {
index = i - 1;
current = a[i];
while (index >= 0 && a[index] > current) {
a[index + 1] = a[index];
index--;
}
a[index + 1] = current;
}
for(int i=0;i<a.length;i++)
System.out.print(a[i] + " ");
}
}希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
算法描述
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
代码：
package sort.shell;
/***
* 希尔排序
* @author LENOVO
*/
public class Shell {
public static void main(String[] args) {
int a[]= {4,5,6,1,2,3,7,8,9,0},increment =a.length,temp=0,j;
do {
increment = (int) Math.ceil((double)(increment)/3l);//每次减小增量，直到increment = 1
for (int i =increment; i < a.length; ++i)//对每个划分进行直接插入排序
if (a[i - increment] > a[i]) {
temp = a[i];
j= i - increment;
do { //移动元素并寻找位置
a[j + increment] = a[j];
j -= increment;
} while (j >= 0 && a[j] > temp);
a[j + increment] = temp; //插入元素
}
} while (increment > 1);
for(int i=0;i<a.length;i++)
System.out.print(a[i] + " ");
}
}归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
代码：
package sort.merge;
/**
* 归并排序
* @author LENOVO
*/
public class Merge{
private static int[] result;
private static int[] arr;
static int s=0;//标记变量
static int step=0;//递归深度
//递归函数
public static void sort(int begin ,int end) {
if(end - begin <= 1) {//开始数据和结束数据是相邻数据时，不需要递归
if(arr[begin] > arr[end]) {
arr[begin] = arr[begin]+arr[end];//交换数据
arr[end] =arr[begin] - arr[end];
arr[begin] =arr[begin]-arr[end];
}
}else {
int mid = (begin + end)/2;//
s++;
if(s>step) {//计算递归深度
step=s;
}
sort(begin ,mid);//数据的左半边进行递归排序
sort(mid+1 ,end);//数据的右半边进行递归排序
s--;
mergeSort(begin ,mid ,end);//对数组的两个区间进行排序
}
}
//排序函数
public static void mergeSort(int begin ,int mid ,int end) {
int i = begin;
int j = mid+1;
int index = begin;
while(i <= mid && j <= end) {
if(arr[i] > arr[j])
result[index++] = arr[j++];
else
result[index++] = arr[i++];
}
if(j > end)//说明排序数据左区间有数据还未复制
for(;i < mid+1;i++)
result[index++] = arr[i];//复制数据
else//说明排序数据右区间有数据还未复制
for(;j < end+1;j++)
result[index++] = arr[j];
for(i=begin ;i<end+1 ;i++)//把已经排序好的数据重新复制到arr数组
arr[i] = result[i];//复制数据
}
public static void main(String[] args) {
arr= new int[]{4,5,6,1,2,3,7,8,9,0};
result=new int[arr.length];
sort(0, arr.length-1);
for(int i=0;i<result.length;i++)
System.out.print(result[i] + " ");
System.out.println();
System.out.println("递归深度："+step);
}
}如需要时间空间复杂度，请自行百度
参照文章：https://www.cnblogs.com/onepixel/articles/7674659.html
理解万岁！