第十七课：数据结构上

第十七课：数据结构上内容摘要：

当我们对一个数组执行二分查找时，最多的查找次数是满足 n 2^k的最小整数 k， 比如：当数组长度为 20时，那么使用二分法的查找次数最多为 5次，即： 2^5 20 因此可以得出二分法的最差及平均情况的复杂度为 O(logn)。 课堂练习 问题描述： 有一个有序数组 :{1， 2， 3， 4， 5， 6， 7，8， 9， 10}，请分别： 以线性法查找 7的下标。 以二分法查找 4的下标。 3 排序算法 1 选择排序 首先在数组中查找最小值，如果该值不在第一个位置，那么将其和处在第一个位置的元素交换，然后从第二个位置重复此过程，将剩下元素中最小值交换到第二个位置。 当到最后一位时，数组排序结束。 static int[] selectionSort(int[] arr){ int tmp, small。 for(int i = 0。 i 1。 i++){ small = i。 for(int j = i + 1。 j。 j++) if(arr[j] arr[small]) small = j。 if(small != i){ tmp = arr[i]。 arr[i] = arr[small]。 arr[small] = tmp。 } print(arr)。 } return arr。 }* 课堂练习 问题描述：对一个有 10个元素的整数数组用选择法排序 ,该数组元素由随机数产生 . 从上面代码我们可以看出，假设数组大小为 n，外循环共执行 n1次；那么第一次执行外循环时，内循环将执行 n1次；第二次执行外循环时内循环将执行 n2次；最后一次执行外循环时内循环将执行1次，因此我们可以通过代数计算方法得出增长函数为： (n 1) + (n 2) + (n 3) + ….. + 1 = n(n 1) / 2 = 1/2 * n^2 + 1/2 * n，即可得出复杂度为：O(n^2)。 我们可以分析得知，当数组非常大时，用于元素交换的开销也相当大。 这都属于额外开销，是呈线性增长的。 注意：如果是对存储对象的集合进行排序，则存储对象必须实现 Comparable接口，并通过 pareTo()方法来比较大小。 2 冒泡排序 从数组的第一个元素开始，每次比较一对元素，一直到数组结束，如果比较的这对元素顺序不对，那么交换位置。 这个过程会使数组中的最大 (最小 )元素逐渐冒到数组的最后 (最前 ). static int[] bubbleSort(int[] arr){ int flag = 1, tmp。 int n =。 for(int i = 1。 i n amp。 amp。 flag == 1。 i。