牛客刷题—排序

Bertha 。 2024-04-03 13:07 25阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[手把手带你刷牛客][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

![92d952b1a9574cee926bba59795dff11.png][]

**题目链接：**

[排序][Link 4]

**描述**

给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

数据范围：0≤n≤1×103，数组中每个元素都满足0≤val≤109

要求：时间复杂度 O(n^2)，空间复杂度 O(n)

进阶：时间复杂度 O(nlogn)，空间复杂度 O(n)

注：本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。

**示例1**

输入：
    [5,2,3,1,4]
    返回值：
    [1,2,3,4,5]

**示例2**

输入：
    [5,1,6,2,5]
    返回值：
    [1,2,5,5,6]

题解：

主要是考察我们对各种排序算法的理解和掌握，本题可以使用多种排序算法，包括插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，但不仅仅限于这些，你可以选择其中的进行解题即可，对于排序算法不清楚的，可以期待一下，博主下一次可能会出一篇有关这些排序的详细解答和图解，希望对大家有帮助！ 本题我们选择较为简单的冒泡排序（大多数人刚接触就会的一种排序）和堆排序进行解答。

AC代码:

import java.util.*;
    
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         * 将给定数组排序
         * @param arr int整型一维数组 待排序的数组
         * @return int整型一维数组
         */
        public int[] MySort (int[] arr) {
            // write code here
    
            //根据题目要求，基础为时间复杂度O(n^2),空间复杂度O(n)
            //进阶为时间复杂度O(nlogn),空间复杂度O(n)
    
            //满足基础的可以用冒泡，插入，选择，快排
            //进阶可以用堆排和归并
            
            /**
            基础的我们用一下冒泡排序
             */
            // boolean flag=false;
            //  for(int i=0;i<arr.length-1;i++){
    
            //      for(int j=0;j<arr.length-1-i;j++){
    
            //          if(arr[j]>arr[j+1]){
            //              int temp=arr[j];
            //              arr[j]=arr[j+1];
            //              arr[j+1]=temp;
            //              flag=true;
            //          }
            //      }
    
            //     if(flag==false){
            //         break;
            //     }
            //  }
    
            //  return arr;
    
            /**
            进阶用堆排序
            
             */
    
              creatHeap(arr);
            int end=arr.length-1;
            while (end>0){
                swap(arr,0,end);
                shiftDown(arr,0,end);
                end--;
            }
    
            return arr;
    
        }
         public  void creatHeap(int[]arr){
    
            for (int parent = (arr.length-1-1)/2; parent>=0; parent--) {
                shiftDown(arr,parent, arr.length);
            }
        }
    
        private  void shiftDown(int[]arr,int parent,int len){
            int child=2*parent+1;
    
            while(child<len){
    
                if(child+1<len&&arr[child+1]>arr[child]){
                    child++;
                }
                if(arr[parent]<arr[child]){
                    swap(arr,parent,child);
                    parent=child;
                    child=2*parent+1;
                }else{
                    break;
                }
            }
    
        }
    
            public  void swap(int[]arr,int i,int j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }

![06d38f9e1beb4354b6e793b6268cdb74.png][]

![b54b851156014d2898904061c4c515e4.png][]

“ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/64bc05604a3b49d6bfd1c419e8c0a1db.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_11980422.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[92d952b1a9574cee926bba59795dff11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/86f4573512a74b0593455e7078f4d0b0.png
[Link 4]: https://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896?tpId=308&tqId=1089529&ru=/exam/oj&qru=/ta/algorithm-start/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D308
[06d38f9e1beb4354b6e793b6268cdb74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8097ab7247444c398c8a979d604a2a9d.png
[b54b851156014d2898904061c4c515e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/672950d34f4540f588f3a8f9b79a37e5.png