十种排序算法理解（前五）

1.冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

算法描述：

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

• 针对所有的元素重复以上的步骤，除了最后一个；

• 重复步骤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] + " ");
	}
}

2.选择排序

选择排序(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] + " ");
	}
}

3.插入排序

插入排序（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] + " ");
	}
}

4.希尔排序

希尔(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] + " ");
	}
}

5.归并排序：

归并排序（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

理解万岁！