排序算法

介绍

排序的分类

内部排序：将处理的数据都加载到内部存储器进行排序

插入排序
（1）直接插入排序
（2）希尔排序
选择排序
（1）简单选择排序
（2）堆排序
交换排序
（1）冒泡排序
（2）快速排序
归并排序
基数排序

外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储（文件等进行排序

算法解析

冒泡排序

基本思想：
对于一个序列，从前往后（小下标到大下标）,依次比较相邻的值，若发现逆序则交换，使较大的值慢慢浮出水面，就像冒泡一样。
举例说明

原始数组：{3，9，-1，5，10}

第一趟排序（交换4次）：
从index=0，依次相邻的进行比较，若前面的比后面的大，则交换，即：

{3,9} ——> {9,-1} ——> {9,5} ——> {9,10}

得到排序的数组：

{3，-1，5，9，10}

根据第一趟排序，最大的数浮出水面（位于数组的最后）。

第二趟排序（交换3次）
经过第一次排序，最大的数已经固定，因此我们只需要对前面4个数进行排序，交换同样按照相同的方法，得：

{-1，3，5，9，10}

依次类推…

第三趟排序（交换2次）
需要对前面3个数进行排序，得：

{-1，3，5，9，10}

第四趟排序（交换1次）
对前面2个数进行排序，同样得：

{-1，3，5，9，10}

经过四趟排序，一个个数都浮出水面，此时我们便完成了排序，根据上面得规律，我们可以针对算法总结如下规律（模板）：

共进行了数组长度-1次的大循环（如上长度为5，一共走了4趟）；
每次大循环之间交换的次数在逐渐减少1次；

示例代码
故根据上述总结，代码如下：

//冒泡排序
//arr:待排序的数组
public static void bubbleSort(int[] arr){
	//大循环:数组的长度-1
	for(int i = 0;i < arr.length- 1;i++){
		//小循环：交换次数，逐渐减少
		for(int j = 0;j < arr.length - 1 - i;j++){
			//若逆序，则交换，从小到大排序
			//从大到小：arr[j] < arr[j+1]
			if(arr[j] >= arr[j+1]){
				//交换
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] =  temp;
			} 
		}
	}
}

代码优化
我们可以从上面的示例看出，在第二趟排序之后，其实数组排序已经完成，因此是无需后面几趟，这里就是优化的点，我们可以对代码进行优化，从而判断当数组已经排序完成，则直接中止，无需后面的交换。
方法
设置标志位flag，若判断此趟中出现交换，则flag=true，否则表示此次未出现交换，排序已完成，直接退出循环。
具体代码实现

//冒泡排序
//arr:待排序的数组
public static void bubbleSort(int[] arr){
	//设置标志位,初始值为flase，;
	boolean flag = false;
	//大循环:数组的长度-1
	for(int i = 0;i < arr.length- 1;i++){
		//小循环：交换次数，逐渐减少
		for(int j = 0;j < arr.length - 1 - i;j++){
			//若逆序，则交换，从小到大排序
			//从大到小：arr[j] < arr[j+1]
			if(arr[j] >= arr[j+1]){
				//出现交换，令flag = true;
				flag = true;
				//交换
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] =  temp;
			} 
		}
		//检查flag，判断是否出现交换
		if(!flag）{ //未出现交换，结束
			break;
		}else{     //出现交换，重置flag
		   flag = false;
		}
	}
}