桶排序

桶排序：适用于小数排序，相同位数的数进行排序。

我觉得桶排序是计数排序与哈希表的结合

思路：按照最高位申请空间，然后把最高位相同的放入相同的桶中，然后将一个桶中的数排序。（即高位相同的排序）

最后按照顺序，将哈希表中的值放回数组。

我的代码：在对链表排序是使用冒泡排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node1
{
    int num;
    struct node1* pnext;
}Node;
Node** CreateHash(int* arr,int len,int n,int* lenth)
{
    if(arr == NULL || len == 0) return NULL;

    int Min = arr[0]/n;
    int Max = arr[0]/n;
    for(int i = 0; i < len;i++)
    {
        if(arr[i]/n < Min)
            Min = arr[i]/n;
        else if(arr[i]/n > Max)
            Max = arr[i]/n;
    }
    *lenth = Max-Min+1;
    Node** HashArr = (Node**) malloc(sizeof(Node*)*(*lenth));
    memset(HashArr,0,sizeof(Node*)*(*lenth));
    //放入桶中
    for(int i = 0 ;i < len;i++)
    {
        Node* tmp = (Node*)malloc(sizeof(Node*));
        tmp->num = arr[i];
        tmp->pnext = HashArr[arr[i]/n - Min] ;
        HashArr[arr[i]/n - Min] = tmp;
    }

    return HashArr;
}
void Sort(Node* Hash)
{
    Node* tmp = Hash;
    int n,len = 0;
    while(tmp != NULL)
    {
        len++;
        tmp = tmp->pnext;
    }
    Node* pMark = NULL;
    for(int i = 0; i < len;i++)//冒泡排序
    {
        for(int j = 0; j < len-i-1;j++)//遍历链表，将最大值放在最后
        {
            if(tmp->num > tmp->pnext->num)
            {
                n = tmp->num;
                tmp->num = tmp->pnext->num;
                tmp->pnext->num = n;

            }
            tmp = tmp->pnext;
        }
    }
}
int main()
{
    int arr[] = {100,103,399,419,536,207,108,220};
    int len = sizeof(arr)/sizeof(arr[0]);
    //位数
    int x = arr[0];int n = 10;
    while(x/n)
    {
        n*=10;
    }
    n/=10;
    int lenth;//Hash表长度
    Node** HashArr = CreateHash(arr,len,n,&lenth);
    //排序
    for(int i = 0; i < lenth;i++ )//hash表遍历
    {
        Sort(HashArr[i]);
    }
    //放回原数组
    int id = 0;
    for(int i = 0; i < lenth;i++)
    {
        while(HashArr[i] != NULL)
        {
            arr[id++] = HashArr[i]->num;
            HashArr[i] = HashArr[i]->pnext;
        }
    }
    //打印数组
    for(int i = 0; i < len;i++)
    {
        printf("%d ",arr[i]);
    }
    //删除
    Node *tmp;
    Node* pDel;
    for(int i = 0; i < lenth;i++)
    {
        tmp = HashArr[i];
        while(tmp)
        {
            pDel = tmp;
            tmp = tmp->pnext;
            free(pDel);
            pDel = NULL;
        }
    }
}

代码二：在对链表排序时使用插入排序，所以结构体要定义为前后两个指针。

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 typedef struct node1
  5 {
  6     int num;
  7     struct node1* pnext;
  8     struct node1* pre;
  9 }Node;
 10 void Sort(Node* Hash)
 11 {
 12     if(Hash == NULL || Hash->pnext == NULL) return;
 13     Node* UnSort = Hash->pnext;
 14     int tmp = 0;
 15     Node* Sort = NULL;
 16     while(UnSort != NULL)
 17     {
 18         tmp = UnSort->num;//无序的第一个
 19         Sort = UnSort->pre;//有序的最后一个
 20         while(Sort && tmp < Sort->num)
 21         {
 22             Sort->pnext->num = Sort->num;
 23             Sort = Sort->pre;
 24         }
 25         if(Sort == NULL)
 26         {
 27             Hash->num = tmp;
 28         }
 29         else
 30         {
 31             Sort->pnext->num = tmp;
 32         }
 33         UnSort = UnSort->pnext;
 34     }
 35 }
 36 void CreateHash(int* arr,int len)
 37 {
 38     if(arr == NULL || len == 0) return ;
 39     //位数
 40     int x = arr[0];int n = 10;
 41     while(x/n)
 42     {
 43         n*=10;
 44     }
 45     n/=10;
 46 
 47     int Min = arr[0]/n;
 48     int Max = arr[0]/n;
 49     for(int i = 0; i < len;i++)
 50     {
 51         if(arr[i]/n < Min)
 52             Min = arr[i]/n;
 53         else if(arr[i]/n > Max)
 54             Max = arr[i]/n;
 55     }
 56     Node** HashArr = (Node**) malloc(sizeof(Node*)*(Max-Min+1));
 57     memset(HashArr,0,sizeof(Node*)*(Max-Min+1));
 58     //放入桶中
 59     for(int i = 0 ;i < len;i++)
 60     {
 61         int index = arr[i]/n-Min;
 62         Node* tmp = (Node*)malloc(sizeof(Node));
 63         tmp->num = arr[i];
 64         tmp->pre = NULL;
 65         tmp->pnext = HashArr[index] ;
 66 
 67         if(HashArr[index])
 68         {
 69             HashArr[index]->pre = tmp;
 70         }
 71         HashArr[index] = tmp;
 72     }
 73     //排序
 74     for(int i = 0; i < Max-Min+1; i++)
 75     {
 76         Sort(HashArr[i]);
 77     }
 78     //放回
 79     int id = 0;
 80     for(int i = 0; i < Max-Min+1; i++)
 81     {
 82         while(HashArr[i] != NULL)
 83         {
 84             arr[id++] = HashArr[i]->num;
 85             HashArr[i] = HashArr[i]->pnext;
 86         }
 87     }
 88     //打印数组
 89     for(int i = 0; i < len;i++)
 90     {
 91         printf("%d ",arr[i]);
 92     }
 93     //删除
 94     Node* pDel = NULL;
 95     Node* tmp = NULL;
 96     for(int i = 0; i < Max-Min+1; i++)
 97     {
 98         tmp = HashArr[i];
 99         while(tmp)
100         {
101             pDel = tmp;
102             tmp = tmp->pnext;
103             free(pDel);
104             pDel = NULL;
105         }
106     }
107     free(HashArr);
108     HashArr = NULL;
109 }
110 
111 int main()
112 {
113     int arr[] = {100,103,399,419,536,207,108,220};
114     int len = sizeof(arr)/sizeof(arr[0]);
115 
116     CreateHash(arr,len);
117 
118 }