简单排序算法(冒泡排序、选择排序、插入排序)

简单排序算法(冒泡排序、选择排序、插入排序)

一、冒泡排序

1、介绍：

冒泡排序和选择排序的思想是蛮力法，冒泡，顾名思义，每次选择后面一个元素（最大或者最小）冒上来，从而得到一个有序的序列。比如对于序列：10、8、5、7、3、1的冒泡第一趟演示图示如图所示

可见第一趟过后做大元素10已经沉底，第二趟就对另外的8、5、7、3、1进行上述同样的比较冒泡，会使得最大元素8沉底，...... ，最终可得到一个有序序列。

2、代码实现（Java）：

	/**
	 * 冒泡排序
	 *@author DR
	 * @param args
	 * @return
	 *2014年1月14日
	 */
	public int[] bubbleSort(int...args){ //这里使用JDK提供的可变参数作可变数组
		for(int i=0;i<args.length-1;i++){  
			for(int j=args.length-1;j>i;j--){  //这里从右向左扫描
				if(args[j]<args[j-1]){
					int temp = args[j];
					args[j] = args[j-1];
					args[j-1] = temp;
				}
			}
		}
		return args;
	}

程序中有两个for循环，在args[i]左边的元素是已经沉底的，排序好了的元素；j作为一个扫描指针，从右向左扫描，如果j-1位置的大于j位置的元素，则交换它们，直到把最小的那个元素沉底到i+1位置。

3、代码优化

对于上述代码，可以发现对于一个大部分有序的序列来说，上面的做法很多步骤是徒劳的不会产生有效的交换，所以，我们想到可以加一个标志位，来标志一趟扫描过后是否发生交换，如果未发生交换，则说明序列已经有序，无需再继续下去

优化后的代码：

	/**
	 * 冒泡排序的优化算法
	 *@author DR
	 * @param args
	 * @return
	 *2014年1月14日
	 */
	public int[] bubbleSort2(int...args){
		boolean flag = true;   //是否交换标志位
		for(int i=0;i<args.length-1&&flag;i++){
			flag = false;
			for(int j=args.length-1;j>i;j--){
				if(args[j]<args[j-1]){
					int temp = args[j];
					args[j] = args[j-1];
					args[j-1] = temp;
					flag = true;   //发生交换则让标志位为真
				}
			}
		}
		return args;
	}

测试一下，对于一个大部分有序的序列，优化后的算法比之前的算法要节省很多步。
测试方法：

public static void main(String[] args) {
		TestBubbleSort t = new TestBubbleSort();
		//int[] array = t.bubbleSort(1,3,4,7,9,5,23,2);
		int[] array = t.bubbleSort2(1,3,4,7,9,5,23,2);
		for(int i:array){
			System.out.println(i);
		}
	}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

二、选择排序

1、介绍：

选择排序开始的时候，我们扫描整个待排序列表，找到最小的那一个，并与第一位的元素进行交换；接着，扫描第2~n位的共n-1个元素，找到最小的那一个，并与第2位的元素进行交换；以此类推，........；最后，扫描第n-1~n位的共2个元素，找到最小的那一个，并与第n-1位的元素进行交换。至此，扫描结束排序完毕，得到了一个非递减列表。

下面以一个整形数组作为待排序列表，描述上述的选择排序过程：

待排序整形数组：6、4、9、1、4、12

第一次：扫描整个列表，找到最小的元素，也就是1，过程如下

扫描第一个元素6，最小元素6，最小元素索引0

扫描第一个元素4，与最小元素6比较，6不小于4，所以，最小元素4，最小元素索引1

扫描第一个元素9，与最小元素4比较，9不小于4，所以，最小元素4，最小元素索引1

扫描第一个元素1，与最小元素4比较，1小于4， 所以，最小元素1，最小元素索引3

扫描第一个元素4，与最小元素1比较，4不小于1， 所以，最小元素1，最小元素索引3

扫描第一个元素12，与最小元素1比较，12不小于1， 所以，最小元素1，最小元素索引3

扫描结束，最小元素1，最小元素索引3，将1与6交换，得到序列：1、4、9、6、4、12

第二次：扫描第2~6位的元素，也就是4、9、6、4、12

扫描第一个元素4，最小元素4，最小元素索引1

扫描第一个元素9，与最小元素4比较，9不小于4，所以，最小元素4，最小元素索引1

扫描第一个元素6，与最小元素4比较，6不小于4，所以，最小元素4，最小元素索引1

