共计 2487 个字符，预计需要花费 7 分钟才能阅读完成。
《Programming Abstractions in C》学习第 76 天，p308-p311 总结，总计 4 页。
一、技术总结
1. 疾速排序伪代码
#include <stdbool.h>
static int Partition(int array[], int n);
/*
* Implementation notes: SortIntegerArray
* --------------------------------------
* This implementation of SortIntegerArray uses the Quicksort
* algorithm, which begins by "partitioning" the array so that
* all elements smaller than a designated pivot element appear
* to the left of a boundary and all equal or larger values
* appear to the right. Sorting the subarrays to the left and
* right of boundary ensures that the entire array is sorted.
*/
void SortIntegerArray(int array[], int n) {
int boundary;
if (n < 2) {return;}
boundary = Partition(array, n);
SortIntegerArray(array, boundary);
SortIntegerArray(array + boundary + 1, n - boundary - 1);
}
/*
* Function: Partition
* Usage: boundary = Partition(array, n);
* --------------------------------------
* This function rearranges the elements of array relative to
* a pivot value, which is taken from array[0]. The partition
* function returns a boundary index such that array[i] < pivot
* for all i < boundary, array[i] == pivot for i == boundary,
* and array[i] >= pivot for all i > boundary.
*/
static int Partition(int array[], int n) {
int lh, rh, pivot, temp;
pivot = array[0];
lh = 1;
rh = n - 1;
while (true) {while (lh < rh && array[rh] >= pivot) {rh--;}
while (lh < rh && array[lh] < pivot) {lh--;}
if (lh == rh) {break;}
temp = array[lh];
array[lh] = array[rh];
array[rh] = temp;
}
if (array[lh] >= pivot) {return 0;}
array[0] = array[lh];
array[lh] = pivot;
return lh;
}2. 疾速排序工夫复杂度
均匀工夫复杂度：O(NlogN)，最坏工夫复杂度：O(N^2)。
二、英语总结
1.fairly 是什么意思？
p308, Tony Hoare’s approach to partioning is fairly easy to explain in English。
答：
(1)fair: adj. fair 比拟罕用的意思是：treating someone in a way that is right or reasonable(公正的，偏心的)；但也有一个用得比拟少的意思: quite large。
(2)fairly: fair + ly。adv. more than average, but less than very(相当地)。
2.coincide 是什么意思？
p308, Move the rh index to the left until it either coincides with lh or points to an element containing a value that is small with respect to the pivot。
答：com-(together) + incidere(to fall upon)。vi. to come together in position / to happen at or near the same time。
3.roughly 是什么意思？
答：
(1)rough: adj. a. not even(平均) or smooth(润滑)，often because of being in bad condistion。b. not exact or detailed(大抵)。
p311, Moreover the running times for both algorithms appear to grow in roughly the same way。
4.appear to 是什么意思？
答：vi. to seem(看起来，仿佛)
三、其它
英语浏览要想疾速了解，就得尽可能把每个单词的所有意思都记录，如下面的：fairly——最罕用的意思就是“偏心地”，但书中显著不是这个意思，而是“quite large(相当地)”，平时用得少，没有在意，导致整个句子无奈了解。还有 rough 也是，罕用意思是 ”not smooth(毛糙的)”，但也有“not exact or detailed(大抵的)”之意。
四、参考资料
1. 编程
(1)Eric S.Roberts，《Programming Abstractions in C》：https://book.douban.com/subject/2003414
2. 英语
(1)Etymology Dictionary：https://www.etymonline.com
(2) Cambridage Dictionary：https://dictionary.cambridge.org
欢送搜寻及关注：编程人 (a_codists)