2016.09.03 –09.07
[个人笔记，可能有错误]

以前胡乱折腾的关于排序或查找的笔记[这次也是]：
[1] 再集查找与排序
[2] 内部排序算法实现(C)
[3] 快速排序的层次改进
[4] 堆（数据结构）及堆排序
[5] 位图标记 二分查找 位二分
[6] 文件排序

09.03

1 内部排序

内部排序指的是带排序记录存放在计算机随机存储器中进行的排序过程。
如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可以分为插入排序、交换排序、选择排序、归并排序和基数排序等五类；如果按照内部排序过程中所需的工作量来区分，则可分为3类：[1] 简单的排序方法，其时间复杂度为$O(n^2)$；[2] 先进的排序方法，其时间复杂度为$O(nlogn)$；[3] 基数排序，其时间复杂度为$O(d \bullet n)$。

通常，排序会涉及两种基本的操作：[1] 比较两个关键字大小；[2] 交换关键字位置。

1.1 插入排序

(1) 直接插入排序

C代码实现。

/* direct_insert.c
 * 直接插入排序（加循环测试条件） - 排整型数组元素示例（升序）
 * 2016.09.03
 */
#include <stdio.h>

void direct_insert(int *ar,unsigned len)
{
    int         v;
    unsigned    i,k;

    if (!ar || 2 > len) return;
    for (i = 1; i < len; ++i) {
        if (ar[i] < ar[i - 1]) {
            v       = ar[i];
            ar[i]   = ar[i - 1];
            for (k = i - 1; k > 0 && v < ar[k]; k--)
                ar[k]   = ar[k - 1];
            ar[k]   = v;
        }
    }
}

/* 简单测试direct_insert函数 */
/*
int main(void)
{
    int ar[] = {6,5,4,3,2,1};
    int ar_len;
    int i;

    ar_len = sizeof(ar) / sizeof(ar[0]);
    direct_insert(ar,ar_len);

    for (i = 0; i < ar_len; i++)
        printf("%d ",ar[i]);
    printf("\n");
    return 0;
}
*/

(2) 希尔排序

09.04

/* shell_sort.c * shell排序简单实现 - 以整型数组升序为例 * 2016.09.04 */

#include <stdio.h>

/* 一次shell排序 */
void shell_sort_once(int *ar,unsigned ar_len,unsigned ic)
{
    int i,j;
    int v;

    for (i = ic; i < ar_len; ++i) { // 依次以ar[ic...len-1]中的一个元素为基点
        if (ar[i] < ar[i - ic]) {
            v   = 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 *ic,unsigned 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,1};
    int ar[] = {6,1};

    ar_len  = sizeof(ar) / sizeof(ar[0]);
    ic_len  = sizeof(ic) / sizeof(ic[0]);
    shell_sort_all(ar,ic,ic_len);

    for (i = 0; i < ar_len; ++i)
        printf("%d ",ar[i]);
    printf("\n");

    return 0;
}

1.2 快速排序

09.05
(1) 快速排序思想

/* general_quick_sort.c * 按照快速排序思想实现的常见的快速排序 - 以整型数组为例（升序） */

#include <stdio.h>

/* 一趟快速排序 */
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 high)
{
    int r_low;

    if (low < high) { //返回条件
        r_low   = quick_sort_once(ar,low,high);   // 分割序列
        quick_sort_all(ar,r_low - 1);         // 递归 - 优先小的序列
        quick_sort_all(ar,r_low + 1,high);
    }
}

/* 简单测试快速排序 */
int main(void)
{
    int i;
    int ar_len;
    int ar[] = {3,6,1};

    ar_len = sizeof(ar) / sizeof(ar[0]);
    //quick_sort_once(ar,ar_len - 1);
    quick_sort_all(ar,0,ar_len - 1);

    for (i = 0; i < ar_len; i++)
        printf("%d ",ar[i]);
    printf("\n");
    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]