扫描第一个元素4，与最小元素4比较，4不小于4， 所以，最小元素4，最小元素索引1

扫描第一个元素12，与最小元素4比较，12不小于4， 所以，最小元素4，最小元素索引1

扫描结束，最小元素4，最小元素索引1，将4与4交换，得到序列：1、4、9、6、4、12

第三次：以此类推，得到1、4、4、6、9、12

第四次：以此类推，得到1、4、4、6、9、12

第五次：以此类推，得到1、4、4、6、9、12

全部扫描结束，排序完成，得到非递减序列：1、4、4、6、9、12

2、代码实现(Java)：

	/**
	 * 选择排序的Java代码实现
	 *@author DR
	 * @param args
	 * @return
	 *2014年1月14日
	 */
	public int[] selectSort(int...args){  //这里使用JDK提供的可变参数作可变数组
		for(int i=0;i<args.length-1;i++){
			for(int j=i+1;j<args.length;j++){
				if(args[i]>args[j]){
					int temp = args[i];
					args[i] = args [j];
					args[j] = temp;
				}
			}
		}
		return args;
	}

程序中有两个for循环，j=i+1作为扫描指针，若i位置的元素大于j位置的元素，则把两者交换，并使j+1,这样当 j 扫描到末尾结束后，i位置上的元素就是本次扫描中最小的那一个，然后i+1。最终，可得一个非递减的序列。但是我们发现上述代码做了很多次元素的交换，而交换元素又是费时费力的，所以改良后的代码是在扫描的过程中不急于做元素的交换，而是用一个变量记下最小元素的位置，更新一个变量的值比做一次元素交换要容易的做，最后将最小元素与i位置的元素交换，这样整个过程我们至多做一次交换。

3、优化后的选择排序算法的Java代码实现：

	/**
	 * 优化后的选择排序Java代码实现
	 *@author DR
	 * @param args
	 * @return
	 *2014年1月14日
	 */
	public int[] selectSort2(int...args){
		int k,num = 0;
		for(int i=0;i<args.length-1;i++){
			k = i;   //设置k变量的目的是为了减少交换的次数，把交换改为对k赋值，每趟循环至多交换1次
			for(int j=i;j<args.length;j++){
				if(args[k]>args[j]){
					k = j;  
				}
			}
			if(k != i){
				int temp = args[k];
				args[k] = args[i];
				args[i] = temp;
			}
		}
		return args;
	}

测试代码：虽然优化后的代码和之前的代码复杂度一样，但是对于一个大量数据的排序其运行时间比之前的代码要少很多。

public static void main(String[] args) {
		TestSelectSort ts = new TestSelectSort();
		//TestSelectSort ts = new TestSelectSort2();
		int[] array = ts.selectSort(5,3,8,2,15,2,11,0);
		for(int i:array){
			System.out.println(i);
		}
	}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

三、插入排序

1、介绍：

对于一个含有n个元素的序列，对它的插入排序的过程是这样的，我们区第一个元素，它一定是有序的（因为只有一个元素），将第二个元素插入到这个有序序列中去（也就是和第一个元素比较，然后插入），再将第3个元素插入到前面；两个元素组成的有序序列中去，.......，最后将第n个元素插入到由前面（n-1）个元素组成的有序序列中去，可以发现这是减治思想的一种体现。

2、插入排序代码实现：

	/**
	 * 插入排序的Java代码实现
	 *@author DR
	 * @param args
	 * @return
	 *2014年1月14日
	 */
	public int[] insertSort(int...args){  //这里使用JDK提供的可变参数作可变数组
		for(int i=1;i<args.length;i++){
			if(args[i-1]>args[i]){
				int key = args[i];
				int j=i-1;
				for(;j>=0 && args[j]>key;j--){
					args[j+1] = args[j];
				}
				args[j+1] = key;
			}
		}
		return args;
	}

注意一点：事实上，插入排序一共有三种：①我们可以从左向右扫描序列，找到合适的位置插入； ②我们可以从右向左扫描序列，找到合适的位置插入；③对于有序序列我们可以使用折半查找到合适的位置插入。 这里由于不知道序列是否有序，我们采用第②中插入法，事实上，很多像这种对数组的排序都采用第②中方法，因为它可以在比较查找的过程中移动腾空位置，比第一种要少做一次循环，这一点可以去验证一下。

总结：之所以是简单排序，因为这三种排序的算法相对简单，最好、最坏、平均情况的时间复杂度都是O(n²)。