查找与排序问题：在一个整型数组中（长度至少为100001，其中下标0处留作它用），随机生成待查找与排序的数据，实现起泡排序，简单选择排序，直接插入排序，二分非递归查找以及带哨兵的顺序查找算法

查找与排序问题是计算机科学基础中的经典课题，通常涉及数据组织、搜索和比较操作。在这个大型整数数组（例如，长度为100001）中，我们可以按照以下步骤实现各种排序和查找算法：

1. **起泡排序**（Bubble Sort）：这是一种简单的排序算法，通过不断交换相邻元素如果它们的顺序错误，直到整个序列有序。虽然效率较低，适合教学演示，不适合大数据。

- 遍历数组多次，每次遍历时比较并交换相邻的元素，直到不再有需要交换的情况。

2. **简单选择排序**（Selection Sort）：每次从未排序部分选择最小（大）的元素放到已排序部分。效率同样不高，但代码简洁。

- 分两步：内层循环找到未排序区间的最小值；外层循环移动这个最小值到已排序区间尾部。

3. **直接插入排序**（Insertion Sort）：将每个元素插入到其前面已排序部分的正确位置。对于小型数据集效果良好，但对于大规模数据则效率低下。

- 比较新元素和已排序元素，然后逐步将新元素向前移动。

4. **二分查找**（Binary Search，适用于有序数组）：利用数组已经排序的特点，通过反复将搜索区间缩小一半来进行查找。时间复杂度为O(log n)。

5. **带哨兵的顺序查找**（Sentinel Search，适用于无序数组）：在数组开头添加一个特殊的“哨兵”元素，便于快速判断查找范围。从第一个元素开始逐个比较，直到找到目标或到达哨兵。

为了实现这些算法，你需要编写相应的函数，并注意性能优化和边界条件处理。以下是简化的伪代码示例：

def bubble_sort(arr):
    # [...]
    
def selection_sort(arr):
    # [...]
    
def insertion_sort(arr):
    # [...]

def binary_search(arr, target):
    # 使用二分查找算法...

def sentinel_search(arr, target):
    sentinel = arr[0]
    for i in range(1, len(arr)):
        if arr[i] == target or arr[i] > sentinel:
            return i
    return -1