排序算法

import java.io.PrintWriter
import com.google.protobuf.Descriptors.FileDescriptor.InternalDescriptorAssigner
import scala.collection.mutable.ArrayBuffer
import scala.io.Source
import scala.util.Random
import scala.util.control.Breaks._

/**
  * 排序算法
  * 插入排序：直接插入排序
  * 选择排序：堆排序
  * 交换排序：冒泡排序
  * 交换排序：快速排序
  * 选择排序：直接选择排序
  * 归并排序
  * 计数排序
  * 桶排序
  * 基数排序
  */
object SortArithmetic {
  def main(args: Array[String]): Unit = {
//    val timeStart = System.currentTimeMillis()
//
//    // 随机产生待排序数据，大量数据时才能看出区别
//    val num = 100000
//    val createData = new PrintWriter("D:\\BaiduNetdiskDownload\\spark\\in")
//    for (_ <- 1 to 30000000)
//      createData.println(Random.nextInt(num))
//    createData.close()
//    val file = Source.fromFile("D:\\BaiduNetdiskDownload\\spark\\in")
//    val preData = new ArrayBuffer[Int]
//    for (line <- file.getLines())
//      preData += line.toInt
//    // 排序
//    val sortedData = straightInsertionSort(preData)
//    // 输出到本地
//    val outData = new PrintWriter("D:\\BaiduNetdiskDownload\\spark\\out")
//    for (i <- sortedData)
//      outData.println(i)
//    outData.close()
//
//    // 统计时间
//    val timeEnd = System.currentTimeMillis()
//    println("straightInsertionSort runtime = " + (timeEnd - timeStart) / 1000.0 + " s")

    val in = ArrayBuffer(7, 3, 1, 4, 2, 6, 5)
    straightInsertionSort(in)
    println(in)
  }

  /**
    * 直接插入排序
    * 遍历数组，调整当前元素到合适的位置，即已遍历部分有序
    */
  def straightInsertionSort(inputData: ArrayBuffer[Int]): Unit = {
    for (i <- 1 until inputData.length) {
      val x = inputData(i)
      var j = i - 1
      while (j >= 0 && x < inputData(j)) {
        inputData(j + 1) = inputData(j)
        j = j - 1
      }
      inputData(j + 1) = x
    }
  }

  /**
    * 构造大顶堆
    * @param inputData 无序数组
    * @param m 最后一个非叶子节点的下标
    * @param j 数组最后一个元素的下标
    */
  def heapify(inputData: ArrayBuffer[Int], m: Int, j: Int): Unit = {
    // 最后一个非叶子节点下标，值
    var i = m
    val x = inputData(i)
    // 最后一个非叶子节点对应的叶子下标（后一个）
    var k = 2 * i

    breakable {
      // 调用循环终止 break 方法
      while (k <= j) {
        if (k < j)
          if (inputData(k) < inputData(k + 1)) k = k + 1
        if (x >= inputData(k)) break
        else {
          inputData(i) = inputData(k)
          i = k
          k = 2 * i
        }
      }
    }
    inputData(i) = x
  }

  /**
    * 堆排序
    * 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
    * 将堆顶元素与末尾元素交换，将最大的元素沉到数组末端
    * 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素
    * 反复执行调整 + 交换步骤，直到得到有序序列
    * @return
    */
  def heapSort(inputData: ArrayBuffer[Int]): ArrayBuffer[Int] = {
    var i = inputData.length / 2
    while (i >= 1) {
      heapify(inputData, i - 1, inputData.length - 1)
      i = i - 1
    }
    var j = inputData.length - 1
    while (j > 0) {
      val x = inputData(0)
      inputData(0) = inputData(j)
      inputData(j) = x
      heapify(inputData, 0, j - 1)
      j = j - 1
    }
    inputData
  }

  // 冒泡排序
  def bubblingSort(inputData: ArrayBuffer[Int]): ArrayBuffer[Int] = {
    for (j <- 0 to inputData.length - 3)
      for (i <- 0 to inputData.length - 2 - j) {
        if (inputData(i) > inputData(i + 1)) { //判断前一个元素是否大于后一个，如果大于，则交换
          val temp = inputData(i + 1)
          inputData(i + 1) = inputData(i)
          inputData(i) = temp
        }
      }
    inputData
  }

