Bioinfo_Homework_02

# Q: 有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？
#    要求时间和空间复杂度尽可能低。

# A1: 使用任意一种排序算法，给原数组排序，然后遍历排好序的数组，
#     并对两个相邻元素求差，最终得到最大差值。

array = c(2,6,3,4,5,10,9)

# 计算差值
sort2Find = function(fun,array){
  sorted_array = fun(array) # 替换成别的排序方法
  temp = 0 # 初始化差值计数器
  for (i in 1:(length(array)-1)){ # 遍历数组
    if (temp < (sorted_array[i+1]-sorted_array[i])){
      temp = sorted_array[i+1]-sorted_array[i] # 如果找到更大的差值，则覆盖
    }
  }
  return(temp)
}

# A1.1 冒泡排序
bubble = function(array){
  n = length(array) # 数组长度
  for (i in 1:(n-1)){ # 注意要减去1
    for (j in 1:(n-i)){ # 内循环
      if (array[j+1] < array[j]){ # 如果右边的比左边的大
        temp = array[j+1] # 左右互换
        array[j+1] = array[j]
        array[j] = temp
      }
    }
  }
  return(array)
}

# A1.2 选择排序
select = function(array){
  n = length(array) # 数组长度
  for (i in 1:(n-1)){ # 外层循环遍历数组
    k = i
    for (j in (i+1):n){ # 内层循环遍历选择元素之后的数组
      if (array[j] < array[k]){ # 如果小于选择的元素
        k = j # 覆盖k
      }
    }
    temp = array[i] # 互换数组下标为i和k的元素
    array[i] = array[k]
    array[k] = temp
  }
  return(array)
}

# A1.3 插入排序
insert = function(array){
  n = length(array) # 数组长度
  for (i in 2:n){ # 第一待排序序列第一个元素看做一个有序序列
    base = array[i] # 第二个元素到最后一个元素当成是未排序序列
    j = i-1
    while(j>0 && array[j] > base){
      array[j+1] = array[j]
      j = j-1
    }
    array[j+1] = base
  }
  return(array)
}

# A1.4 快速排序
quick = function(array) {
  n = length(array) # 获取数组长度
  if (n <= 1) {
    return(array) # 如果数组长度小于等于1, 则返回整个数组
  } else {
    pivot = array[1] # 取第一个元素为枢轴元素
    smaller = array[array < pivot] # 比枢轴小的元素为一个数组
    equal = array[array == pivot] # 和枢轴一样大的元素为一个数组
    larger = array[array > pivot] # 比枢轴大的元素为一个数组
    return(c(quick(smaller), equal, quick(larger))) # 递归
  }
}

sort2Find(insert, array) # 使用插入排序
sort2Find(select, array) # 使用选择排序
sort2Find(bubble, array) # 使用冒泡排序
sort2Find(quick, array) # 使用快速排序

################################################################################
# A2 计数排序
array = c(4,5,8,8,8,8,9,10,15,16,16)

countFind = function(array){
  # 最大最小取差值
  max = max(array)
  min = min(array)
  minus = max-min+1
  # 创建新数组
  nums = array(0,c(minus))
  # 遍历原数组array, 统计个数
  for (num in array){
    nums[num-min+1] = nums[num-min+1] + 1
  }
  # 统计连续最多的0的个数
  temp = 0
  count0_max = 0
  for (num in nums){ # 遍历新数组
    if (num == 0){ # 如果遇到0, 计数器temp加1
      temp = temp + 1
    }
    if (num != 0){
      # 遇到不是0, 判断本轮统计的连续0个数是否是最大
      if (count0_max < temp){
        count0_max = temp # 如果比之前的大则覆盖
        temp = 0 # 重新计数， 计数器清零
      }
    }
  }
  # 返回最大的差值
  return(count0_max + 1)
}

countFind(array)

array = c(2,6,3,4,5,10,9)

> sort2Find(insert, array) # 使用插入排序
[1] 3
> sort2Find(select, array) # 使用选择排序
[1] 3
> sort2Find(bubble, array) # 使用冒泡排序
[1] 3
> sort2Find(quick, array) # 使用快速排序
[1] 3

> array = c(4,5,8,8,8,8,9,10,15,16,16)

> countFind(array) # 使用计数排序
[1] 5