【数据结构】内排序——Java实现

都说数据结构是我们程序员的基本功之一，那么内排序就是数据结构里必不可少的重要部分。所以自己在学习这部分内容的同时也希望能给大家带来更多的东西，希望你能有所收获！

概念

内排序和外排序

在排序过程中，整张表都是在内存中处理，不涉及内、外存的数据交换，称之为内排序。

反之，排序过程中需涉及内外存交换的，称之为外排序。

排序的稳定性

排序过程中，可能会遇到关键字相同的几个元素，若排序完后它们的相对顺序不变，则这种排序方法是稳定的。

反之，如果它们相对次序变动了，就是不稳定的排序方法。

插入排序

      直接插入排序

            思路解析：将未排序区的第一个元素插入到有序区合适的位置

            时间复杂度：O(n2)

            稳定性：稳定

/**
 * 直接插入排序
 *
 * 将数组分为'有序区'与'无序区'，每次将'无序区'的开头元素放到'有序区'的指定位置中
 * @author Levi
 *
 */
public class DirectInsertionSort {
	public static void main(String[] args) {
		int[] arrayInt = { 17, 56, 80, 17, 12, 9, 18, 100, 64, 42, 37, 64, 82, 123, 974, 314, 548 };
		int length = arrayInt.length;

		//注意初始的i是1不是0,在数组中是第二位
		for (int tmp, j, i = 1; i < length; i++) {//外循环，小于等于i的是有序区
			tmp = arrayInt[i];
			for (j = i-1; j >= 0 && tmp < arrayInt[j]; j--) {
				arrayInt[j+1] = arrayInt[j];//将值小于arrayInt[i]的值往后移
			}
			arrayInt[j+1] = tmp;
		}
		
		//输出结果
		for (int i : arrayInt) {
			System.out.println(i);
		}
	}

}

希尔排序

            思路解析：希尔排序是一种分组的插入排序，先选取一个增量X（一般为n/2），将彼此间隔为X的元素放在一组（所以一共X个组），每个组组内进行插入排序后，再缩小增量X（一般去X/2），再次排序，直到X为1，所有元素为一组，排序完成

            时间复杂度：O(n1.3)

            稳定性：不稳定

/**
 * 希尔排序
 * 
 * @author Levi
 *
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] arrayInt = {17,56,80,17,12,9,100,64,42,37,64,82,123,974,314,548};
		
		shellSort( arrayInt);
		
		for (int i : arrayInt) {
			System.out.println(i);
		}
	}
	
	public static void shellSort( int[] arrayInt) {
		 int j = 0;
		 int temp = 0;
		 for(int increment = arrayInt.length/2; increment > 0; increment /= 2) {//循环1:控制间隔
			 
			 for(int i = increment; i < arrayInt.length; i++) {//循环2:逐渐增加i
				 temp = arrayInt[i];
				 
				 for(j = i; j >= increment && temp < arrayInt[j-increment]; j-=increment) {//循环3:对相隔为increment的组进行直接插入排序
					 arrayInt[j] = arrayInt[j-increment];
				 }
				 arrayInt[j] = temp;
			 }
		 }
	}
	
}

交换排序

冒泡排序

            思路解析：

            时间复杂度：O(n2)

            稳定性：稳定

/**
 * 冒泡排序
 * @author Levi
 */
public class BubbleSort {
	public static void main(String[] args) {
		int[] arrayInt = {17,56,80,17,12,9,100,64,42,37,64,82,123,974,314,548};
		
		for(int temp,j,i = 0; i < arrayInt.length; i++) {
			for(j = arrayInt.length - 1; j > i; j--) {//比较，找出本趟最小的元素
				if(arrayInt[j] < arrayInt[j - 1]) {//通过交换元素将最小的元素前移
					temp = arrayInt[j];
					arrayInt[j] = arrayInt[j - 1];
					arrayInt[j - 1] = temp;
				}
			}
		}
		
		for (int i : arrayInt) {
			System.out.println(i);
		}
	}
}

快速排序

            思路解析：

            时间复杂度：O(nlog2 n)

            稳定性：不稳定

public class QuickSort {
	public static void main(String[] args) {
		int[] arrayInt = {17,56,80,17,12,9,100,64,42,37,64,82,123,974,314,548};
		int length = arrayInt.length;
		
		QuickSort(arrayInt, 0, length-1);//注意传入参数应为物理值
		
		for (int i : arrayInt) {
			System.out.print(i+" ");
		}
		
	}
	
	public static void QuickSort(int[] arrayInt, int start, int end) {
		int i = start, j = end;
		int temp;
		
		if(start < end) {//区间至少存在两个数
			temp = arrayInt[start];//选区基准(区间的第一个数)
			while(i != j) {
				while(j>i && arrayInt[j] >= temp)//从右向左扫描，找到'第一个'小于temp(基准)的数
					j--;
				arrayInt[i] = arrayInt[j];//找到符合情况的arrayInt[j],与arrayInt[i]交换
				
				while(i<j && arrayInt[i] <= temp)//从左向右扫描，找到'第一个'大于temp(基准)的数
					i++;
				arrayInt[j] = arrayInt[i];//找到符合情况的arrayInt[i],与arrayInt[j]交换
			}
			arrayInt[i] = temp;//基准归位
			
			QuickSort(arrayInt, start, i-1);
			QuickSort(arrayInt, i+1, end);
		}
	}
}

选择排序

快速选择排序

            思路解析：

            时间复杂度：O(n2)

            稳定性：不稳定

/**
 * 简单选择排序
 * @author Jacky
 *
 */
public class SimpleSelectSort {
	public static void main(String[] args) {
		int[] arrayInt = {17,56,80,17,12,9,100,64,42,37,64,82,123,974,314,548};
		int length = arrayInt.length;
		
		for(int i=0; i<length; i++) {//循环1:0至i的是有序区
			for(int j=i+1; j<length; j++) {//循环2:每次选取无序区最小的数,放入有序区末尾
				if(arrayInt[i] > arrayInt[j]) {//若遍历到更小的数,与有序区末尾交换
					int k = arrayInt[i];
					arrayInt[i] = arrayInt[j];
					arrayInt[j] = k;
				}
			}
		}
		
		for (int i : arrayInt) {
			System.out.println(i);
		}
	}
}