算法学习--排序与查找.docx

算法学习-排序与查找作者：qinzhaokun二分查找我们都知道二分查找算法，实际上二分查找以及其扩展应用是很广泛的。这里收集了一些和二分查找有关的有趣问题。强烈建议大家看完问题后最小化浏览器，先尝试自己去解决，然后再看代码，问题都不是太难。问题1描述给一个已经排序的数组，其中有N个互不相同的元素。要求使用最小的比较次数找出其中的一个元素。(你认为二分查找在排序数组里找一个元素是最优的算法的吗？)不需要太多的理论，这是一个典型的二分查找算法。先看下面的代码：int BinarySearch(int A, int l, int r, int key) int m; while( l = r ) m = l + (r-l)/2; if( Am = key ) /第一次比较 return m; if( Am key ) / 第二次比较 l = m + 1; else r = m - 1; return -1;理论上，我们最多需要 logN+1 次比较。仔细观察，我们在每次迭代中使用两次比较，除了最后比较成功的一次。实际应用上，比较也是代价高昂的操作，往往不是简单的数据类型的比较。减少比较的次数也是优化的方向之一。下面是一个比较次数更少的实现：/ 循环不变式： Al key/ 边界: |r - l| = 1/ 输入: Al . r-1int BinarySearch(int A, int l, int r, int key) int m; while( r - l 1 ) m = l + (r-l)/2; if( Am r )不断缩小，我们需要一个比较跟踪搜索状态。需要注意的，要保证我们恒等式（Al key）正确，后面还会用到循环不变式。问题2描述给一个有N个互不相同的元素的已排序数组，返回小于或等于给定key的最大元素。 例如输入为 A = -1, 2, 3, 5, 6, 8, 9, 10 key = 7,应该返回6.分析：我们可以用上面的优化方案，还是保持一个恒等式，然后移动 左右两个指针。最终 left指针会指向 小于或等于给定key的最大元素(根据恒等式Al key)。- 如果数组中所有元素都小于key，左边的指针left 会一直移动到最后一个元素。- 如果数组中所有元素都大于key，这是一个错误条件，无答案。- 如果数组中的所有元素都 1 ) m = l + (r - l)/2; if( Am = key ) l = m; else r = m; return Al;/ 初始调用int Floor(int A, int size, int key) / 如果 key A0 不符合条件 if( key A0 ) return -1; return Floor(A, 0, size, key);问题3描述给一个有重复元素的已排序数组，找出给定的元素key出现的次数，时间复杂度要求为logN.分析其实可以对上面的程序稍作修改，思路就是分别找出key 第一次出现的位置和最后一次出现的位置。/ 输入: 数组区间 l . r)/ 循环不变式: Al keyint GetRightPosition(int A, int l, int r, int key) int m; while( r - l 1 ) m = l + (r - l)/2; if( Am = key and Al keyint GetLeftPosition(int A, int l, int r, int key) int m; while( r - l 1 ) m = l + (r - l)/2; if( Am = key ) r = m; else l = m; return r;int CountOccurances(int A, int size, int key) / 找出边界 int left = GetLeftPosition(A, -1, size-1, key); int right = GetRightPosition(A, 0, size, key); / key有可能不存在，需要判断 return (Aleft = key & key = Aright)? (right - left + 1) : 0;问题4描述有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的最小元素所在的位置。例如：原数组 1,2,3,4,5,6,7,8,9,10， 旋转后的数组可能是 6,7,8,9,10, 1,2,3,4,5 ，也可能是 8,9,10,1,2,3,4,5,6,7 分析：我们不断的缩小 l 左指针和 r 右指针直到有一个元素。把上面划横线的作为第一部分，剩下的为第二部分。如果中间位置m落在第一部分，即Am Ar 不成立，我们排序掉区间 Am+1 . r。 如果中间位置m落在第二部分，即 Am Ar if( Al = Ar ) return l; while( l = r ) /终止条件 if( l = r ) return l; m = l + (r-l)/2; / m 可以落在第一部分或第二部分 if( Am Ar ) / (m i = r),可以排除 Am+1 . r r = m; else / min肯定在区间 (m i = r), / 缩小区间至 Am+1 . r l = m+1; return -1;int BinarySearchIndexOfMinimumRotatedArray(int A, int size) return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1);问题5描述有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的指定元素所在的位置。public class Solution public int search(int nums, int target) int l = 0; int r = nums.length-1; while(l r) int mid = l + (r-l)/2; if(target = numsmid) return mid; if(numsl numsr) if(numsmid target) l = mid+1; else r = mid-1; else if(numsmid numsmid & target = numsl & target l /1. 找到中间点，讲arr分为两部分: middle m = (l+r)/2 /2. 对一部分调用mergeSort : Call mergeSort(arr, l, m) /3.对第二部分调用mergeSort: Call mergeSort(arr, m+1, r) /4. 合并这两部分: Call merge(arr, l, m, r)堆排序堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。1.堆堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：Keyi=key2i+1 & Keyi=Key2i+1 & key=key2i+2即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆，满足Keyi=Key2i+1 & key=key2i+2称为大顶堆，满足 Keyi=key2i+1&Keyi=key2i+2称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。2.堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆)：1)将初始待排序关键字序列(R1,R2.Rn)构建成大顶堆，此堆为初始的无序区；2)将堆顶元素R1与最后一个元素Rn交换，此时得到新的无序区(R1,R2,Rn-1)和新的有序区(Rn),且满足R1,2.n-1=Rn;3)由于交换后新的堆顶R1可能违反堆的性质，因此需要对当前无序区(R1,R2,Rn-1)调整为新堆，然后再次将R1与无序区最后一个元素交换，得到新的无序区(R1,R2.Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。操作过程如下：1)初始化堆：将R1.n构造为堆；2)将当前无序区的堆顶元素R1同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。下面举例说明：给定一个整形数组a=16,7,3,20,17,8，对其进行堆排序。首先根据该数组元素构建一个完全二叉树，得到然后需要构造初始堆，则从最后一个非叶节点 ( 程序中size/2)开始调整，调整过程如下：20和16交换后导致16不满足堆的性质，因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。此时3位于堆顶不满堆的性质，则需调整继续调整 这样整个区间便已经有序了。从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R1.n中选择最大记录，需比较n-1次，然后从R1.n-2中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。void HeapAdjust(int *a,int i,int size) /调整堆 int lchild=2*i; /i的左孩子节点序号 int rchild=2*i+1; /i的右孩子节点序号 int max=i; /临时变量 if(i=size/2) /如果i是叶节点就不用进行调整 if(lchildamax) max=lchild; if(rchildamax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size); /避免调整之后以max为父节点的子树不是堆 void BuildHeap(int *a,int size) /建立堆 int i; for(i=size/2;i=1;i-) /非叶节点最大序号值为size/2 HeapAdjust(a,i,size); void HeapSort(int *a,int size) /堆排序 int i; BuildHeap(a,size); for(i=size;i=1;i-) /couta1=nint c = new intk + 1;for (int i = 0; i k; i+) ci = 0;for (int i = 0; i a.length; i+) cai+;System.out.println(n*);System.out.println(计数排序第2步后,临时数组C变为：);for (int m : c) System.out.print(m + );for (int i = 1; i = 0; i-) bcai - 1 = ai;/ CAi-1 就代表小于等于元素Ai的元素个数，就是Ai在B的位置cai-;System.out.println(n计数排序第4步后,临时数组C变为：);for (int n : c) System.out.print(n + );System.out.println(n计数排序第4步后,数组B变为：);for (int t : b) System.out.print(t + );System.out.println();System.out.println(*n);public static int getMaxNumber(int a) int max = 0;for (int i = 0; i a.length; i+) if (max ai) max = ai;return max;public static void main(String args) int a = new int 2, 5, 3, 0, 2, 3, 0, 3 ;int b = new inta.length;System.out.println(计数排序前为：);for (int i = 0; i a.length; i+) System.out.print(ai + );System.out.println();countSort(a, b, getMaxNumber(a);System.out.println(计数排序后为：);for (int i = 0; i a.length; i+) System.out.print(bi + );System.out.println();线性时间内对范围在0-n2内的数排序这是一个面试题。问题描述：给一个大小为n的数组arr，每个元素都是范围在 0 到 n2-1内的数字，如何在线性时间内对齐排序？例子:假设有5个元素,每个元素范围在 0 - 24.Input: arr = 0, 23, 14, 12, 9Output: arr = 0, 9, 12, 14, 23假设有3个元素,每个元素范围在 0 - 8.Input: arr = 7, 0, 2Output: arr = 0, 2, 7分析：基于比较的排序肯定是不能用了，最低复杂度为O(nlogn)，而题目要求为O(n)。复杂度为O(n) 的排序算法常见的有计数排序、基数排序和桶排序。如果数据的范围都在0-n ，就可以直接用计数排序了，空间复杂度为O(n)。在考虑下基数排序，一般来说复杂度为 O(nk)，其中n是排序元素个数，k是数字位数，k的大小是取决于我们选取的底(基数)，一般对十进制数的话就选取的10. 这里为了把k变为常数，就可以取n为底，k就为2. 这样复杂度就为 O(n)了。即把这些数都看成是n进制的，位数则不会超过2arr = 0, 10, 13, 12, 7假设以5为底(即5进制). 十进制的13 就为 23，十进制的 7为 12.arr = 00(0), 20(10), 23(13), 22(12), 12(7)第一边遍历后 (根据最低位排序）arr = 00(0), 20(10), 12(7), 22(12), 23(13)第二遍遍历后arr = 00(0), 12(7), 20(10), 22(12), 23(13)其中，基数排序的实现，又要依赖稳定的计数排序，所以需要O(n)的空间来计数。就是两次计数排序。代码实现如下：#includeusing namespace std;/对数组arr计数排序，根据 exp 指定的位int countSort(int arr, int n, int exp) int outputn; / 结果数组 int i, countn ; for (int i=0; i n; i+) counti = 0; / count记录出现的次数 for (i = 0; i n; i+) count (arri/exp)%n +; for (i = 1; i = 0; i-) outputcount (arri/exp)%n - 1 = arri; count(arri/exp)%n-; / 再将排序结果复杂到 arr for (i = 0; i n; i+) arri = outputi;/ 使用基数排序void sort(int arr, int n) / 按最后一位排序，即 exp (n0 = 1) countSort(arr, n, 1); /按高位排序，即exp (n1 = n ) countSort(arr, n, n);/打印数组void printArr(int arr, int n) for (int i = 0; i n; i+) cout arri ;/ 测试int main() / 元素个数7, 范围在 0 - 48 int arr = 40, 12, 45, 32, 33, 1, 22; int n = sizeof(arr)/sizeof(arr0); cout Given array is n; printArr(arr, n); sort(arr, n); cout nSorted array is n; printArr(arr, n); return 0;求第二小元素一、题目证明：在最坏情况下，利用n+ceil(lg n)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）。ceil表示向上取整二、思考step1：对所有元素，两个一组比较大小，小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。step2：沿着树从树根向下到叶子，找出第二小的元素，比较次数是ceillgn-1。令m2p表示以p为根的树中的第二小元素。对于当前处理结点为p，keyp = minkeyleftp, keyrightp。假设keyp = keyleftp，则m2p = minm2leftp, keyrightp可以这么理解：先找到最小的元素X，需要 n-1次比较。只有和X比较过的元素才有可能为 第二小，和X比较过的元素个数为ceil(lg n) 个，需要比较ceil(lg n)-1次，即上面蓝色圈中的数字。即总得比较次数为：n+ceil(lg n)-2三、代码#include using namespace std;/第一遍求最小值的结果用树表示struct nodeint key;node *next;/指向同一层中的下一个元素node *p;node *left;node *right;node(int k):key(k),next(NULL),p(NULL),left(NULL),right(NULL);/求第二小值int Find_S2(node *head)node *p, *q, *r, *t;/step1：求最小值/两两比较，较小的一个进入下一轮，这个循环当只剩下一个元素时结束while(head-next