Browsed by
Tag: 排序

判断数组中是否存在两个数之和为指定值

判断数组中是否存在两个数之和为指定值

题目是CLRS 2.3-7。原题如下: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,determines whether or not there exist two elements in S whose sum is exactly x. 初看这个题目,就大约想到用排序来解决。我大概的思路是先排序,然后再用二分查找法去寻找。 看了看CLRS的答案,给出的方法跟我思路不同,他的想法是,添加一个数组,其值为原输入数组中值与x的差,删除掉两个数组中相同的数,然后合并排序那两个数组,如果合并排序后数组中相邻的两个数相同,则说明原数组中有sum为x的元素。 觉得答案给出的方法也比较有意思,于是试着实现了一下。过程中还真遇到了点问题,下次要吸取教训。 问题是这样的,要删除原数组中相同的元素,我用的如下的方法: // assume array, length is defined. int i = 0; for(; i < length – 1; i++){ if(array[i] == array[i+1]){ int tmp = i; while(tmp < length – 1){ array[tmp] = array[tmp + 1]; tmp++; } } } 看出问题在哪儿了吗?在遇到这样{-26 -23 -22 -19…

Read More Read More

插入排序

插入排序

按照计划,接下来开始实现书中的一些算法。今天是比较简单的插入排序法,但是也不是一次就成功,可见再简单的算法,也需要真正实践才能确保没有问题。 主要问题是处在插入排序需要找到一个key,用于标记当前需要插入的值。其原理想象起来也简单,就是想插入扑克牌一样,把目标扑克牌插入一个已经排序好的牌中,所以需要一个key来标记当前要插入的牌。而平时写冒泡比较多,所以很习惯的就写了两个for循环,然后才发现不太好往下面写了,其实第二循环换成while更加顺畅。 #include void InsertionSort(int array[], int length){ int i = 1; int j = 0; for(; i < length; i++){ int key = array[i]; j = i - 1; while(j >= 0 && array[j] > key){ array[j+1] = array[j]; j–; } array[j+1] = key; } } int main(int argc, char** argv){ int array[] = {8, 7, 6, 5, 4, 3, 2, 1}; int length = 8; int i = 0; printf(“before sort\n”); for(; i < length; i++){ printf("%d ",...

Read More Read More