摘要： 本文旨在准备明年2023的蓝桥杯竞赛，培养个人Java语法素养和手感。 希望可以帮助到一起备赛的小伙伴们。题目来自蓝桥杯刷题网

@[toc]

前言：注意主类是 Main，编辑器用ecilips

一、数列排序

资源限制
内存限制：512.0MB Java时间限制：3.0s

问题描述
　　给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200
　　
输入格式
　　第一行为一个整数n。
　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。
　　
输出格式
　　输出一行，按从小到大的顺序输出排序后的数列。
　　
样例输入
5
8 3 6 4 9

样例输出
3 4 6 8 9

解题思路： 数组排序有着八大排序算法，比较常用的是冒泡排序，选择排序，直接插入排序 、希尔排序、堆排序、归并排序、快速排序， 但在竞赛中其实并不用说使用最好的排序，只要能符合题目要求即可，选择自己比较熟练的即可。这里为了演示，八大排序都给读者展示如下🙋‍♂️ ( 为了减少代码冗余，只展示核心排序代码

代码框架

public class 数组排序 {
	public static void main(String args[]) {
		Scanner reader = new Scanner(System.in);
		int num = reader.nextInt(); // 读取数组长度
		int array[] = new int[num]; // 构造数组
		for(int i = 0;i<num;i++) {
			array[i] = reader.nextInt();
		}
		/*
	 	* 排序代码
	 	* ...
 		*/
 		
 		//输出
		for(int i = 0;i<num;i++) {
			System.out.print(array[i] + " ");
		}	
	}
		public void swap(int a,int b) {  // 封装数组元素交换
		int temp;
		temp = a;
		a = b;
		b = temp;
	}
} 
	

1.1 冒泡排序

// 排序
		boolean judge;// 循环 judge
		for(int i = 0;i<num;i++) {
			judge = true;
			for(int j = num-1;j>0;j--) { // 逆序遍历
				if(array[j-1] > array[j])
					swap(array,j-1,j);
					judge = false;
			}
			if(judge)   // 如果一轮循环没有元素交换，则都已排序完毕
				break;
		}

1.2 简单选择排序·

简单选择排序虽然与冒泡排序时间复杂度都是 $O(N^2）$ 但选择排序的交换次数在正常情况要普遍少于冒泡排序，在性能总体上交换和比较上性能还是要略优于冒泡排序

//		选择排序 ( 簡單 )
		int min;
		for(int i = 0;i<num;i++) {
			min = i;
			for(int j = i + 1;j<num;j++) { // 逆序遍历
			   if (array[min] > array[j])
				   		min = j;
			}
			swap(array,i,min);
		}

1.3 直接插入排序

直接排序无需交换，大小比较后将赋值替代交换，在性能上要优于简单选择排序和冒泡排序,但是要额外多一个辅助空间，代码框架需要改一下（array[0] 要当作哨兵）

public class 数组排序 {
	public static void main(String args[]) {
		Scanner reader = new Scanner(System.in);
		int num = reader.nextInt(); // 读取数组长度
		int array[] = new int[num + 1]; // 构造数组
		for(int i = 1;i<array.length;i++) {
			array[i] = reader.nextInt();
		}
// 直接插入排序
		int j;
		for(int i = 2;i<array.length;i++) {
			
			if(array[i] < array[i-1]) { 
				array[0] = array[i];
				for(j = i-1;array[j]>array[0];j--) {
					array[j+1] = array[j];
				}
				array[j+1] = array[0];
			}
		}
				for(int k = 1;k<array.length;k++) {
			System.out.print(array[k] + " ");
		}	
	}
} 

1.4 希尔排序

希尔排序是直接插入排序的升级版，也是最早一批打破时间复杂度为 O(N^3) 的一批排序算法，其运用跳跃排序的方法提高了性能

		//希尔排序
		int increment = array.length;
		int j;
		do {
			increment = increment / 3 + 1;
			for(int i = increment + 1;i<array.length;i++) {
				if(array[i]<array[i-increment]) {
					array[0] = array[i];
					for(j = i - increment;j > 0 && array[j]>array[0] ; j-=increment) {
						array[j + increment] = array[j];
					}
					array[j + increment] = array[0];
				}
			}	
		}while(increment>1);

这里看到时间上升许多
·

1.5 堆排序

堆排序属于非比较排序，因此不论在数组好坏情况都是 $O(nlog_n)$ 复杂度，但是不适用于排序个数较少的情况（建堆比较次数较多）

//		堆排序 ( 非比较排序)
		int i;
		for (i = (array.length - 1) / 2; i > 0; i--) {
			HeapAdjust(array, i, array.length - 1); // 循环双亲节点生成
		}
		for (i = array.length - 1; i > 1; i--) {
			swap(array, 1, i);
			HeapAdjust(array, 1, i - 1); // 继续调整
		}
		// 输出
		for (int k = 1; k < array.length; k++) {
			System.out.print(array[k] + " ");
		}
	}

	/*
	 * description: Resize array elements in order
	 */
	public static void HeapAdjust(int array[], int i, int num) {
		int temp, j;
		temp = array[i];
		for (j = 2 * i; j <= num; j *= 2) {
			if (j < num && array[j] < array[j + 1]) {
				j += 1;
			}
			if (temp >= array[j])
				break;
			array[i] = array[j];
			i = j;
		}
		array[i] = temp;
	}

1.6 归并排序

前面所说堆排序充分利用了完全二叉树中的深度为 $[log_2n]+ 1$ 的特性，所以效率比较高，但是结构比较复杂，而归并排序则是一种比较分治思想。（注意这里没有添加一个辅助空间，下标从0开始）

//		归并排序mergingSort （非递归）
	int temp[] = new int[array.length];
	int k = 1 ;
	while(k < array.length) {
		MergePass(array,temp,k);
		k *= 2;
		MergePass(temp,array,k);
		k *= 2;
	}
	// 输出
	for (int k1 = 0; k1 < array.length; k1++) {
		System.out.print(array[k1] + " ");
	}
}
	
	/*
	 * 归并排序
	 * description: traversal array and merge pass every element
	 */ 
	public static void MergePass(int a[],int b[], int num) {
		int i = 0;
		while(i <= a.length - 2*num ) {
			Merge(a,b,i,i+num - 1,i+2*num); // 需要减一，因为把自己下标包含进去了
			i += num*2 ;
		} 
		if(i < a.length - num) {
			Merge(a,b,i,i+num - 1,a.length); // 归并最后两个序列
		}
		else {
			for(int j = i;j < a.length;j++)
			b[j] = a[j]; // 留下单个子序列
		}
		
	}
	/*
	 * 归并排序
	 * description: merge array a to array b 
	 */
	public static void Merge(int a[],int b[], int begin,int middle,int end) {
		int i,j,k;
		for(j = middle + 1,i = begin,k = begin;k<middle+1 && j<end;i++) {
			if(a[k]>a[j]) {
				b[i] = a[j++];
			}
			else {
				b[i] = a[k++];
			}	
		}
		if(k < middle + 1) {
			for (int l = 0; l <  middle - k + 1;l++) {
				b[i ++ ] = a[k + l];
			}
		}
		if(j < end) {
			for (int l = 0; l < end - j ;l++) {
				b[i ++ ] = a[j + l];
			}
		}
		
	}
	