  // 快速排序
  def qksort(inputData: ArrayBuffer[Int]): ArrayBuffer[Int] = {
    def qsort1(inputData: ArrayBuffer[Int], left: Int, right: Int): Unit = {
      if (left < right) {
        var i = left
        var j = right
        val x = inputData(i)
        while (i < j) {
          while (i < j && inputData(j) > x) j = j - 1 /* 从右向左找第一个小于x的数 */
          if (i < j) {
            inputData(i) = inputData(j)
            i = i + 1
          }
          while (i < j && inputData(i) < x) i = i + 1 /* 从左向右找第一个大于x的数 */
          if (i < j) {
            inputData(j) = inputData(i)
            j = j - 1
          }
        }
        inputData(i) = x
        qsort1(inputData, left, i - 1) /* 递归调用 */
        qsort1(inputData, i + 1, right)
      }
    }
    qsort1(inputData, 0, inputData.length - 1)
    inputData
  }


  // 选择排序
  def SelectionSort(inputData: ArrayBuffer[Int]): ArrayBuffer[Int] = {
    for (i <- 0 until inputData.length - 1) {
      var index = i
      var value = inputData(i)
      for (j <- i + 1 until inputData.length) {
        if (value > inputData(j)) {
          index = j
          value = inputData(j)
        }
      }
      if (index != i) {
        inputData(index) = inputData(i)
        inputData(i) = value
      }
    }
    inputData
  }

  // 归并排序
  def merge(a: List[Int], b: List[Int]): List[Int] = (a, b) match {
    case (Nil, _) => b
    case (_, Nil) => a
    case (x :: xs, y :: ys) =>
      if (x <= y) x :: merge(xs, b)
      else y :: merge(a, ys)
  }
//  InternalDescriptorAssigner
  def mergeSort(lst: List[Int]): List[Int] = {
    if (lst.length < 2) lst
    else {
      val (first, second) = lst.splitAt(lst.length / 2)
      merge(mergeSort(first), mergeSort(second))
    }
  }

  // 计数排序
  def Countingsort(inputData: ArrayBuffer[Int], k: Int): Array[Int] = {
    // k表示有所输入数字都介于0到k之间
    val temp = new Array[Int](k)
    // 临时存储区
    val outdata = new Array[Int](inputData.length)
    val len = temp.length
    for (i <- 0 until len) {
      // 初始化
      temp(i) = 0
    }
    for (i <- inputData.indices) {
      temp(inputData(i)) = temp(inputData(i)) + 1
    }
    for (i <- 1 until len) {
      temp(i) = temp(i) + temp(i - 1)
    }
    // 把输入数组中的元素放在输出数组中对应的位置上
    var n = inputData.length - 1
    while (n >= 0) {
      // 从后往前遍历
      outdata(temp(inputData(n)) - 1) = inputData(n)
      temp(inputData(n)) = temp(inputData(n)) - 1
      n = n - 1
    }
    outdata
  }

  // 桶排序
  def bucketsort(inputData: ArrayBuffer[Int], max: Int): ArrayBuffer[Int] = {
    var buckets = new Array[Int](max)
    for (i <- inputData.indices) //计数
      buckets(inputData(i)) = buckets(inputData(i)) + 1
    var j = 0
    for (i <- 0 until max)
      while (buckets(i) > 0) {
        inputData(j) = i
        j = j + 1
        buckets(i) = buckets(i) - 1
      }
    buckets = null
    inputData
  }

  /** 基数排序函数
    * B表示要排序的数组
    * d表示每一位数字的范围（这里是10进制数，有0~9一共10种情况）
    */
  def RadixSort(inputData: ArrayBuffer[Int], d: Int): ArrayBuffer[Int] = {
    //n用来表示当前排序的是第几位
    var n = 1
    //hasNum用来表示数组中是否有至少一个数字存在第n位
    var hasNum = false
    /** 二维数组temp用来保存当前排序的数字
      * 第一维d表示一共有d个桶
      * 第二维B.length表示每个桶最多可能存放B.length个数字
      */
    val temp = Array.ofDim[Int](d, inputData.length)
    val order = new Array[Int](d)
    breakable {
      while (true) {
        // 判断是否所有元素均无比更高位，因为第一遍一定要先排序一次，所以有n!=1的判断
        if (n != 1 && !hasNum) {
          break
        }
        hasNum = false
        // 遍历要排序的数组，将其存入temp数组中（按照第n位上的数字将数字放入桶中）
        for (i <- inputData.indices) {
          val x = inputData(i) / (n * 10)
          if (x != 0) hasNum = true
          val lsd = x % 10
          temp(lsd)(order(lsd)) = inputData(i)
          order(lsd) = order(lsd) + 1
        }
        // k用来将排序好的temp数组存入B数组（将桶中的数字倒出）
        var k = 0
        for (i <- 0 until d) {
          if (order(i) != 0) {
            var j = 0
            while (j < order(i)) {
              inputData(k) = temp(i)(j)
              k = k + 1
              j = j + 1
            }
          }
          order(i) = 0
        }
        n = n + 1
      }
    }
    inputData
  }

}