题目链接：
描述
给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。
数据范围：0≤n≤1×103，数组中每个元素都满足0≤val≤109
要求：时间复杂度 O(n^2)，空间复杂度 O(n)
进阶：时间复杂度 O(nlogn)，空间复杂度 O(n)
注：本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。
示例1
1. 输入： 2. [5,2,3,1,4] 3. 返回值： 4. [1,2,3,4,5]
示例2
1. 输入： 2. [5,1,6,2,5] 3. 返回值： 4. [1,2,5,5,6]
题解：
主要是考察我们对各种排序算法的理解和掌握，本题可以使用多种排序算法，包括插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，但不仅仅限于这些，你可以选择其中的进行解题即可，对于排序算法不清楚的，可以期待一下，博主下一次可能会出一篇有关这些排序的详细解答和图解，希望对大家有帮助！ 本题我们选择较为简单的冒泡排序（大多数人刚接触就会的一种排序）和堆排序进行解答。
AC代码:
1. import java.util.*; 2. 3. 4. public class Solution { 5. /** 6. * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 7. * 将给定数组排序 8. * @param arr int整型一维数组 待排序的数组 9. * @return int整型一维数组 10. */ 11. public int[] MySort (int[] arr) { 12. // write code here 13. 14. //根据题目要求，基础为时间复杂度O(n^2),空间复杂度O(n) 15. //进阶为时间复杂度O(nlogn),空间复杂度O(n) 16. 17. //满足基础的可以用冒泡，插入，选择，快排 18. //进阶可以用堆排和归并 19. 20. /** 21. 基础的我们用一下冒泡排序 22. */ 23. // boolean flag=false; 24. // for(int i=0;i<arr.length-1;i++){ 25. 26. // for(int j=0;j<arr.length-1-i;j++){ 27. 28. // if(arr[j]>arr[j+1]){ 29. // int temp=arr[j]; 30. // arr[j]=arr[j+1]; 31. // arr[j+1]=temp; 32. // flag=true; 33. // } 34. // } 35. 36. // if(flag==false){ 37. // break; 38. // } 39. // } 40. 41. // return arr; 42. 43. /** 44. 进阶用堆排序 45. 46. */ 47. 48. creatHeap(arr); 49. int end=arr.length-1; 50. while (end>0){ 51. swap(arr,0,end); 52. shiftDown(arr,0,end); 53. end--; 54. } 55. 56. return arr; 57. 58. } 59. public void creatHeap(int[]arr){ 60. 61. for (int parent = (arr.length-1-1)/2; parent>=0; parent--) { 62. shiftDown(arr,parent, arr.length); 63. } 64. } 65. 66. private void shiftDown(int[]arr,int parent,int len){ 67. int child=2*parent+1; 68. 69. while(child<len){ 70. 71. if(child+1<len&&arr[child+1]>arr[child]){ 72. child++; 73. } 74. if(arr[parent]<arr[child]){ 75. swap(arr,parent,child); 76. parent=child; 77. child=2*parent+1; 78. }else{ 79. break; 80. } 81. } 82. 83. } 84. 85. public void swap(int[]arr,int i,int j){ 86. int temp=arr[i]; 87. arr[i]=arr[j]; 88. arr[j]=temp; 89. } 90. }
