有个需求需要在内核态下修改本机的IP地址，经过分析后我个人觉得不可行（不修改内核的情况下）

分析思路：

1、用户态下修改IP可以通过shell命令：
   ifconfig eth0 192.168.1.xxx

2、通过kgdb跟踪上述命令后，发现走的是ioctl，即代码走到
   int devinet_ioctl(unsigned int cmd, void __user *arg)
   {

    /* 验证参数，禁止了直接从内核态下调用该ioctl */
    if (copy_from_user(&ifr, arg, sizeof(struct ifreq)))
    ...

    case SIOCSIFADDR:    /* Set interface address (and family) */
        修改ip地址
    ...
    }

 3、研究了修改ip地址的相关函数后，发现ioctl是唯一修改IP的途径。在
    内核下直接调用该ioctl，函数copy_from_user无法通过

 4、把copy_from_user改为memcpy后在内核下便可以直接调用ioctl修改IP了，
    但是老大不让..(需要重编内核，已验证过)

在前2个Posts中，使用了递归的方式实现快速排序算法，如果想
去掉递归，则我们需要使用栈数据结构，

//为数组分区，返回新的支点位置(前2个Posts中已经实现)
int partition(int array[], int left, int right);

//记录数组信息的结构
typedef struct _qsort_range {
        int left, right;
}qsort_range;

//记录数组信息的栈
typedef stack<qsort_range, list<qsort_range> > range_stack;

//用非递归方法实现快速排序
void qsort2(int array[], int left, int right)
{
        /*数组分区*/
        int pos = partition(array, left, right);
        if (pos == -1) return;

        range_stack s;
        if (pos >= left) {
                /*左子数组left、right信息保存，注意：先左再右*/
                if (pos + 1 < right) {
                        qsort_range r2;
                        r2.left = pos+1; r2.right = right;
                        s.push(r2);
                }
                /*右子数组left、right信息保存*/
                if (pos - 1 > left) {
                        qsort_range r1;
                        r1.left = left; r1.right=pos-1;
                        s.push(r1);
                }
        }

        /*模拟递归调用*/
        while (s.size() > 0) {
                /*出栈*/
                qsort_range r3 = s.top();
                s.pop();

                /*数组分区*/
                int pos3 = partition(array, r3.left, r3.right);
                if (pos3 != -1) {
                        /*子数组的left、right信息保存*/
                        if (pos3 >= r3.left) {
                                if (pos3 + 1 < r3.right) {
                                        qsort_range r31;
                                        r31.left = pos3+1; r31.right = r3.right;
                                        s.push(r31);
                                }
                                if (pos3 - 1 > r3.left) {
                                        qsort_range r32;
                                        r32.left = r3.left; r32.right=pos3-1;
                                        s.push(r32);
                                }
                        }
                }
        }
}   上个Post以数组最右边的那个元素作为支点，这里将
重写partition函数，以数组中间位置作为支点。
实现如下，

int partition(int array[], int left, int right)
{
        /*以中间元素作为支点*/
        int l=left, r=right, pivot=(left+right)/2;

        while (l < r) {
                if (array[l] < array[pivot]) {
                        l++;
                        continue;
                }
                if (array[r] > array[pivot]) {
                        r--;
                        continue;
                }

                SWAP(array+l, array+r);

                /*更新pivot位置*/
                if (pivot==l) pivot=r;
                else if(pivot==r) pivot=l;

                l++; r--;
        }

        /*注意：此时l==r*/
        if (l < pivot) { /*支点在右边*/
                if (array[l] < array[pivot]) l++;
        }
        else if (l > pivot) { /*支点在左边*/
                if (array[l] > array[pivot]) l--;
        }
        SWAP(array+l, array+right);

        /*返回新的支点位置*/
        return l;
}

下一个Post将考虑给出qsort的非递归实现 。。。
快速排序的实现思想其实很简单，可以简单的描述成下面的递归形式，

qsort(array)
        设置分界点;
        把所有小于分界点的值作为左子列;
        把所有大于分界点的值作为右子列;
        qsort(左子列);
        qsort(有子列);
}


但是，实际用c/c++实现起来，就不见得一下可以写出来了，

以下是我的实现

#define SWAP(p1, p2) do { \
        int tmp = *(p1); \
        *(p1) = *(p2); \
        *(p2) = tmp; \
} while (0)


//====================================================
// 划分数组，并返回分界点
//====================================================
int partition(int array[], int left, int right)
{
        int l=left, r=right-1; /*用数组的最后1个元素分区*/

        while (l < r) {
                /*查找交换元素*/
                if (array[l] < array[right]) {
                        l++;
                        continue;
                }

                if (array[r] > array[right]) {
                        r--;
                        continue;
                }

                /*交换元素，调整索引*/
                SWAP(array+l, array+r);
                l++;
                r--;
        }

        /*此时数组l,r索引已经相遇，即l==r*/
        if (array[l] < array[right]) l++;
        SWAP(array+l, array+right);

        return l;
}


//快速排序
void qsort(int array[], int left, int right)
{
        if (left >= right) return;

        int pos = partition(array, left, right);
        if (pos == -1) return;

        qsort(array, left, pos-1);
        qsort(array, pos+1, right);
}


我认为快速排序中主要的东西就是partition方法，如果把partition
提取出来实现，则快速排序算法也就比较简单了。网上有qsort比较简
洁的c++实现，即没有把partition方法分离出来，但是一步到位的做法
比较难，我还是更喜欢先实现，再优化的方式。。。


//有序数组二分查找
int bsearch(int array[], int left, int right, int target)
{
    while (left <= right)
    {
        int mid = (left+right)/2;
        if (array[mid] == target) return mid;
        else if (array[mid] > target) right=mid-1;
        else left=mid +1;
    }
    return -1;
}