题目主要信息
1、自己手动输入数组
2、根据输入的0或者1对数组进行排序，其中0代表升序，1代表降序。
这题其实考察的就是排序算法，对于8大排序算法，大家选择任何一个都可以解决这个问题，这里给出两个在面试中经常让大家手写的算法，一个是冒泡一个是堆排序。
方法一：冒泡排序
具体做法
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//记录元素个数
int length = Integer.parseInt(bf.readLine());
//输入数组
String []s = bf.readLine().split(" ");
//记录是升序还是降序
int flag = Integer.parseInt(bf.readLine());
int []num = new int[length];
for(int i=0;i<length;i++){
num[i] = Integer.parseInt(s[i]);
}
//如果输入0表示升序
if(flag == 0){
Ascending_Order(num);
}else{
Descending_Order(num);
}
for(int i=0;i<num.length;i++){
if(i == num.length-1){
System.out.print(num[i]);
}else {
System.out.print(num[i]+" ");
}
}
}
public static void Descending_Order(int []result){
int temp;
for(int i=0;i<result.length-1;i++){
for(int j = 0;j<result.length-1-i;j++){
if(result[j+1]>result[j]){
//后一个比前一个小
temp = result[j];
result[j] = result[j+1];
result[j+1] = temp;
}
}
}
}
//升序
public static void Ascending_Order(int []result){
int temp;
for(int i=0;i<result.length-1;i++){
for(int j = 0;j<result.length-1-i;j++){
if(result[j+1]<result[j]){
//后一个比前一个小
temp = result[j];
result[j] = result[j+1];
result[j+1] = temp;
}
}
}
}
}
复杂度
- 时间复杂度：,由于是两层循环，所以是。
- 空间复杂度：，一个临时的temp变量
方法二：堆排序
具体做法
堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。 其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大****根堆。 举例来说，对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：
- Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
- Ri >= R2i+1 且 Ri >= R2i+2 (大根堆) 其中i=1,2,…,n/2向下取整；
如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆，元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//记录元素个数
int length = Integer.parseInt(bf.readLine());
//输入数组
String []s = bf.readLine().split(" ");
//记录是升序还是降序
int flag = Integer.parseInt(bf.readLine());
int []num = new int[length];
for(int i=0;i<length;i++){
num[i] = Integer.parseInt(s[i]);
}
//如果输入0表示升序
if(flag == 0){
Ascending_Order(num);
}else{
Descending_Order(num);
}
for(int i=0;i<num.length;i++){
if(i == num.length-1){
System.out.print(num[i]);
}else {
System.out.print(num[i]+" ");
}
}
}
public static int[] Ascending_Order(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
//核心代码！！！
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * i + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
public static int[] Descending_Order(int[] array) {
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap_1(array, i, array.length); //调整堆
}
for (int j = array.length - 1; j > 0; j--) {
swap(array, 0, j);
adjustHeap_1(array, 0, j);
}
return array;
}
public static void adjustHeap_1(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * i + 1) {
//看左右子树哪个更小
if (k + 1 < length && array[k] > array[k + 1]) {
k++;
}
if (array[k] < temp) {
swap(array, i, k);
i = k;
} else {
break;
}
}
}
/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
复杂度分析：
- 时间复杂度：，主要在初始化堆过程和每次选取最大数后重新建堆的过程
- 空间复杂度：，堆排序是就地排序。
京公网安备 11010502036488号