🤵♂️ 个人主页: @计算机魔术师 👨💻 作者简介：CSDN内容合伙人，全栈领域优质创作者。
蓝桥杯竞赛专栏 | 简单题系列 （一）
摘要： 本文旨在准备明年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 简单选择排序·
简单选择排序虽然与冒泡排序时间复杂度都是 但选择排序的交换次数在正常情况要普遍少于冒泡排序，在性能总体上交换和比较上性能还是要略优于冒泡排序
// 选择排序 ( 簡單 )
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 堆排序
堆排序属于非比较排序，因此不论在数组好坏情况都是 复杂度，但是不适用于排序个数较少的情况（建堆比较次数较多）
// 堆排序 ( 非比较排序)
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 归并排序
前面所说堆排序充分利用了完全二叉树中的深度为 的特性，所以效率比较高，但是结构比较复杂，而归并排序则是一种比较分治思想。（注意这里没有添加一个辅助空间，下标从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);
}
}使用递归虽然代码比较清晰，但相对比较难懂，且性能要差一点，因为递归是将数组拆开成一个一个元素，再将其合并回去。