十二的编程笔记

# 6. 分配类排序 1. 多关键字排序 两个关键字的优先级，先分高级的叫 “高位优先” 排序法，先分低级的叫 “低位优先” 排序法 2. 链式基数排序 排序时先按最低位的值对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。依此类推，由低位到高位，每一趟都是在前一趟的基础上，根据关键字的某一位对所有记录进行排序，直至最高位，这样就完成了基数排序的全过程。 // 理解就好不用硬看#define RADIX 10#define KEY_SIZE 6#define LIST_SIZE 20typedef int KeyType;typedef struct {...

# 7. 排序方法的综合比较 1. 各种排序方法的性能比较 排序方法 平均时间复杂度 最坏时间复杂度 辅助存储空间 简单排序法 O(n2) O(n2) O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 堆排序 O(nlog2n) O(nlog2n) O(1) 归并排序 O(nlog2n) O(nlog2n) O(n) 基数排序 O(d(n+rd)) O(d(n+rd)) O(rd) 2. 各种排序方法的稳定性比较 排序方法 稳定性 反例 直接插入排序 是 冒泡排序 是 简单选择排序 否 （3，3*，2） 希尔排序 否 （2，4，1，2*）...

# 2. 插入排序 基本思想：将一个元素记录按其应用的位置插入 到已排好序的序列中。依据寻找插入位置的方法不同，插入排序分为： 直接插入排序；折半插入排序；希尔插入排序；表插入排序。 # 1. 直接插入排序 基本思想： 插入 Ri 时，R1，R2，…，Ri-1 已排好，用 Ri 的关键字与 Ri-1,Ri-2,…，R1 比较，找到插入位置。即把一个记录插入到已排好序的有序表中。 /* 对记录数组 r 做直接插入排序，length 为数组中待排序记录的数目 */void InsSort(RecordType r[], int length){ for ( i=2 ;...

# 内部排序 # 1. 概念 内部排序：是指待排序记录存放在计算机随机存储器中进行的排序过程。 ** 外部排序:** 是指待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程. 排序的稳定性 假设 ki=kj, 且排序前序列中 Ri 领先于 Rj, 若在排序后的序列中 Ri 仍领先于 Rj, 则称排序方法是稳定，否则称为不稳定的。 排序时间复杂性 排序过程主要是对记录的关键码进行比较和记录的移动，所以排序的时间复杂性以算法的执行中数据比较次数和数据移动的次数来衡量。

# 5. 归并排序 基本思想 1）把 n 个记录看成 n 个长度为 l 的有序子表； 2）进行两两归并使记录关键字有序，得到［n/2］个长度为 2 的有序子表； 3）重复第（2）步，直到所有记录归并成一个长度为 n 的有序表为止。 // 相邻两个有序子序列的合并成算法/* 已知 r1 [low..mid] 和 r1 [mid+1..high] 分别按关键字有序排列，将它们合并成一个有序序列，存放在 r2 [low..high] */void Merge ( RecordType r1[], int low, int mid, int high, RecordType...

# 4. 选择类排序 选择排序 (Selection Sort) 的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。 # 1. 简单选择排序 基本思想 第一趟，从 n 个记录中找出关键字最小的记录与第一个记录交换； 第二趟，从第二个记录开始的 n-1 个记录中再选出关键码最小的记录与第二个记录交换； 第 i 趟，则从第 i 个记录开始的 n-i+1 个记录中选出关键字最小的记录与第 i 个记录交换，直到整个序列按关键字有序。 这种操作进行 n-1 次，但每一次的待排元素个数比上一次少一个。 void...

# 3. 交换类排序 # 1. 冒泡排序 （相邻比序法） 基本思想： 通过不断比较相邻元素大小，进行交换实现排序。 第一趟排序： 首先将第一个元素和第二个元素比较大小，若为逆序，则交换；然后比较第二个与第三个，一直到第 n-1 和第 n 个，这样就使最大的元素放到了最后一个位置。 void BubbleSort(SqList *L){ for(int i=1; i<L->length; i++){ flag=1; for(j=1;j<L->length-i;j++){...

# 7.Linux 磁盘管理 # 1.Linux 物理设备介绍 1.1 一切从 “/” 开始 在 Linux 系统中，目录、字符设备、块设备、套接字、打印机等都被抽象成了文件，既然平时我们打交道的都是文件，那么又应该如何找到它们呢？ 在 Linux 系统中并不存在 C/D/E/F 等盘符，Linux 系统中的一切文件都是从 “根（ / ）” 目录开始的，并按照文件系统层次化标准（FHS）采用树形结构来存放文件，以及定义了常见目录的用途。 另外，Linux 系统中的文件和目录名称是严格区分大小写的。例如，root、rOOt、Root、rooT 均代表不同的目录，并且文件名称中不得包含斜杠（ /...

# 2. 物理层 物理层的四个基本特性 物理层下面的传输媒体：双绞线和光纤 常见的几种信道复用技术 宽带接入技术：ADSL 和 FTTx # 2.1 物理层的基本概念 物理层考虑的是怎样才能在连接各种计算机的传输媒体上传输数据比特流，而不是指具体的传输媒体。 物理层的作用是要尽可能地屏蔽掉不同传输媒体和通信手段的差异。 用于物理层的协议也常称为物理层规程...

# 1. 概述 21 世纪是知识经济的时代，但几乎所有的经济活动都依赖于信息的交流。目前信息的主要载体是计算机，而传播信息靠的就是计算机网络。计算机网络是现代通信技术与计算机技术紧密相结合的产物。 计算机网络的发展使计算机应用发生了巨大的变化，已经遍布经济、文化、科研、军事、政治、教育和社会生活等各个领域，引起了世界范围内信息产业的发展。 计算机网络的发展史： 根据计算机发展的特点，将计算机网络的发展过程大致分为以下 4 个阶段： 1. 面向终端的计算机网络（20 世纪 50 年代末 - 60 年代初） 1951 年，美国麻省理工学院为美国空军设计 SAGE...