function ArrayList() {

  this.array = [];

  ArrayList.prototype.insert = function (item) {
      this.array.push(item);
  }

  ArrayList.prototype.toString = function (item) {
      return this.array.join('-');
  }


  //冒泡排序
  ArrayList.prototype.bubuleSort = function () {


      for (var i = 0; i < this.array.length; i++) {
          for (var j = i + 1; j < this.array.length; j++) {

              if (this.array[i] > this.array[j]) {
                  var temp = this.array[j];
                  this.array[j] = this.array[i];
                  this.array[i] = temp;
              }
          }
      }


  }
  //选择排序
  ArrayList.prototype.selectSort = function () {

      for (var j = 0; j < this.array.length; j++) {

          var minIndex = j;
          for (var i = minIndex + 1; i < this.array.length; i++) {
              if (this.array[minIndex] > this.array[i]) {
                  minIndex = i;
              }
          }
          var temp = this.array[j];
          this.array[j] = this.array[minIndex];
          this.array[minIndex] = temp;
      }
  }


  //插入排序
  ArrayList.prototype.insertSort = function () {
      //优化写法
      for (var i = 1; i < this.array.length; i++) {
          //标记值
          var temp = this.array[i];
          //选出的位置
          var j = i;

          //标记的位置 和 前一个比较 小于左移知道找到正确的位置
          while (temp < this.array[j - 1] && j > 0) {
              this.array[j] = this.array[j - 1]
              j--;
          }

          this.array[j] = temp;
      }

  }


  //希尔排序
  ArrayList.prototype.shellSort = function () {

      //间距
      var gap = Math.floor(this.array.length / 2);

      while (gap >= 1) {

          //以gap为间距 进行分组 对分组进行插入排序
          for (var i = gap; i < this.array.length; i++) {

              var j = i;
              var temp = this.array[i];
              while (temp < this.array[j - gap] && j > gap - 1) {
                  this.array[j] = this.array[j - gap]
                  j -= gap;

              }

              this.array[j] = temp;
          }

          gap = Math.floor(gap / 2)
      }

  }

  // //快排
  ArrayList.prototype.fastSort = function () {

      if (this.array.length == 0) return;
      this.fast(0, this.array.length - 1);

  }
  //
  ArrayList.prototype.fast = function (left, right) {
      if (left >= right) return;

      var medianValue = this.median(left, right);

      var i = left;
      var j = right-1;
      while (true) {
          //找从左边第一个大于或等于midan 的位置
          while (this.array[++i] < medianValue) {
          }
          //找到从右边第一个小于或等于midan 的位置
          while (this.array[--j] > medianValue) {
          }

          if (i < j) {//交换位置
              this.swap(i, j);
          }else {
              break;
          }            
      }

      //枢纽放到正确的位置
      this.fast(i, right - 1);

      //分而治之
      this.fast(left, i-1);
      this.fast(i+1, right);



  }

  //交换位置
  ArrayList.prototype.swap = function (n, m) {
      var temp = this.array[n];
      this.array[n] = this.array[m];
      this.array[m] = temp;
  }

  //找枢纽位置  右侧前面的一个位置
  ArrayList.prototype.median = function (left, right) {
      var center = Math.floor((left + right) / 2);

      if (this.array[left] > this.array[right]) {
          this.swap(left, right);
      }
      if (this.array[left] > this.array[center]) {
          this.swap(left, center);
      }
      if (this.array[center] > this.array[right]) {
          this.swap(center, right);
      }

      //把中间位置 放到右边前一个位置
      this.swap(center,right-1);

      return this.array[right - 1];

  }

}