代码有点长，咋一看有点难懂，其实原理还是比较简单的，在处理数组下标中要格外小心，其中该非迭代算法直接对原数组开刀，并使用了一个辅助数组存贮数据，每一次Mergepass 都是将数组按照num个数进行合并，假如我到最后只剩下两个序列就会直接合并，如果判断一开始无法合并，则表明排序结束，直接将辅助数组排序好的复制回原数组。

merge 函数用于合并两个序列，这在递归归并排序算法也有使用，下面我看看其的归并排序（递归）算法

int temp[] = new int[array.length];
	Msort(array,temp,0,array.length - 1);
	for (int k1 = 0; k1 < array.length; k1++) {
		array[k1] = temp[k1];
	}
	// 输出
	for (int k1 = 0; k1 < array.length; k1++) {
		System.out.print(array[k1] + " ");
	}
}

	/*
	 * 归并排序（合并）
	 * description: merge array a to array b 
	 * 
	 */
	public static void Merge(int a[],int b[], int begin,int middle,int end) {
		int i,j,k;
		for(j = middle + 1,i = begin,k = begin;k<middle+1 && j<=end;i++) {
			if(a[k]>a[j]) {
				b[i] = a[j++];
			}
			else {
				b[i] = a[k++];
			}	
		}
		if(k < middle + 1) {
			for (int l = 0; l <  middle - k + 1;l++) {
				b[i ++ ] = a[k + l];
			}
		}
		if(j <= end) {
			for (int l = 0; l <= end - j ;l++) {
				b[i ++ ] = a[j + l];
			}
		}
		
	}
	
	/*
	 * 归并排序（递归）
	 * description:  recursive sort
	 */
	public static void Msort(int a[],int b[],int start,int end) {
		int middle;
		int temp[] = new int[a.length];	
		if(start == end) {
			b[start] = a[start];
		} 
		else {
			middle = (start+end)/2;
			Msort(a,temp,start,middle);
			Msort(a,temp,middle + 1,end);
			Merge(temp,b,start,middle,end);
		}
	}
	

使用递归虽然代码比较清晰，但相对比较难懂，且性能要差一点，因为递归是将数组拆开成一个一个元素，再将其合并回去。