文章目录
前言
考完试又到了新的学期，这学期的计算机专业课从C程序设计变成了面向对象的程序设计（C++），接下来的学习笔记会更新C++的上课内容。C++学习笔记合集：
这一期是C向C++过渡的课程，所以这些内容都还是用C来写的。这一期的引用（Reference）：
- 《C Primer Plus 6th Edition》
- 《编程珠玑》第二版修订版
- 《算法导论》第三版
- https://www.jb51.net/article/232301.htm
Qsort
qsort()函数是在include<stdlib.h>库中的一个快速排序函数。下面是 qsort() 函数的声明。
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));- base -- 指向要排序的数组的第一个元素的指针。一般为数组名。
- num -- 由 base 指向的数组中元素的个数。
- size -- 数组中每个元素的大小，以字节为单位。一般可用sizeof运算。
- compar -- 指向比较两个元素的函数的指针。它是函数的指针。
其中，compar指针所对应的函数应符合下面的格式：
int compar (const void* p1, const void* p2);
该函数通过返回（以稳定和传递的方式）定义元素的顺序：
| 返回值 | 意义 |
|---|---|
<0 |
p1指向的元素在p2指向的元素之前 |
0 |
p1指向的元素等价于p2指向的元素 |
>0 |
p1指向的元素在p2指向的元素之后 |
这个函数的写法等会会有说明。
快速排序
我们知道了qsort()函数的组成，但可能还不知道快速排序和其他排序的区别，接下来我们就来讲快速排序的过程。
快速排序是由C. A. R. Hoare提出的一种排序算法。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的最快情况 Ο(nlogn) ，最坏运行情况是 O(n²)。
它的基本思想是：
- 选择一个基准数（pivot），通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。
- 然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
我们在经典算法书《编程珠玑》中可以看到它的基本实现方法，例如，为了对如下的八元数组排序：
我们把第一个元素55当成pivot：所有小于 55 的元素都移到其左边，所有大于55的元素都移到其右边。
接着对下标为0～2的子数组和下标为4～7的子数组分别进行递归排序，那么整个数组就排好序了。
这个基本过程我们可以简单的用一个递归来解决，可以分别用下标l和u表示数组待排序部分的下界和上界，递归结束的条件是待排序部分的元素个数小于2。
实现这个过程我们一般有两种方法，第一种是递归Hoare版（双指针法），第二种是划分算法。说法仅供参考而已，名字可能不同。
递归Hoare版（双指针法）
首先是这个版本的，采用了循环递归的方法，我们先从这个GIF来看整个排序的过程。
我们一步步看这个函数，为保证数组第一个元素和最后一个元素下标不变，创建first和last两个局部变量记录数组第一个元素和最后一个元素的下标，然后设置一个pivot为基准值。
void Quicksort(int *arr, int l, int r)
{
int first = l;//最左边数组下标
int last = r;//最右边数组下标
int pivot = first;//用于比较的标量（选取最左边第一个元素）
}既然是写递归，那我们应该先考虑返回条件。有可能有这些返回条件：
- 判断数列是否只有一个元素，如果只有一个元素，则函数结束。
- first>=last时，说明重合了或者已经排列完了，则结束子函数。
void Quicksort(int *arr, int l, int r)
{
int first = l;//最左边数组下标
int last = r;//最右边数组下标
int pivot = first;//用于比较的标量（选取最左边第一个元素）
if (first >= last)//如果只有一个元素，first==last；以及first>last的情况
{
return;
}
}我们选取了左边第一个数据为pivot，那么应该先从右边开始比较，从右边第一个数据开始与pivot进行比较，如果比它大则继续向左比较(last--)，直到找到比pivot小的数据，便停下来。
右边的比较暂时结束了，此刻开始从左边开始与pivot比较，如果比pivot小则继续向右比较(first++)，如果比pivot大则也停下来。
我们比较first对应的元素与last此时对应的元素，如果first < last，左边找到的比pivot大的数与右边找到的比pivot小的数进行交换。
至此，第一次查找结束了，根据循环，如果此时first < last还成立，我们继续按照上面的方法移动，直到不成立这次循环就结束了。
void Quicksort(int *arr, int l, int r)
{
int first = l;//最左边数组下标
int last = r;//最右边数组下标
int pivot = first;//用于比较的标量（选取最左边第一个元素）
if (first >= last)//如果只有一个元素，first==last；以及first>last的情况
{
return;
}
while (first < last)
{
while (first < last && arr[last] >= arr[pivot])//右边找比标量小的数
{
last--;
}
while (first < last && arr[first] <= arr[pivot])//左边找比标量大的数
{
first++;
}
if(first < last)//分析交换找出来的值
swap(&arr[first], &arr[last]);
}
}我们把pivot放到中间位置，至此就分成了左右两个数组。接下来就是我们的递归了，递归左边的部分数组，递归右边的部分数组。
void Quicksort(int *arr, int l, int r)
{
int first = l;//最左边数组下标
int last = r;//最右边数组下标
int pivot = first;//用于比较的标量（选取最左边第一个元素）
if (first >= last)//如果只有一个元素，first==last；以及first>last的情况
{
return;
}
while (first < last)
{
while (first < last && arr[last] >= arr[pivot])//右边找比标量小的数
{
last--;
}
while (first < last && arr[first] <= arr[pivot])//左边找比标量大的数
{
first++;
}
if(first < last)//分析交换找出来的值
swap(&arr[first], &arr[last]);
}
if (first == last)
{
swap(&arr[pivot], &arr[last]);//交换pivot到它应该到的位置上，重新选取标量
}
Quicksort(arr,l,first-1);//左边递归排序
Quicksort(arr,first+1,r);//右边递归排序
}当然，这还没有结束，swap函数还没有写，不过这一部分就很简单了。因为arr是局部的，需要影响到交换函数外的值，使用指针形参。
void swap(int* a, int* b)
{
int t = 0;
t = *a;
*a = *b;
*b = t;
}划分算法
根据《算法导论》里对快速排序算法的说明，我们还可以使用拆分算法来实现：
数组A[p.. r] 被划分为两个（可能为空）子数组A1[p.. q-1] 和A2[q+ 1.. r], 使得A1[p .. q-1] 中的每一个元素都小于等于A[q], 而A[q] 也小于等于A2[q+l..r] 中的每个元素。其中，计算下标q 也是划分过程的一部分。
首先是主要递归函数部分：
void quickSort(int a[], int p, int r) {
int position = 0;
if (p<r)
{
position = partition(a,p,r);//返回划分元素的最终位置
quickSort(a,p,position-1);//划分左边递归
quickSort(a, position + 1,r);//划分右边递归
}
}算法的关键部分是PARTITION 过程，它实现了对子数组A[p.. r] 的原址重排。
int partition(int a[], int p, int r) {
int pivot = a[r];//取最后一个
int i = p - 1;
for (int j = p; j < r; j++)
{
if (a[j] <= pivot)
{
i++;
//i一直代表小于pivot元素的最后一个索引，当发现有比pivot小的a[j]时候，i+1 后交换
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[r]);//将pivot切换到中间来，左边是小于pivot的，右边是大于pivot的值。
return i + 1;
}这个相当于就是挖坑法的单向形式，固定右侧位置，只移动左侧位置，当出现比pivot大的时候就停止，然后继续循环。与挖坑法如出一辙。
优化算法
我们看，快速排序这个算法虽然快速，但当数据比较阴间的时候会退化为O（n^2），说明这个算法是不稳定的。我们一般有两种优化方式：
- pivot取随机数，有时我们可以通过在算法中引入随机性，从而使得算法对于所有的输入都能获得较好的期望性能。
- 我们知道插入排序在数组少的时候速度更快，所以大小为11或更小的数组在划分过程中被忽略，使用插入排序来完成排序。
- 三平均划分法，或划分成三段等。
对于第一种，我们只需要把pivot改为用rand()取出的一个随机值的随机位置就行了；第二种优化多一段在数组小的时候的判断，和插入排序；第三段就比较复杂了，这里就先不写了。
Compar函数写法
回到qsort()函数，它帮我们一键进行快速排序。但是因为它开的接口比较多，所以效率上不如自己写的快速排序。
我们知道参数(*compar)(const void *, const void *) - 此为指向比较函数的函数指针，决定了排序的顺序。
我们知道数组的名字可以作为数组第一个位置的地址，但是很少见函数名作为函数指针的情况，在此处compar函数名就作为指向比较函数的指针使用。
两个形参必须是const void *型，同时在调用compar 函数（compar实质为函数指针，这里称它所指向的函数也为compar）时，传入的实参也必须转换成const void *型。在compar函数内部需要把const void *型转换成实际类型。
所以，compar函数可以这样写：
int compareMyType (const void * a, const void * b)
{
if ( *(MyType*)a < *(MyType*)b ) return -1;
if ( *(MyType*)a == *(MyType*)b ) return 0;
if ( *(MyType*)a > *(MyType*)b ) return 1;
}你要将MyType换成实际数组元素的类型。例如我们转换成double型的升序排序，根据书上的写法，应该写成：
int mycomp(const void * p1, const void * p2)
{
/* need to use pointers to double to access values. 格式转换 */
const double * a1 = (const double *) p1;
const double * a2 = (const double *) p2;
if (*a1 < *a2)
return -1;
else if (*a1 == *a2)
return 0;
else
return 1;
}但是我们平常一般不会写成这样，为了追求简单，我们一般这样写：
int compar_lowtoup (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}如果a小于b，则返回值为负数（< 0），也即a会排在b的前面。同理，若a大于b，则a会排在b的后面。所以，这里的qsort()为从小到大即升序排序。
如果要是从大到小即降序排序，我们也只需要更改a,b的位置即可，即：
int compar_uptolow (const void * a, const void * b)
{
return ( *(int*)b - *(int*)a );
}如果我们要比较不是数字，是字符之类的，例如定义一个结构体：
struct stu{
int age;
float height;
const char * name;
}student[100];我们比较他们名字，我们的compar函数可以这么写：
int nameComp(const void * x, const void * y){
const Student * xp = (const Student *) x;
const Student * yp = (const Student *) y;
return strcmp(xp->name, yp->name); // in string.h
}这时，qsort函数中size也要做出一点更改：qsort(arr, 100, sizeof(student), nameComp);
队列ADT
首先这个标题队列ADT中由两个词组成，一个是队列，一个是ADT。
队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊链表。队列具有先进先出FIFO（First in First Out）的原则。
ADT是抽象数据类型，是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。
那么我们就可以把它看成是一个链表来处理，还要注意它的特殊性质。
这一篇属于高级数据表示了，之后也会专门写一篇专题来写队列的使用。
位操作
二进制数、位和字节
我们日常中通常都是基于十进制书写数字。例如1234=1*1000+2*100+3*10+4*1.计算机中一般采用二进制数（Binary number）表示数字。
我们还一般用字节(byte)表示储存系统字符集所需的大小，用位（bit）或字长来表示位的长度。
除了二进制外，我们一般还常用八进制（Octal）（形如：0377）、十六进制（Hexadecimal）（形如：0XC2），接下来就是位运算了。
按位取反：~
按位取反（Bitwise Negation），一元运算符～把二进制中1 变为0 ， 把0 变为1 。例如：
val=(10001011)2 --> ~val==(1001011)2 == (01110100)2
就像3 * val不会改变val的值一样，~运算符不会改变val的值，所以只能当做右值使用。
按位与：＆
二元运算符＆通过逐位比较两个运算对象， 生成一个新值。对于每个位， 只有两个运算对象中相应的位都为1时， 结果才为1。所以只有1 & 1时结果为1，其他如0&1、1&0、0&0情况均为0。即全真则真。
例如：val=(10010011)2 & (00111101)2 //2在此表示二进制，实际写时不需要写出
则val==(00010001)2
按位或：|
二元运算符I, 通过逐位比较两个运算对象， 生成一个新值。对于每个位， 如果两个运算对象中相应的位为1, 结果就为1。即有真则真。即1 & 1、0&1、1&0的结果均为1，0&0为0.
例如：val=(10010011)2 | (00111101)2
则val==(10111111)2
按位异或：^
按位异或（Bitwise EXCLUSIVE OR），二元运算符＾ 逐位比较两个运算对象。对千每个位， 如果两个运算对象中相应的位中有且仅有一个1 ， 结果为1.即0&1、1&0的结果均为1，1 & 1、0&0为0.
注意：这个符号在C/C++中不代表乘方符号，乘方需要使用函数pow()。
例如：val=(10010011)2 ^ (00111101)2
则val==(10101110)2
掩码（Mask）
所谓掩码指的是一些设置为开(1)或关(0) 的位组合。掩码是一串二进制代码对目标字段进行位与运算，屏蔽当前的输入位。这个在计算机网络中使用比较多，这么就不多说了。
移位运算符（Bitwise Left Shift Operator）
左移：<<
左移运算符（＜＜）将其左侧运算对象每一位的值向左移动其右侧运算对象指定的位数。左侧运算对象移出左末端位的值丢失， 用0填充空出的位置。
例如：(10001010) << 2 //运算
(00101000) ／／结果值
右移：>>
右移运算符（＞＞）将其左侧运算对象每一位的值向右移动其右侧运算对象指定的位数。左侧运算对象移出右末端位的值丢失， 用0填充空出的位置。
就不举例了，是上面的反过来。
位字段
操控位的第2 种方法是位宇段(bitfield) 。位字段是一个signed int 或unsigned int 类型变量中的一组相邻的位(C99和C11新增了＿Bool 类型的位字段）。位字段通过一个结构声明来建立， 该结构声明为每个字段提供标签， 并确定该字段的宽度。
例如：
struct {
unsigned int field1 : 1;
unsigned int : 2;// pad with a 2-bit hole
unsigned int field2 : 2;
unsigned int : 0; //alignment to next byte
unsigned int field3 : 3; // field 3 start at next integer
} stuff;
stuff.field1 = 1;
stuff. field2 = 5; // error, 5 needs 3 bits
stuff.field3 = 7; // ok后记
这一篇主要讲了C语言的qsort函数、快速排序算法和位运算，队列的内容将在专题中发布，这同时也是C/C++的过渡，在C++中大部分还是适用的。
Comments NOTHING