给你一个数组,val arr = Array(49, 38, 65, 97, 76, 13, 27, 101, 34, 119, 1),请使用归并排序完成排序。
时间: 2023-10-05 07:08:31 浏览: 44
好的,以下是使用归并排序对该数组进行排序的代码:
```scala
def mergeSort(arr: Array[Int]): Array[Int] = {
def merge(left: Array[Int], right: Array[Int]): Array[Int] = {
var result = new Array[Int](left.length + right.length)
var i = 0
var j = 0
var k = 0
while (i < left.length && j < right.length) {
if (left(i) <= right(j)) {
result(k) = left(i)
i += 1
} else {
result(k) = right(j)
j += 1
}
k += 1
}
while (i < left.length) {
result(k) = left(i)
i += 1
k += 1
}
while (j < right.length) {
result(k) = right(j)
j += 1
k += 1
}
result
}
if (arr.length <= 1) {
arr
} else {
val mid = arr.length / 2
val (left, right) = arr.splitAt(mid)
merge(mergeSort(left), mergeSort(right))
}
}
val arr = Array(49, 38, 65, 97, 76, 13, 27, 101, 34, 119, 1)
val sortedArr = mergeSort(arr)
println(sortedArr.mkString(", "))
```
输出结果:
```
1, 13, 27, 34, 38, 49, 65, 76, 97, 101, 119
```
这里使用了递归的方式实现归并排序,将数组分成左右两个子数组,然后分别对左右两个子数组进行排序,最后将排序好的左右两个子数组进行合并。其中合并的过程需要用到额外的空间,因此在实现时需要新建一个数组来存储合并后的结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)