/**
 * 冒泡排序升序，將最大的冒泡到最后
 */
fn bubble_sort1<T: Ord>(arr: &mut [T]) -> &mut [T] {
  let len = arr.len();
  println!("array size is {:?}", arr.len());
  for i in 0..len {
    println!("i:{}", i);
    for j in 0..len - i - 1 {
      println!("i=:{}, j=:{}", i, j);
      if arr[j] > arr[j + 1] {
        // 可以直接使用swap
        arr.swap(j, j + 1);
      }
    }
  }
  // println!("array is sorted {:?}", arr);
  return arr;
}

/**
 * 冒泡排序降序，將最小的冒泡到最后。
 * 且增加是否交換的標(biāo)志，針對已排序做優(yōu)化。
 */
fn bubble_sort2<T: Ord>(arr: &mut [T]) -> &mut [T] {
  let len = arr.len();
  let mut flag = true;
  let mut i = 0;
  while i < len && flag == true {
    flag = false;
    println!("i:{}", i);
    for j in 0..len - i - 1 {
      // 當(dāng)前項跟后一項進(jìn)行比較，如果需要交換
      // 當(dāng)沒有任何一項需要交換時則終止循環(huán)
      println!("i=:{}, j=:{}", i, j);
      if arr[j] < arr[j + 1] {
        flag = true;
        arr.swap(j, j + 1);
      }
    }
    i = i + 1;
  }
  return arr;
}
fn main() {
  println!("bubbleSort:");
  let mut data1 = [2, -1, 10, 5, 8, 11];
  println!("sort1 before: {:?}", data1);
  bubble_sort1(&mut data1);
  println!("sort1 after: {:?}", data1);
  let mut data2 = [2, -1, 10, 5, 8, 11];
  println!("sort2 before: {:?}", data2);
  bubble_sort2(&mut data2);
  println!("sort2 after: {:?}", data2);
}