Scala冒泡排序、快速排序、插入排序

冒泡排序：

所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。 这个操作称为分区(partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置

插入排序：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码：

package Test2/**  * Created by zhouzhongqing on 2017/2/7 0007.  */object ArithmeticTest {  def main(args: Array[String]): Unit = {      //bubblingSort(0);    //  insertSort(0);    //val array = Array(2,4,3,5,8,66,7,22,12,11);    val array = Array(3,2);    quickSort(array, 0, array.length - 1);// 快速排序    for ( i <- 0 to (array.length - 1) ) {      PRintln(array(i),"----",array.length);    }  }/**  * 快速排序  * 是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，  * 其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  *param data  *            目标数组  *param start  *            起始位  * param end  *            结束位  * */  def quickSort( data: Array[Int] , start : Int , end : Int ) : Int = {    // 设置关键数据key为要排序数组的第一个元素，    // 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小    val key = data(start);    // 设置数组左边的索引，往右移动比key大的数    var i = start;    // 设置数组右边的索引，往左移动比key小的数    var j = end;    // 如果左边索引比右边索引小，则还有数据没有排序    while (i < j){        while(data(j) > key && j > i){ //  2  3   1 0            j = j - 1;        }      data(i) = data(j);//data(0) = 2      while (data(i) < key && i < j ){// 2 3    0  1        i = i+1;// i = 1      }      data(j) = data(i);// data(0) = 2    }    //此时 i == j    data(i) = key;  // data(1) = 3    //递归调用    if(i - 1 > start){      // 递归调用，把key前面的完成排序      quickSort(data, start, i - 1);    }    if(i + 1 < end){      // 递归调用，把key后面的完成排序      quickSort(data, i + 1, end);    }    return 0;  }/**  * 插入排序，从小到大排序  * 这个算法从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。  * */  def insertSort( a:Int ) : Int = {    val array = Array(2,4,3,5,8,66,7,22,12,11);    for ( i <-1 to (array.length -1 ) ) {//这个算法从数组的第二个元素开始循环 j <- 1        var arrayVal = array(i);        var j = i - 1;//得到前一位元素      // while 循环执行 2      while( j >= 0 &&  array(j) > arrayVal){//判断前面的是否大于arrayVal        array(j+1) = array(j);//如果大于，将它放后面        j = j-1;     //   println(array(j),"----",array.length,"j:" , j);      }      array(j+1) = arrayVal;//如果一次都不满足while的条件，arrayVal还在原来的位置；如果满足过arrayVal会放在前面    }    for ( i <- 0 to (array.length - 1) ) {      println(array(i),"----",array.length);    }    return 0;  }  /**    * 冒泡排序    *从大到小排列    * 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。    */  def bubblingSort( a:Int ) : Int = {    val array = Array(2,4,3,5,8,66,7,22,12,11);    for ( j <-0 to (array.length - 3) ) {      for (i <- 0 to (array.length - 2 - j)) {        //     println(array(i),"----",array.length);        if (array(i) > array(i + 1)) {//判断前一个元素是否大于后一个          var temp = 0;          temp = array(i + 1);//赋值          array(i + 1) = array(i);//如果前一个元素大，把他移动到后面          array(i) = temp;//把后面一个移动到前面        }      }    }    for ( i <- 0 to (array.length - 1) ) {      println(array(i),"----",array.length);    }    return 0;  }}