常用的八种排序算法Java代码实现

Algorithm

package algorithm;

import java.util.Arrays;

public class EightAlgorithm {
	/**
	 * 
	 * 常用的八种排序算法Java代码实现
	 * 时间：2018-9-5-下午9:14:30 
	 * 邮件：hasp_Jason@163.com
	 * @exception 
	 * *辅助记忆*
	 * 时间复杂度记忆- 
	 * 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）（一遍找元素O(n)，一遍找位置O(n)）
	 * 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）
	 * 稳定性记忆-“快选希堆”（非稳定：快牺牲稳定性） 
	 * 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
	 */
	public static void main(String[] args) {
		
		int []array={23,56,8,45,2,95,11,12,17,10,11};
		System.out.println("length: "+array.length);
		insertSort(array);	//1.直接插入
		//sheelSort(array);		//2.希尔排序
		//selectSort(array);	//3.简单选择排序
		//heapSort(array);		//4.堆排序
		//bubbleSort(array);	//5.冒泡排序
		//quickSort(array, 0, array.length-1);//6.快速排序  
		//mergeSort(array);		//7.归并排序
		//sort(array,10);		//8.基数排序
		System.out.println(Arrays.toString(array));
	}
	
	/**
	 * 1.直接插入  经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度		是否稳定
	 * 	O（n^2）			O（n^2）		O（1）		是
	 * 	将第一个数和第二个数排序，然后构成一个有序序列
	 * 	将第三个数插入进去，构成一个新的有序序列。
  	 * 	对第四个数、第五个数……直到最后一个数，重复第二步。
  	 * 
  	 ***如何写成代码：
  	 *	1.首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
  	 *	2.设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
  	 *	3.从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
  	 *	4.将当前数放置到空着的位置，即j+1。
	 */
	public static void insertSort(int[] a) {
		int insertNum; // 要插入的数
		for (int i = 1; i < a.length; i++) {
			insertNum = a[i];
			int j = i - 1;
			while (j >= 0 && a[j] > insertNum) {// 将大于insertNum的数向后移动一格
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = insertNum;
		}
	}
	
	/**
	 * 2.希尔排序   对于直接插入排序问题，数据量巨大时。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
	 * O(nlogn)		O（n^s）		O（1）	不是
	 * 	将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。
	 * 	再取k=k/2 ，将下标差值为k的数分为一组，构成有序序列。
	 * 	重复第二步，直到k=1执行简单插入排序。
	 * 
	 ***如何写成代码：
	 *	1.首先确定分的组数。
	 *	2.然后对组中元素进行插入排序。
	 *	3.然后将length/2，重复1,2步，直到length=0为止。
	 */
	public static void sheelSort(int[] a) {
		int length = a.length;
		while (length != 0) {
			length = length / 2;
			System.out.println("length变化： " + length);
			for (int x = 0; x < length; x++) { 	// 分组个数
				for (int i = x + length; i < a.length; i += length) {
					int j = i - length; 	// j为有序序列最后一位的位数
					int insertNum = a[i]; 	// 要插入的元素
					for (; j >= 0 && insertNum < a[j]; j -= length) {
						a[j + length] = a[j];	// 向后移动length位
					}
					a[j + length] = insertNum;
				}
			}
		}
	}
	
	/**
	 * 3.简单选择排序    常用于取序列中最大最小的几个数时。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
	 * O（n^2） 		O（n^2）		O（1）	不是
	 * 	(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)
	 * 	遍历整个序列，将最小的数放在最前面。
	 * 	遍历剩下的序列，将最小的数放在最前面。
	 * 	重复第二步，直到只剩下一个数。
	 * 
	 ***如何写成代码：
	 *	1.首先确定循环次数，并且记住当前数字和当前位置。
	 *	2.将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。
	 *	3.比对完成后，将最小的值与第一个数的值交换。
	 *	4.重复2、3步。
	 */
	public static void selectSort(int[] a) {
		int length = a.length;
		for (int i = 0; i < length; i++) {			// 循环次数
			int key = a[i];
			int position = i;
			for (int j = i + 1; j < length; j++) {	// 选出最小值和位置
				if (a[j] < key) {
					key = a[j];
					position = j;
				}
			}
			a[position] = a[i];			// 交换位置
			a[i] = key;
		}
	}
	
	/**
	 * 4.堆排序   对简单选择排序的优化。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
	 * O(nlogn)		O(nlogn)	O（1）	不是
	 *	将序列构建成大顶堆。
	 *	将根节点与最后一个节点交换，然后断开最后一个节点。
	 *	重复第一、二步，直到所有节点断开。
	 */
	public static void heapSort(int[] a) {
		System.out.println("开始排序");
		int arrayLength = a.length;
		// 循环建堆
		for (int i = 0; i < arrayLength - 1; i++) {
			// 建堆
			buildMaxHeap(a, arrayLength - 1 - i);
			// 交换堆顶和最后一个元素
			swap(a, 0, arrayLength - 1 - i);
			System.out.println(Arrays.toString(a));
		}
	}

	private static void swap(int[] data, int i, int j) {
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}

	// 对data数组从0到lastIndex建大顶堆
	private static void buildMaxHeap(int[] data, int lastIndex) {
		// 从lastIndex处节点（最后一个节点）的父节点开始
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			// k保存正在判断的节点
			int k = i;
			// 如果当前k节点的子节点存在
			while (k * 2 + 1 <= lastIndex) {
				// k节点的左子节点的索引
				int biggerIndex = 2 * k + 1;
				// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
				if (biggerIndex < lastIndex) {
					// 若果右子节点的值较大
					if (data[biggerIndex] < data[biggerIndex + 1]) {
						// biggerIndex总是记录较大子节点的索引
						biggerIndex++;
					}
				}
				// 如果k节点的值小于其较大的子节点的值
				if (data[k] < data[biggerIndex]) {
					// 交换他们
					swap(data, k, biggerIndex);
					// 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
					k = biggerIndex;
				} else {
					break;
				}
			}
		}
	}
	
    
    /**
     * 5.冒泡排序    一般不用。
     * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
     * O（n^2） 		O（n^2）		O（1）	是
	 *	将序列中所有元素两两比较，将最大的放在最后面。
	 *	将剩余序列中所有元素两两比较，将最大的放在最后面。
	 *	重复第二步，直到只剩下一个数。
	 *	
	 ***如何写成代码：
	 *	1.设置循环次数。
	 *	2.设置开始比较的位数，和结束的位数。
	 *	3.两两比较，将最小的放到前面去。
	 *	4.重复2、3步，直到循环次数完毕。
	 *
     */
	public static void bubbleSort(int[] a) {
		int length = a.length;
		int temp;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}
	}

	/**
	 * 6.快速排序		要求时间最快时。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度		是否稳定
	 * O(nlogn) 	O（n^2）		O（logn）	不是
	 *	选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
	 *	递归的将p左边和右边的数都按照第一步进行，直到不能递归。
	 */
	public static void quickSort(int[] numbers, int start, int end) {
		if (start < end) {
			int base = numbers[start];// 选定的基准值
			int temp;
			int i = start, j = end;
			do {
				while ((numbers[i] < base) && (i < end))
					i++;
				while ((numbers[j] > base) && (j > start))
					j--;
				if (i <= j) {
					temp = numbers[i];
					numbers[i] = numbers[j];
					numbers[j] = temp;
					i++;
					j--;
				}
			} while (i <= j);
			if (start < j)
				quickSort(numbers, start, j);
			if (end > i)
				quickSort(numbers, i, end);
		}
	}

	/**
	 * 7.归并排序		速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
	 * O(nlogn) 	O(nlogn)	O（n）	是
	 *	选择相邻两个数组成一个有序序列。
	 *	选择相邻的两个有序序列组成一个有序序列。
	 *	重复第二步，直到全部组成一个有序序列。
	 */
	public static void mergeSort(int[] arr) {
		int[] temp = new int[arr.length];// 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
		mergeSort(arr, 0, arr.length - 1, temp);
	}

	private static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if (left < right) {
			int mid = (left + right) / 2;
			mergeSort(arr, left, mid, temp);// 左边归并排序，使得左子序列有序
			mergeSort(arr, mid + 1, right, temp);// 右边归并排序，使得右子序列有序
			merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
		}
	}

	private static void merge(int[] arr, int left, int mid, int right,
			int[] temp) {
		int i = left;// 左序列指针
		int j = mid + 1;// 右序列指针
		int t = 0;// 临时数组指针
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}
		while (i <= mid) {// 将左边剩余元素填充进temp中
			temp[t++] = arr[i++];
		}
		while (j <= right) {// 将右序列剩余元素填充进temp中
			temp[t++] = arr[j++];
		}
		t = 0;
		// 将temp中的元素全部拷贝到原数组中
		while (left <= right) {
			arr[left++] = temp[t++];
		}
	}
	
	
	/**
	 * 8.基数排序		用于大量数，很长的数进行排序时。
	 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
	 * O(N∗M)		O(N∗M)		O(M)	是
	 * 将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
	 * 将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
	 */
	public static void sort(int[] number, int d) {
		int k = 0;
		int n = 1;
		int m = 1;
		int[][] temp = new int[number.length][number.length];
		int[] order = new int[number.length];
		while (m <= d) {
			for (int i = 0; i < number.length; i++) {
				int lsd = ((number[i] / n) % 10);
				temp[lsd][order[lsd]] = number[i];
				order[lsd]++;
			}
			for (int i = 0; i < d; i++) {
				if (order[i] != 0)
					for (int j = 0; j < order[i]; j++) {
						number[k] = temp[i][j];
						k++;
					}
				order[i] = 0;
			}
			n *= 10;
			k = 0;
			m++;
		}
	} 
}