Java基础复习笔记11基本排序算法

1.       排序

排序是一个历来都是很多算法家热衷的领域，到现在还有很多数学家兼计算机专家还在研究。而排序是计算机程序开发中常用的一种操作。为何需要排序呢。我们在所有的系统中几乎都要检索数据，而这些欲检索的数据如果有规律的话，比如按照某些字段、属性降序排序的话，那么从这些有规律的数据查询结果或者结果集的话就快速得多。

2.       常用算法

常用的算法有：直接选择排序、堆排序、冒泡排序、快速交换排序、直接插入排序、折半插入排序、Shell排序、归并排序、桶式排序、基数排序。这些都属于常用排序算法，也都是内部排序算法。所谓内部排序就是不借助任何外部的内存处理器，直接使用内存，在内存中完成就可以的排序方式。

3.       直接选择排序

直接排序的思想就是进行二重遍历，由外层元素依次和内层元素进行对比，之后交换位置。算法如下

package sort;

import java.util.Arrays;

/**
 * 选择排序
 * 
 * @author liuyan
 */
public class SelectSort {

	// 选择排序法
	public static void selectSort(Integer[] integers) {
		for (int i = 0; i < integers.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < integers.length; j++) {
				if (integers[i] < integers[j]
						&& integers[minIndex] < integers[j]) {

					// 只记住标记
					minIndex = j;
				}
			}

			// 每次只交换一次即可
			if (minIndex != i) {
				Integer temp = integers[i];
				integers[i] = integers[minIndex];
				integers[minIndex] = temp;
			}
		}
	}
}

 4.       堆排序

堆排序的思想就是将要排序的数组看成一个完全二叉树（出最后一层节点外，其他节点都是2个子节点），之后建立大顶堆，将完全二叉树建立成一个父节点值都大于它的子节点的树。之后将根节点和要排序的数组的最后一个元素进行换位。之后除了数组最后一个元素外重复建堆过程。算法如下

package sort;

import java.util.Arrays;

/**
 * 堆排序
 * 
 * @author liuyan
 */
public class HeapSort {

	/**
	 * 构建堆数组
	 * 
	 * @param datas
	 * @param lastIndex
	 */
	public static void buildHeap(Integer[] datas, int lastIndex) {
		
		//从目标的父节点开始遍历
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			
			//记录父节点位置
			int maxIndex = i;
			
			//当父节点的子节点存在的时候
			while (maxIndex * 2 + 1 <= lastIndex) {
				
				//默认附一个大值为父节点的左子节点的索引
				int biggerIndex = maxIndex * 2 + 1;
				
				//此处判断是否父节点还有一个右子节点
				if (biggerIndex < lastIndex) {
					
					//如果有右子节点判断左右子节点的值大小，记录一个最大的位置，好用于交换
					if (datas[biggerIndex] < datas[biggerIndex + 1]) {
						biggerIndex++;
					}

				}
				
				//此处是比较父节点值和左右子节点值，找个最大的做父亲
				if (datas[maxIndex] < datas[biggerIndex]) {
					Integer temp = datas[maxIndex];
					datas[maxIndex] = datas[biggerIndex];
					datas[biggerIndex] = temp;
					
					//记录一下最大值的索引
					maxIndex = biggerIndex;
				} else {
					break;
				}

			}

		}

	}

	/**
	 * 堆排序
	 * 
	 * @param datas
	 */
	public static void heapSort(Integer[] datas) {

		// 数组大小
		int arrayLength = datas.length;

		// 遍历数组
		for (int i = 0; i < arrayLength - 1; i++) {

			// 构建堆
			buildHeap(datas, arrayLength - 1 - i);

			// 交换元素
			Integer temp = datas[0];
			datas[0] = datas[arrayLength - 1 - i];
			datas[arrayLength - 1 - i] = temp;
		}

	}

 5.       冒泡排序

冒泡排序在使用频率上来说，也许是仅次于直接选择排序的算法的了。因为起泡的思想也很简单就是循环数组中的元素，相邻元素一一对比，进行交换。算法如下

package sort;

import java.util.Arrays;

/**
 * 冒泡排序法
 * 
 * @author liuyan
 */
