面试操作系统生疏点

这天面试被问到了一些操作系统，和算法题。有些感觉有点陌生了，来回顾一下。

1. 过程之间的通信形式？
2. 排序数组二维数组查找？
3. 快排工夫复杂度及过程？

过程之间通信形式？

 相干好文：[过程间的通信形式](https://www.cnblogs.com/LUO77/p/5816326.html)

过程复制:fork() 复制一个截然不同的子过程，胜利返回 0。
通信形式有：管道、有名管道、音讯队列、共享内存、信号量、套接字、信号。
信号：半双工，只限于父子过程间应用。在 <signal.h> 头文件中，软件层面对中断的模仿。
管道：半双工，FIFO。匿名管道只能用于父子过程通信。
音讯队列：可按音讯类型分类读取的队列。
共享内存：间接进行共享内存数据交换。无需用户态和外围态的切换。效率最高。

排序二维数组查找值

剑指 offer 的题。leetcode 地址：剑指 Offer 04. 二维数组中的查找

法一 暴力:

• 思路：间接二重循环遍历。工夫复杂度 O（n*m）。
• 毛病：没有利用到已排序个性。

public boolean findNumberIn2DArray(int[][] matrix, int target) {for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[i].length;j++){if(target==matrix[i][j])return true;
            }
        }
        return false;
    }

法二：

• 思路：穿插极值点（左下或右上，既是极小值也是极大值）。每次没找到就剔除一行 / 一列。工夫复杂度 O(m+n), 最极其状况：在最初一行最右边匹配。
• 剖析：每行的最初边必然大于右边的数。所以先判断每行最大值。
• 代码:

// 每一行的最初边是值最大的
    public boolean findNumberIn2DArray(int[][] matrix, int target) {if(matrix.length==0) return false;
        int col_len = matrix[0].length;
        for(int i=0;i<matrix.length;i++){   // 行下移
            for(int j=col_len-1;j>=0;j--){     // 列左移
                if(matrix[i][j]==target)return true; 
                if(matrix[i][j]<target){    // 这行都不够大
                    j=matrix[0].length-1;   // 重置列
                    break;                  // 下移一行
                }
            }
        }
        return false;
    }

法三：行列同时二分查找。
思路：充分利用二分查找思维。
代码：略

快排 工夫复杂度 O（nlgn）

void quicksort(int data[],int low,int high){
        int i,j,temp,basis;
        if(low>high)return;     // 弹出条件
        i = low;
        j = high;
        basis = data[low];    // 第一位为基准值
        while(i!=j){          // 先左边左移
            while(data[j]<=basis&&i<j)j--;        // i<j 必须要有 , 直到 data[j]>=basis
            while(data[i]>=basis&&i<j)i++;        // = 号必须要有
            if(i<j){// swap(data[i],data[j])
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        //i j 相遇，基值归位 swap(data[low],data[i])
        temp = data[low];
        data[low] = data [i];
        data[i] = temp;
        quicksort(data,low,i-1);    // 右边排序
        quicksort(data,i+1,high);    // 左边排序
    }