数据结构和算法

1、数组和链表区别
（1）物理存储结构不同。链表与数组在计算中存储元素采用不同的存储结构，数组是顺序存储结构，链表是链式存储结构；
（2）内存分配方式不同。数组的存储空间一般采用静态分配，链表的存储空间一般采用动态分配；
（3）元素的存取方式不同。数组元素为直接存取，链表元素的存取需要遍历链表；
（4）元素的插入和删除方式不同。数组进行元素插入和删除时，需要移动数组内的元素，链表进行元素插入和删除时无需移动链表内的元素

2、冒泡排序：
冒泡排序每次只会比较相邻的两个元素，只有在不满足要求的大小关系情况下，才会发生交换行为。一次冒泡迭代会让至少一个元素移动到它最终应该在的位置上，最多n次冒泡迭代，当某次冒泡迭代没有发生元素的交换行为，就可以判定数列已经完成了排序。

// 最多需要迭代n次冒泡
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(data[j] > data[j+1]){
// 不满足从小到大的关系，需要交换
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}

3、二分查找

func twoSearch(arr:int[], low:int, high:int target:int) {
mid = (high + low) / 2
while(low <= high) {
if (target < arr[mid]) {
high = mid - 1
}else if (target > arr[mid]) {
low = mid + 1
}else {
return mid
}
}
return -1
}