public class BubbleSort {

	/**
	 * 冒泡排序
	 * 
	 * @param datas
	 */
	public static void bubbleSort(Integer[] datas) {
		int datasLength = datas.length;
		for (int i = 0; i < datasLength - 1; i++) {
			for (int j = 0; j < datasLength - 1 - i; j++) {
				if (datas[j] < datas[j + 1]) {

					// 交换之
					Integer temp = datas[j + 1];
					datas[j + 1] = datas[j];
					datas[j] = temp;
				}
			}
		}

	}

}

 6.       快速排序

所谓快速排序法是从待排序的数组中找一个标本作为分界值（一般是数组的第一个元素），所有比这个值小的值放到它的左边（或者右边），将比它大的值放到它的右边（或者左边），这样这个分界值左右两边的值要么全部比它大，要么全部比它小。之后再利用递归，将此标本右边、左边的所有元素也按部就班。算法如下

package sort;

import java.util.Arrays;

/**
 * 快速排序
 * 
 * @author liuyan
 */
public class QuickSort {

	/**
	 * 交换数组元素位置
	 * 
	 * @param datas
	 * @param i
	 * @param j
	 */
	public static void chang(Integer[] datas, int i, int j) {
		Integer temp = datas[i];
		datas[i] = datas[j];
		datas[j] = temp;

	}

	/**
	 * 快速排序法
	 * 
	 * @param datas
	 * @param startIndex
	 * @param endIndex
	 */
	public static void quickSort(Integer[] datas, int startIndex, int endIndex) {

		if (startIndex < endIndex) {
			
			//标本
			Integer startData = datas[startIndex];
			
			//左边的开始索引
			int i = startIndex;
			
			//右边的开始索引
			int j = endIndex + 1;
			while (true) {
				
				//找左边比标本大的下标
				while (i < endIndex && datas[++i] > startData){
				}
				
				//找右边比标本小的下标
				while (j > startIndex && datas[--j] < startData){
				}
					
				if (i < j) {
					
					//交换i、j元素位置
					chang(datas, i, j);
				} else {
					break;
				}
			}
			
			//交换开始位置、j的元素为止
			chang(datas, startIndex, j);
			
			//递归标本左边
			quickSort(datas, startIndex, j - 1);
			
			//递归标本右边
			quickSort(datas, j + 1, endIndex);
		}

	}
}

 7.       直接插入排序

直接插入排序的原理就是将数组中的元素依次和前面元素进行比较，如果发现了比它大的（或者小的），记录标志位、记录被比较元素，之后从标志位一位一位的向后进行元素移动，之后空出来的的那一位就是留给被比较元素的。这样造成了一个现象就是被比较的元素前面的所有元素都是排序过了的。算法如下。

package sort;

import java.util.Arrays;

/**
 * 直接插入排序
 * 
 * @author liuyan
 */
public class InsertSort {

	/**
	 * 直接插入
	 * 
	 * @param datas
	 */
	public static void insertSort(Integer[] datas) {
		
		//从数组第二个元素开始遍历
		for (int i = 1; i < datas.length; i++) {
			
			//当前元素和前一个元素进行对比【此处前面的元素已经排序好了】
			if (datas[i] < datas[i - 1]) {
				
				//记录当前要比较的元素值
				Integer temp = datas[i];
				
				//从当前元素往前开始比较
				int j = i - 1;
				
				//如果满足前面索引有效并且前面的元素值都是比当前值大的，那就进行元素后移动操作
				for (; j >= 0 && datas[j] > temp; j--) {
					
					//元素后移
					datas[j + 1] = datas[j];

				}
				
				//前移操作后，j的索引就是中间那个比前面元素大，比后面元素小的位置索引-1
				
				//将其要对比的值插进去
				datas[j + 1] = temp;
			}

		}
	}
}

 8.       折半插入排序

折半插入排序是在原直接插入的基础上作了改进。对于折半插入法，被比较的元素不用和前面所有的元素进行一一对比，而是先找到0位元素到此被比较元素的中点元素，和这个重点元素进行比较，看看谁大，之后就是被比较元素元素和这个中点元素之间再找一个中点进行比较，或者是0点和原中点元素找个新中点。这样就可以缩小范围，反正排在被比较元素之前的元素是一个已经排好大小的序列，那就可以善加利用这已经排好的序列。当然了，找到位置后，该移动元素的还是要移动的。算法如下：

