排序算法（2）

本此介绍十大经典排序算法的后五个：

• 快速排序
• 堆排序
• 计数排序
• 桶排序
• 基数排序

快速排序

算法步骤

1. 比较相邻元素的大小如果第一个小于第二个就交换他们的位置
2. 循环比较每一对，最后一个元素会是最小的元素
3. 重复上面的操作，除了最后一个，因为最后一个已经确定
4. 继续重复比较直到全部比较完成，或某次比较没有任何元素交换

代码实现

void quick_sort(int *list, int low, int high)
{
    int key = list[low];
    int i = low;
    int j = high;
    int temp;
    if (low >= high)
    {
        return;
    }

    while (low < high)
    {
        while (low < high && key >= list[high])
        {
            --high;
        }
        if (list[high] > key)
        {
            list[low] = list[high];
            ++low;
        }
        while (low < high && key <= list[low])
        {
            ++low; //向后寻找
        }
        if (key > list[low])
        {
            list[high] = list[low]; //直接赋值, 不用交换
            --high;
        }
        list[low] = key;
        quick_sort(list, i, low-1);
        quick_sort(list, low+1, j);
    }

}

---

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

算法步骤

1. 构造一个堆
2. 取出根节点，并将最后一个叶子节点放到根节点的位置
3. 重新将二叉树构造成堆
4. 重复上述操作，直到排序完成

代码实现

void adjust_heap(int *list, int head, int l)
{
    int tmp;
    if (list[head] > list[head * 2 + 1] && head * 2 + 1 < l)
    {
        tmp = list[head];
        list[head] = list[head * 2 + 1];
        list[head * 2 + 1] = tmp;
    }

    if (list[head] > list[head * 2 + 2] && head * 2 + 2 < l)
    {
        tmp = list[head];
        list[head] = list[head * 2 + 2];
        list[head * 2 + 2] = tmp;
    }
}

void heap_sort(int *list,int len)
{
    int i, temp;
    if ( len <= 0)
    {
        return;
    }

    for (i = (len - 1) / 2; i >= 0; i--)
    {
        adjust_heap(list, i, len);
    }

    for(i = len - 1; i > 0; i--)
    {
        temp=list[0];
        list[0]=list[i];
        list[i]=temp;
    }

    heap_sort(list,len-1);
}

---

计数排序

算法步骤

1. 扫描数组获得最大值max和最小值min
2. 开辟空间（数组）A，大小为：max-min+1
3. 新的数组A记录的是对应元素的元素个数
4. 遍历新的数组A输出对应元素及其个数

   即我们要排列的数组为{3,5,5,2,8},则新数组A为A[7] = {1,1,0,2,0,0,1}。代表有1个2,1个3,0个4,2个5,0个6,0个7,1个8

代码实现

void count_sort(int *list, int len)
{
    int i, j = len-1, max = list[0], min = list[0];
    for (i = 0; i < len; i++)
    {
        if (list[i] > max)
        {
            max = list[i];
        }
        if (list[i] < min)
        {
            min = list[i];
        }
    }
    int tmplen = max - min + 1;
    int tmp[tmplen];
    for (i = 0; i < tmplen; i++)
    {
        tmp[i] = 0;
    }

    for (i = 0; i < len; i++)
    {
        tmp[list[i] - min]++;
    }

    for (i = 0; i < tmplen; i++)
    {
        for (; tmp[i] > 0 && j >= 0; )
        {
            list[j] = min + i;
            j--;
            tmp[i]--;
        }
    }
}

---

桶排序

算法步骤

桶排序基于计数排序

1. 找到最大值和最小值，将数组按区间分为n个桶
2. 将符合区间的数放入桶中
3. 在放入桶中的同时就按顺序排好（插入到桶中合适的位置）
4. 全部元素放入桶中后将各个桶的元素拼接起来

代码实现

此代码按照个人理解使用单链表实现

typedef struct bucketlist
{
    int key;
    struct bucketlist* next;
}BUCKET;

void free_node(BUCKET *node)
{
    BUCKET *tmp;
    if (node == NULL)
    {
        return;
    }

    while (node->next != NULL)
    {
        tmp = node;
        tmp = tmp->next;
        node->next = tmp->next;
        free(tmp);
    }
    free(node);
}

void instertion(BUCKET *bucket, int number)
{
    int i;
    BUCKET *temp = bucket;
    if (bucket == NULL)
    {
        return;
    }
    for (;;)
    {
        if (temp->next == NULL ||temp->next->key < number)
        {
            BUCKET *node  = (BUCKET*)malloc(sizeof(BUCKET));
            node->next = temp->next;
            node->key = number;
            temp->next = node;
            return;
        }
        else
        {
            temp = temp->next;
        }
    }

}

void bucket_sort(int *list, int len)
{
    int i = 0, j = 0, max = list[0], min = list[0];
    for (i = 0; i < len; i++)
    {
        if (list[i] > max)
        {
            max = list[i];
        }
        if (list[i] < min)
        {
            min = list[i];
        }
    }

    int tmplen = (max - min) / 3;
    BUCKET *buket1  = (BUCKET*)malloc(sizeof(BUCKET));
    buket1->next = NULL;
    BUCKET *buket2  = (BUCKET*)malloc(sizeof(BUCKET));
    buket2->next = NULL;
    BUCKET *buket3  = (BUCKET*)malloc(sizeof(BUCKET));
    buket3->next = NULL;
    BUCKET *tmp;

    for (i = 0; i < len; i++)
    {
        if (list[i] <= min + tmplen)
        {
            instertion(buket1,list[i]);
        }
        else if (list[i]> min + tmplen && list[i] <= min + (2 * tmplen))
        {
            instertion(buket2,list[i]);
        }
        else
        {
            instertion(buket3,list[i]);
        }
    }
    tmp = buket3->next;
    while (tmp != NULL)
    {
        list[j] = tmp->key;
        tmp = tmp->next;
        j++;
    }
    tmp = buket2->next;
    while (tmp != NULL)
    {
        list[j] = tmp->key;
        tmp = tmp->next;
        j++;
    }
    tmp = buket1->next;
    while (tmp != NULL)
    {
        list[j] = tmp->key;
        tmp = tmp->next;
        j++;
    }

    free_node(buket3);
    free_node(buket2);
    free_node(buket1);

}

---

基数排序

算法步骤

1. 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
2. 从最低位开始，依次进行一次排序
3. 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

代码实现

此实现使用之前的数据结构-队列为基础,使用了其中的方法。

void radix_sort(int *list, int len)
{
    int i = 0, j = 0;
    LINKLIST *queue[10];
    for (i = 0; i < 10; i++)
    {
        queue[i] = init_list();
    }
    for (i = 0; i < len; i++)
    {
        push(queue[list[i] % 10],list[i]);
    }
    for (i = 0; i < 10; i++)
    {
        while (!is_empty(queue[i]))
        {
            list[j] = pop(queue[i]);
            j++;
        }
    }
    j = 0;
    for (i = 0; i < len; i++)
    {
        push(queue[list[i]/10 % 10],list[i]);
    }
    for (i = 0; i < 10; i++)
    {
        while (!is_empty(queue[i]))
        {
            list[j] = pop(queue[i]);
            j++;
        }
    }
}