跳到文档正文
数据结构 / 一维数组
03 / 18
我们的可视化工具通过直观的图形界面将数组操作变得生动形象。在处理一维数组时，每个元素都表示为一个矩形，其值显示在内部。这些元素按水平顺序排列，让您能够一目了然地理解数组的结构。
我们的工具的一个关键特性是其动态索引跟踪功能。当您的代码执行数组操作（如访问或修改元素）时，该工具会自动检测这些操作并突出显示相关元素。随着索引的变化，突出显示会在元素之间平滑过渡，帮助您理解代码如何遍历数组。
这种视觉反馈对于学习数组操作概念或调试数组相关算法特别有用。
让我们来看看一些常见的数组算法及其可视化效果：
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
bubble_sort([64, 34, 25, 12, 22, 11, 90])
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
selection_sort([64, 34, 25, 12, 22, 11, 90])
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
insertion_sort([64, 34, 25, 12, 22, 11, 90])
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
shell_sort([64, 34, 25, 12, 22, 11, 90])
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
# 计数出现次数
for num in arr:
count[num] += 1
# 重建排序后的数组
idx = 0
for i in range(len(count)):
while count[i] > 0:
arr[idx] = i
idx += 1
count[i] -= 1
counting_sort([3, 2, 3, 4, 6, 5, 1, 2, 4, 5])
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 在已排序数组上的使用示例
binary_search([11, 12, 22, 25, 34, 64, 90, 100], 90)
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
linear_search([64, 34, 25, 12, 22, 11, 90], 25)
def max_average(arr, k):
# 找出k个连续元素的最大平均值
window_sum = sum(arr[:k])
max_avg = window_sum / k
for i in range(k, len(arr)):
window_sum = window_sum - arr[i-k] + arr[i]
max_avg = max(max_avg, window_sum / k)
return max_avg
max_average([1, 12, -5, -6, 50, 3], 4)
def longest_subarray(arr, target):
# 找出和小于等于目标值的最长子数组
left = curr_sum = max_len = 0
for right in range(len(arr)):
curr_sum += arr[right]
while curr_sum > target:
curr_sum -= arr[left]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
longest_subarray([1, 2, 3, 4, 5], 10)
def build_prefix_sum(arr):
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]
# 使用示例
arr = [1, 2, 3, 4, 5]
prefix = build_prefix_sum(arr)
range_sum(prefix, 1, 3) # 计算索引1到3之间元素的和
def rotate_array(arr, k):
def reverse(arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
k = k % len(arr)
reverse(arr, 0, len(arr)-1)
reverse(arr, 0, k-1)
reverse(arr, k, len(arr)-1)
rotate_array([1, 2, 3, 4, 5, 6, 7], 3)