欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序-4.归并排序(mergeSort)

程序员文章站 2022-06-04 16:30:01
...

归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案“修补”在一起,即分而治之)。
排序-4.归并排序(mergeSort)
排序-4.归并排序(mergeSort)

代码实现

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
    }


  }
}

运行结果

排序-4.归并排序(mergeSort)