2016.09.03 –09.07
[personal notes, there may be errors]

The notes about sorting or searching in the past [this time]:
[1] Re-collection of searching and sorting
[2] Implementation of internal sorting algorithm (C)
[3] Level improvement of quick sorting
[4] Heap (data structure) and heap sorting
[5] Bitmap mark binary search bit binary search
[6] File sorting

09.03

1 Internal sorting

Internal sorting means that the sorted records are stored in Computer random storage The sorting process in the storage.
If the internal sorting methods are classified according to different principles in the sorting process, they can be roughly divided into five categories: insertion sort, exchange sort, selective sort, merge sort and cardinal sort; if required in the internal sorting process Can be divided into three categories: [1] Simple sorting method, its time complexity is O(< span style="position: absolute; clip: rect(1.976em 1000em 2.723em -0.477em); top: -2.557em; left: 0.003em ;">n2 ) span> < /span>$O(n^2)$; [2] Advanced sorting method, its time complexity is $O(nlogn)$; [3] Cardinal sorting, its time complexity For $O(d ullet n)$.

Usually, sorting involves two basic operations: [1] compare the size of two keywords; [2] exchange keyword positions.

1.1 Insert Sort

(1) Direct Insert Sort

C code implementation.

/* direct_insert.c * Direct insertion sorting (plus loop test conditions)-Example of arrayed integer array elements (ascending order) * 2016.09< /span>.03 */#include void direct_insert(int *ar, unsigned len){ int v; unsigned i, k; if (!ar || 2> len) return; for (i = 1 ; i if (ar[i] 1 ]) {v = ar[i]; ar[i] = ar[i-1];  for (k = i-1; k> 0 && v 1]; ar[k] = v;} }}/* Simple test direct_insert function *//*int main(void){ int< /span> ar[] = {6, 5,  4, 3, 2, 1< /span>}; int ar_len; int i; ar_len = sizeof(ar) / sizeof(ar[ 0]); direct_insert(ar, ar_len); for (i = 0; i printf("%d ", ar[i]); printf("
" ); return 0;}*/

(2) Hill sort

09.04

/* shell_sort.c * Simple implementation of shell sorting-take integer array ascending order as an example * 2016.09.04 */#include /* one shell sort*/void  shell_sort_once(int *ar, unsigned ar_len, unsigned ic){ int i, j; int v; for (i = ic; i // Followed by ar[ic...len-1] One element is the base point if (ar[i] for (j = i-ic ; j >= 0 && v < ar[j]; j -= ic) // 以ar[i]为基点，每隔ic个元素的为一组序列                ar[j + ic] = ar[j];            ar[j + ic]  = v;        }    }} /* 整个shell排序, 排序间隔最终要为1 */void shell_sort_all(int *ar, unsigned ar_len, unsigned *ic, unsigned< /span> ic_len){    int k;    for (k = 0; k < ic_len; k++)        shell_sort_once(ar, ar_len, ic[k]);}/* 简单测试shell排序*/int main(void){    int i;    int ar_len, ic_len;    int ic[] = {5, 2, 1};    int ar[] = {6, 5, 4, 3, 2, 1};    ar_len  = sizeof(ar) / sizeof(ar[0]);    ic_len  = sizeof(ic) / sizeof(ic[0]);    shell_sort_all(ar, ar_len, ic, ic_len);    for (i = 0; i < ar_len; ++i)        printf("%d ", ar[i]) ;    printf("
");    return 0;}

1.2 快速排序

09.05
(1) 快速排序思想

/* general_quick_sort.c * 按照快速排序思想实现的常见的快速排序 - 以整型数组为例（升序） */#include /* 一趟快速排序 */int quick_sort_once(int *ar, int low, int high){    int v;    if (!ar) return;    v   = ar[low]; // 可随机选择序列中的某一个元素来和ar[0]交换    // 一次分割序列    while (low < high) {        // 将比v小的元素放置到v的前面        while (low < high && ar[high] >= v) high--;        ar[low]     = ar[high];        // 将比v大的元素放到v的后面        while (low < high && ar[low] <= v) low++;        ar[high]    = ar[low];    }    ar[low] = v;    return low;}/* 快速排序递归 */void quick_sort_all(int *ar, int low, int high){    int r_low;    if (low < high) { //返回条件        r_low   = quick_sort_once(ar, low, high);   / / 分割序列        quick_sort_all(ar, low, r_low - 1);         // 递归 - 优先小的序列        quick_sort_all(ar, r_low + 1, high);    }}/* 简单测试快速排序 */int main(void){    int i;    int ar_len;    int ar[] = {3, 4, 5, 6, 2, 1};    ar_len = sizeof(ar) / sizeof(ar[0]);    //quick_sort_once(ar, 0, ar_len - 1);    quick_sort_all(ar, 0, ar_len - 1);    for (i = 0; i < ar_len; i++)        printf("%d ", ar[i]);    printf("
");    return 0;}

(2) 快速排序优化 –> $O(nlog_2^n)$

1.3 选择排序

(1) 简单选择排序

(2) 堆排序

1.4 归并排序

2 查找

09.06
介绍在实际应用中大量使用的数据结构 —— 查找表。查找表示由同一类元素构成的集合。

关键字是数据元素中某个数据项的值，用它可以标识一个数据元素。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字。反之，称用以识别若干记录的关键字称为次关键字。

查找。根据给定的某个值，在查找表中确定一个其关键字等于给定值的元素。

静/动态查找表。若对查找表只进行查找或查询操作，则称此类表为静态查找表。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表。

平均查找长度。为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望称为查找算法在查找成功时的平均查找长度。

2.1 静态查找表

2.2 动态查找表

动态查找表的特点是，表结构本身是查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

09.07

2.3 哈希表

3 内存管理

[2016.10.01 – 01:06]