排序-4.归并排序(mergeSort)
程序员文章站
2022-06-04 16:30:01
...
归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案“修补”在一起,即分而治之)。
代码实现
package chapter18.sort
import java.text.SimpleDateFormat
import java.util.Date
object MergeSort {
def main(args: Array[String]): Unit = {
println("---------------------功能测试-------------------------")
val arr1 = Array(-9, 78, 0, 23, -567, 70)
val temp1 = new Array[Int](arr1.length) // 临时的数组
mergeSort(arr1, 0, arr1.length - 1, temp1)
println("归并排序后的代码")
println(arr1.mkString(" "))
println("---------------------性能测试-------------------------")
//创建一个80000个随机数据的数组
//使用归并排序,时间小于1秒
val random = new util.Random()
val arr = new Array[Int](8000000)
val temp = new Array[Int](arr.length) // 临时的数组
for (i <- 0 until 8000000) { //循环生成随机数
arr(i) = random.nextInt(8000000)
}
println("排序前")
val now: Date = new Date()
val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")
val date = dateFormat.format(now)
println("排序前时间 = " + date) //输出时间
//println(arr.mkString(" "))
mergeSort(arr, 0, arr.length - 1, temp)
println("排序后")
//println(arr.mkString(" "))
val now2: Date = new Date()
val date2 = dateFormat.format(now2)
println("排序后时间 = " + date2) //输出时间
}
/**
* 这是一个归并排序
*
* @param arr 待排序的数组
* @param left 最初的左边的下标 0
* @param right 最初的右边的下标 arr.length - 1
* @param temp 临时数组,事先开辟好,它的大小与待排序数组的大小一致。
*/
def mergeSort(arr: Array[Int], left: Int, right: Int, temp: Array[Int]): Unit = {
if (left < right) { // 如果left < right 就可以继续分
val mid = (left + right) / 2
mergeSort(arr, left, mid, temp) // 递归将左边的数据做成一个有序列表
mergeSort(arr, mid + 1, right, temp) //递归将右边的数据做成一个有序列表
//merge 是合并操作
merge(arr, left, mid, right, temp)
}
}
/**
* 合并部分
*
* @param arr 待排序的数组
* @param left 最初的左边的下标 0
* @param mid 中间位置下标
* @param right 最初的右边的下标 arr.length - 1
* @param temp 临时数组,事先开辟好,它的大小与待排序数组的大小一致。
*/
def merge(arr: Array[Int], left: Int, mid: Int, right: Int, temp: Array[Int]): Unit = {
var i = left //i 就是左边指针[索引]
var j = mid + 1 // j 为右边指针
var t = 0 //temp数组的下标
while (i <= mid && j <= right) {
//如果当前左边的有序列表的值小于当前右边有序列表的值,就把值拷贝到temp数组
if (arr(i) <= arr(j)) {
temp(t) = arr(i)
t += 1
i += 1
} else {
//如果当前右边的有序列表的值小于当前左边有序列表的值,就把值拷贝到temp数组
temp(t) = arr(j)
t += 1
j += 1
}
}
while (i <= mid) {
//如果左边有序列表有剩余数据,就依次拷贝到temp数组
temp(t) = arr(i)
t += 1
i += 1
}
while (j <= right) {
//如果右边有序列表有剩余数据,就依次拷贝到temp数组
temp(t) = arr(j)
t += 1
j += 1
}
//下面代码是完成将本次的temp的数据拷贝到arr中
t = 0
var tempLeft = left
while (tempLeft <= right) {
arr(tempLeft) = temp(t)
t += 1
tempLeft += 1
}
}
}
运行结果
上一篇: 上班族如何让自己精力充沛 摆脱身体亚健康
下一篇: 冬天怎么给宝宝喂食 宝妈有计谋