Scala中Array和List的区别说明

package com.tingfeng.scala.testimport scala.annotation.tailrecimport scala.util.{Random, Sorting}/**  * 快速排序测试  */object SortTest {  /**    * 初始化一个数组，产生随机数字填充    * @param size    * @return    */  def initRandomList(size :Int):List[Int]={    val random = new Random()    def initList(size :Int,random: Random):List[Int] = size match {      case 0 => Nil      case 1 => List(random.nextInt())      case s:Int =>        val value = s / 2        if( s % 2 == 0) {          initList(value,random) ++ initList(value,random)        }else{          initList(value,random) ++ initList(value + 1,random)        }    }    initList(size,random)  }  /**    * 打印出使用的时间    * @param call    */  def printTime(call : => Unit,tag: String = ""){    val startTime = System.currentTimeMillis()    println(tag)    call    println    println(s"use time : ${System.currentTimeMillis() - startTime}\n")  }  /**    * 交换数组中两个位置的值，经过测试这种按位与的方式比普通建立变量交换的效率更高    * @param array    * @param x    * @param y    */  def swap(array: Array[Int],x:Int,y:Int):Unit ={      val t = array(x) ^ array(y)      array(x) = t ^ array(x)      array(y) = t ^ array(y)  }  /**    * 将传入的值直接返回,并且执行逻辑    * @param call    * @param any    * @tparam A    */  def doThing[A<:Any](any: A,call: A => Unit):A = {      call(any)      any  }  /**    * 打印列表    */  def printList[A<%Seq[Any]](seq:A,size :Int = 10):Unit={    seq.splitAt(size)._1.foreach(it => print(s"$it,"))  }  def shuffleIntSeq(seq: Array[Int],size: Int):Unit={      val random = new Random()      val maxSize = size/2      for(i <- 0 to maxSize){          swap(seq,i,maxSize + random.nextInt(maxSize))      }  }  def main(args: Array[String]): Unit = {    val size = 5000000    val printSize = 10    val list = initRandomList(size)    //打印出钱100个，和List快速排序的时间花费    printTime(printList[List[Int]](qSortList(list),Math.min(10,size)),"qSortList")    val array = list.toArray    printTime(printList[Array[Int]](doThing[Array[Int]](array,Sorting.quickSort),Math.min(printSize,size)),"Sorting.quickSort")    shuffleIntSeq(array,size)    printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray1),Math.min(printSize,size)),"qSortArray1")    shuffleIntSeq(array,size)    printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray2),Math.min(printSize,size)),"qSortArray2")    shuffleIntSeq(array,size)    printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray3),Math.min(printSize,size)),"qSortArray3")    shuffleIntSeq(array,size)    printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray4),Math.min(printSize,size)),"qSortArray4")  }  /**    * 对List快速排序    * @param list    * @return    */  def qSortList(list: List[Int]):List[Int] = list match {    case Nil => Nil    case head :: other =>      val (left, right) = other.partition(_ < head)      (qSortList(left) :+ head) ++ qSortList(right)  }  /**    * 通过每次比较数组‘head'值与其余值的方式直接实现    * 比‘head'小的值移动到其前，比‘head'大的移动到其之后    * @param array    */  def qSortArray1(array: Array[Int]):Unit = {    def sort(ay : Array[Int],start: Int,end: Int):Unit={      if(start >= end) {        return      }      val head = ay(start)      var spliteIndex = start      for (i <- start + 1 to end){        if(ay(i) < head){          swap(array,spliteIndex,i)          spliteIndex += 1        }      }      if(start != spliteIndex){        sort(ay, start, spliteIndex)      }      if(start == spliteIndex){        spliteIndex += 1      }      if(spliteIndex != end){        sort(ay, spliteIndex, end)      }    }    sort(array,0,array.size - 1)  }  /**    * 将数据以中线拆分左右两部分，交换值，使得右边值比左边大，    * 再以左或者右边交换的界限分为两部分做递归    * @param array    */  def qSortArray2(array: Array[Int]) {    def sort(l: Int, r: Int) {      val pivot = array((l + r) / 2)      var lv = l; var rv = r      while (lv <= rv) {        while (array(lv) < pivot) lv += 1        while (array(rv) > pivot) rv -= 1        if (lv <= rv) {          swap(array,lv, rv)          lv += 1          rv -= 1        }      }      if (l < rv) sort(l, rv)      if (rv < r) sort(lv, r)    }    sort(0, array.length - 1)  }  /**    * 系统自带的过滤函数,无法排序成功，因为filter返回的是引用    * @param xs    * @return    */  def qSortArray3(xs: Array[Int]): Array[Int] ={    if (xs.length <= 1){      xs    }else {      val pivot = xs(xs.length / 2)      val left = xs filter (pivot > _)      val cu = xs filter (pivot == _ )      val right = xs filter (pivot < _ )      Array.concat(        qSortArray3(left),cu,qSortArray3(right))    }  }  /**    * 系统自带的分割函数,无法排序成功，因为partition返回的是引用，数据量大的时候会栈溢出失败    * @param xs    * @return    */  def qSortArray4(array: Array[Int]): Array[Int] ={    if (array.length <= 1){      array    }else {      val head = array(0)      val (left,right) = array.tail partition  (_ < head )      Array.concat(qSortArray4(left),Array(head),qSortArray4(right))    }  }}