[原创]桶排序 链表 hash C语言实现

3小时前 102

思路：将数放到桶内，先将桶内排序，再整体排序。用链表数组表示桶，
然后用(元素值 + k)/(k+1)来定位插入哪个桶里

k 个桶，最后一个桶用来放最大值，只有 k - 1 个跨度，这 k - 1 个跨度对应 k - 1 个桶。

数对应的桶的下标为 (元素值 + k)/(k+1)

1.遍历原始数组 arr 找到最大值和最小值，确定桶数 k
2.对桶内的数做排序
3.遍历所有的桶，输出结果

#include <iostream>
#include <stdio.h> 
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct no
{
    int data;   //链表定义
    no *pnext;

}node;

typedef struct
{
    node head;
    node tail;  //构造头尾

}lht;

void link_init(lht larr[],int size)
 {
     int i=0;
     while(i<size)
  {
     larr[i].head.pnext=&larr[i].tail;//连接头尾
     larr[i].tail.pnext=NULL;
     i++;
  }
 }

  void link_order(lht larr[],int l,int i)//链表排序
 {
     node *pt,*pf=NULL,*pm=NULL,*pl=NULL,*pn=NULL;
     pn=(node *)malloc(sizeof(node));
     if(pn==NULL)
     exit(0); 
     pf=&larr[l].head;
     pt=pf;
     pm=pf->pnext;
     pl=pm->pnext;

  while( pm!=&larr[l].tail )
 {

     if(pm->data >i)    //排序
     { 

         pn->pnext=pm;
         pf->pnext=pn;
         pn->data=i;
         printf("%d %d... ",l,i);
         return ;
         }
     pt=pt->pnext;
     pf=pt;
     pm=pf->pnext;
     pl=pm->pnext;

 }
 pf->pnext=pn;//*****当插入元素的值大于或小于链表里的任何元素时
 pn->pnext=&larr[l].tail;//**********
 pn->data=i;
 return ;

}

void link_show(const lht larr[],int size)
 {
     int i=0;
   node *pn=larr[i].head.pnext;

    while(i<size) 
    {
    pn=larr[i].head.pnext;
     while(pn!=&larr[i].tail)
     {

         printf("\n%d  %d ",i,pn->data);
         pn=pn->pnext;
     }
     i++;
     }

 }


int main(int argc, char *argv[]) 
{    
    int arr[13]={0,1,99,11,12,4,3,8,77,67,58,69,33};
lht larr[10]={0};//链表数组
  link_init(larr,sizeof(arr)/sizeof(arr[0]));
    int i=0;
    while(i<sizeof(arr)/sizeof(arr[0]))
   {
 link_order(larr,(arr[i]*sizeof(arr)/sizeof(arr[0])))/(99+1),arr[i]);
   i++;
   }
 link_show(larr,sizeof(arr)/sizeof(arr[0]));
    return 0;
}

[公告]安全测试和项目外包请将项目需求发到看雪企服平台：https://qifu.kanxue.com