3.数组向左移若干位的算法##

3.1杂技算法

最重要的是如何使用左移位数和数组长度的最大公约数

void func(int *arr, int rotdist, int length)
{
    int max=gcd(rotdist, length);//!!!!!!!!!!!!!
    for(int i=0; i<max; i++)//!!!!!!!!!!!!!!!!!!
    {
        int temp=arr[i];
        int to=i;
        int from=(to+rotdist)%length;
        while(from != i)
        {
            arr[to]=arr[from];
            to= from;
            from =(to+rotdist)%length;
        }
        arr[to]=temp;
    }
    return;
}

3.2reverse###

reverse(0, n1-1);
reverse(n1, n2-1);
reverse(0, n2-1);

7.如何快速来转置一个矩阵？##

作者给出的解答是：为每条记录插入列号和行号，然后调用系统的磁带排序程序先按列排序再按行排序，最后使用另一个程序删除列号和行号。

8.求n个数字中最小的k个元素？##

8.1排序###

先排序，O(nlogn),然后取前k个O(k), 所以为O(nlogn＋k)

8.2建立一个大小为k的堆###

先拿前k个数建立一个堆，O(k)，再循环拿剩下的n-k个数与堆顶比较，每次维护为O(logk), 所以为O((n－k)logk＋k)

8.3建立一个大小为n的堆###

建立大小为n的堆，O(n)，然后循环k次，每次取堆顶元素，O(klogn), 所以为O(n ＋ klogn)

8.4直接维护一个大小为k的数组###

选择或交换排序，即遍历n个数，先把最先遍历到的K个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最大数Kmax(Kmax为这K个元素的数组中最大的元素)，用时间为O(k)（你应该知道，插入或选择排序查找操作需要O(k)的时间），后再继续遍历后n-k个数，x与Kmax比较：如果x< Kmax，则x代替Kmax，并再次重新找出K个元素的数组中的最大元素Kmax'；如果x>Kmax，则不更新数组。这样每次更新和不更新数组所用的时间为O(k)或O(0)，整趟下来，总的时间复杂度平均下来为：O(n*k)