package sort;

import java.util.Arrays;

/**
 * 折半排序
 * 
 * @author liuyan
 */
public class BinaryInsertSort {

	/**
	 * 折半排序
	 * 
	 * @param datas
	 */
	public static void binaryInsertSort(Integer[] datas) {

		// 从数组第二个元素开始遍历
		for (int i = 1; i < datas.length; i++) {

			// 记录当前要比较的元素值
			Integer temp = datas[i];

			// 低位开始
			int low = 0;

			// 高位开始
			int hight = i - 1;

			// 位置有效，低位、高位
			while (low <= hight) {

				// 中间位置
				int mind = (low + hight) / 2;
				
				//被比较元素大于中间元素
				if (temp > datas[mind]) {
					
					//低位调整在中点之后
					low = mind + 1;
				} else {//被比较元素小于中间元素
					
					//高位在中点之前
					hight = mind - 1;
				}
			}
			// 低高位调整完毕后，将中点元素依次往后移动
			for (int j = i; j > low; j--) {

				// 元素后移
				datas[j] = datas[j - 1];

			}

			// 前移操作后，low的索引就是中间那个比前面元素大，比后面元素小的位置索引low
			// 将其要对比的值插进去
			datas[low] = temp;
		}
	}
}

 9.       归并排序

归并排序的主要思想就是将原来的数组分开成2大部分，建立一个新的临时数组，分别从2部分开始顺序走，将2部分的元素进行比较，先将小元素放入到临时数组，之后索引往前走一位，剩下的在进行比较。算法如下：

 

 

 

 

 

package sort;

import java.util.Arrays;

/**
 * 归并排序
 * 
 * @author liuyan
 */
public class MergeSort {

	/**
	 * 归并排序
	 * 
	 * @param datas
	 * @param start
	 * @param datasLength
	 */
	public static void mergeSort(Integer[] datas, int leftIndex, int rightIndex) {
		
		//当分块索引有效时
		if (leftIndex < rightIndex) {
			
			//找出中间索引
			int center = (leftIndex + rightIndex) / 2;
			
			//把左边到中点的元素集合继续分堆儿
			mergeSort(datas, leftIndex, center);
			
			//把右边到中点的元素集合继续分堆儿
			mergeSort(datas, center + 1, rightIndex);
			
			//归并
			merge(datas, leftIndex, center, rightIndex);
		}

	}

	/**
	 * 归并
	 * 
	 * @param datas
	 * @param left
	 * @param center
	 * @param right
	 */
	private static void merge(Integer[] datas, int left, int center, int right) {
		
		//建立一个临时的数组，用于装载排序后的数组
		Integer[] temp = new Integer[datas.length];
		
		//第二队的开始索引位置
		int mind = center + 1;
		
		//临时数组从第一队的索引开始
		int third = left;
		
		//仅仅记录开始索引位置
		int tmp = left;
		while (left <= center && mind <= right) {//分队后的数组进行比较
			if (datas[left] <= datas[mind]) {
				
				//左边的略小，左边索引前进
				temp[third++] = datas[left++];
			} else {
				
				//右边的略小，右边索引前进
				temp[third++] = datas[mind++];
			}

		}
		
		//如果第二队数组还没走完，继续走完，将第二队右边的元素都放到临时数组后面
		while (mind <= right) {
			temp[third++] = datas[mind++];
		}
		
		//如果第一队数组还没走完，继续走完，将第一队右边的元素都放到临时数组后面
		while (left <= center) {
			temp[third++] = datas[left++];
		}
		
		//将临时数组中的所有元素（排序好的），原样覆盖到原先的数组
		while (tmp <= right) {
			datas[tmp] = temp[tmp++];
		}
	}
}

 总结到这里发现自己实在不行了。要吐了，算法真的是数学大师+计算机专业的人才能搞得了得。相当于大脑就是一个编译器+数学公式器+内存监视器。向所有世界上还在为算法而奋斗的人们致敬，先总结到这里。