當前位置：首頁 » 編程語言 » 基數排序c語言

基數排序c語言

發布時間: 2021-03-22 07:27:45

① 用c語言實現計數排序、基數排序、桶排序演算法。

網上找吧,這些都是基本東西,要不買本數據結構的書看看

② 一道C語言數據結構鏈表求基數排序問題

假如不用基數列復表，制通過逐位藉助棧似乎也可以高效地得到結果（從「嵌套調用」改寫為「藉助棧」），但是不好理解。其實主要思路不復雜：隨機計算至少20個四位數，然後排序，可以用先除再求余數的方法，先得到高位數，把所有四位數分別整理到基數列表（最好可以同步記錄余數到列表項），此時就可以開始遍歷基數列表（從0到9，每個數所代表的列表對應一組「記錄了余數的對象」），對於每個子列表中的所有對象，逐個排列出來到原有數組空間（也就是refill），清理基數列表以便再次使用(記得在每次refill的時候，也需要clearlist，注意訪問的順序不能打亂，可以將上次從表尾加入的列表項找到，從表頭結點後清理)；然後從數組空間里這些對象的余數找到其最高位數，即百位數，再次整理到基數列表，同步逐個排列出來到原有數組空間；以此類推，經過四輪處理就有結果了。

③ c語言歸並排序，基數排序

void merge(int *a, int low, int center, int high){
int m,n,i,j,k;
int *L,*R;
if(low >= high) return;
m = center - low + 1;
n = high - center;
L = (int *)malloc(m * sizeof(int));
R = (int *)malloc(n * sizeof(int));
for(i=0; i<m; ++i) L[i] = a[low+i];
for(i=0; i<n; ++i) R[i] = a[low+i+m];
for(i=0,j=0,k=low; i<m && j<n;++k) {
if(L[i] > R[j])
a[k] = R[j++];
else
a[k] = L[i++];
}
while(i<m) a[k++] = L[i++];
while(j<n) a[k++] = R[j++];
}
void m_sort(int *a, int low, int high){
int center;
if(low < high) {
center = (low + high)/2;
m_sort(a, low, center);
m_sort(a, center+1, high);
merge(a, low, center, high);
}
}
int main(){
int i;
int a[] = {23, 2, 45, 78, 1, 99, 3,65,43,55};
m_sort(a, 0, 6);
for(i=0; i<10; ++i) {
printf("%d ",a[i]);
}
return 0;
}

④ C語言，基數排序

#include <stdio.h>

typedef struct node {
int data;
int next;
} node;

int head; //這里的head是全局變數
int fr[10];
int re[10];

void Distribute(node *a, int w) //第一次w=1
{
int i;
for (i=0; i<10; i++) { //初始化
fr[i] = -1;
}
for (i=head; i!=-1; i=a[i].next) { //第一次i=0
int x = a[i].data / w % 10; //這是以前求一個數各個位的方法例：98%10=8(個位) 98/10%10=9(十位)

if (fr[x] == -1) {
fr[x] = re[x] = i;
}
else {
a[re[x]].next = i;
re[x] = i;
}
}
for (i=0; i<10; i++) {
if (fr[i] != -1) {
a[re[i]].next = -1;
}
}
}

void Collect(node *a)
{
int i, last;

last = -1;
for (i=0; i<10; i++) {
if (fr[i] != -1) {
if (last == -1) {
head = fr[i];
last = re[i];
}
else {
a[last].next = fr[i];
last = re[i];
}
}
}
a[last].next = -1;
}

void Out(node *a, int w)
{
int i, p, k;

printf("weight == %d\n", w);
for (i=0; i<10; i++) {
printf("fr[%d] ", i);
p = fr[i];
k = 0;
while (p != -1) {
printf("->%4d ", a[p].data);
p = a[p].next;
k++;
}
while (k<3) printf("-------"),k++;
printf("-> re[%d]\n", i);
}
}

void Output(node *a, int head) //結構體指針，這里的head是形參，調用此函數結束後即釋放，不影響全局變數head的值
{
while (head != -1) {
printf("%4d", a[head].data);
head = a[head].next;
}
printf("\n");
}

void main()
{
//對於無數據的數組排序會出錯~~~
//614 738 921 485 637 101 215 530 790 306
node a[10]; //結構體數組
int i, n = 10, max;
max = 0x80000000; //此處對0x80000000及MAX的意思不理解
printf("max == %d\n", max);
printf("Please intput %d numbers~\n", n);
for (i=0; i<n; i++) {
scanf("%d", &a[i].data); //賦值
a[i].next = i + 1;
if (a[i].data > max) max=a[i].data;
}
head = 0;
a[n - 1].next = -1;

Output(a, head);
for (i=1; i<=max; i*=10) {
Distribute(a, i);
Out(a, i);
Collect(a);
Output(a, head);
}
}

⑤ c語言，基數排序

如圖

//#pragmaGCCdiagnosticerror"-std=c11"
#include<stdlib.h>//有隨機數庫
#include<malloc.h>
#include<time.h>//用於產生隨機數種子
#include<string.h>
#include<stdio.h>

#defineLEN30//要多長這里改就行
intA[LEN];

intascend(constvoid*a,constvoid*b){
return*((int*)a)-*((int*)b);
}

voidprintArr(intA[],intlen){
inti;
for(i=0;i<len;++i){
printf("%d",A[i]);
if((i+1)%10==0)putchar(' ');//10個數換一行
}
}

intmain(){
inti;
srand(time(0));//置隨機數種子
printf("生成隨機數：↓ ");
for(i=0;i<LEN;++i){
A[i]=rand();
}
printArr(A,LEN);

printf(" 排序後：↓ ");
qsort(A,LEN,sizeof(int),ascend);
printArr(A,LEN);
return0;
}

⑥ C語言，基數排序(149,138,165,197,176,113,127)

基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

以LSD為例，假設原來有一串數值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接著再進行一次分配，這次是根據十位數來分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。

LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式恰與LSD相反，是由高位數為基底開始進行分配，其他的演算方式則都是相同。

⑦ C語言排序的方法

現在流行的排序有：直接插入排序、冒泡排序、簡單選擇排序、希爾排回序、快速排序答、堆排序、歸並排序、基數排序。

對n個記錄進行選擇排序的方法是：通過n-i次關鍵字之間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，並和第i（1<=i<=n）個記錄進行交換，當i等於n時所有記錄都已有序排列。

void selectsort(int data[],int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(data[j]<data[k]) k=j;
if(k!=i)
{
temp=data[i];data[i]=data[k];data[k]=temp;
}//if
}//for
}//for
}//selectsort

⑧ 求c語言基數排序與桶排序的源代碼

基數排序：

#include<math.h>
testBS()
{
inta[]={2,343,342,1,123,43,4343,433,687,654,3};
int*a_p=a;
//計算數組長度
intsize=sizeof(a)/sizeof(int);
//基數排序
bucketSort3(a_p,size);
//列印排序後結果
inti;
for(i=0;i<size;i++)
{
printf("%d
",a[i]);
}
intt;
scanf("%d",t);
}
//基數排序
voidbucketSort3(int*p,intn)
{
//獲取數組中的最大數
intmaxNum=findMaxNum(p,n);
//獲取最大數的位數，次數也是再分配的次數。
intloopTimes=getLoopTimes(maxNum);
inti;
//對每一位進行桶分配
for(i=1;i<=loopTimes;i++)
{
sort2(p,n,i);
}
}
//獲取數字的位數
intgetLoopTimes(intnum)
{
intcount=1;
inttemp=num/10;
while(temp!=0)
{
count++;
temp=temp/10;
}
returncount;
}
//查詢數組中的最大數
intfindMaxNum(int*p,intn)
{
inti;
intmax=0;
for(i=0;i<n;i++)
{
if(*(p+i)>max)
{
max=*(p+i);
}
}
returnmax;
}
//將數字分配到各自的桶中，然後按照桶的順序輸出排序結果
voidsort2(int*p,intn,intloop)
{
//建立一組桶此處的20是預設的根據實際數情況修改
intbuckets[10][20]={};
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum為上式中的1、10、100
inttempNum=(int)pow(10,loop-1);
inti,j;
for(i=0;i<n;i++)
{
introw_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++)
{
if(buckets[row_index][j]==NULL)
{
buckets[row_index][j]=*(p+i);
break;
}
}
}
//將桶中的數，倒回到原有數組中
intk=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if(buckets[i][j]!=NULL)
{
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}

桶排序

#include<stdio.h>
#defineMAXNUM100

voidbucksort(intarr[],intN,intM)
{
intcount[MAXNUM];
for(inti=0;i<=M;i++)
{
count[i]=0;
}

for(inti=0;i<N;i++)
{
++count[arr[i]];
}

for(inti=0;i<=M;i++)
{
for(intj=1;j<=count[i];j++)
{
printf("%d",i);
}
}
}

intmain()
{
inta[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6};
bucksort(a,sizeof(a)/sizeof(a[0]),12);
return0;
}

⑨ 鏈式基數排序的演算法思想（C語言），越多越仔細越好

參考
/* 基數排序的演算法源程序*/
#include <stdio.h>
#define D 3 /* D為排序碼的最大位數 */
#define R 10 /* R為基數 */
typedef int KeyType;
typedef int DataType;
struct Node; /* 單鏈表結點類型 */
typedef struct Node RadixNode;
struct Node {
KeyType key[D];
/* DataType info;*/
RadixNode *next;
};
typedef RadixNode * RadixList;
typedef struct QueueNode {
RadixNode *f; /* 隊列的頭指針 */
RadixNode *e; /* 隊列的尾指針 */
} Queue;
Queue queue[R];
void radixSort(RadixList * plist, int d, int r) {
int i,j,k;
RadixNode *p, *head = (*plist)-> next;
for(j = d-1; j > = 0; j--) { /* 進行d次分配和收集*/
p = head;
for(i = 0; i < r; i++) {
queue[i].f = NULL; queue[i].e = NULL; /* 清隊列 */
}
while (p != NULL) {
k = p-> key[j]; /* 按排序碼的第j個分量進行分配*/
if (queue[k].f == NULL)
queue[k].f = p; /* 若第k個隊列為空，則當前記錄為隊頭*/
else (queue[k].e)-> next = p;/* 否則當前記錄鏈接到第k隊的隊尾*/
queue[k].e = p;
p = p-> next;
}
for(i = 0; queue[i].f == NULL; i++) /* 找出第一個非空隊列*/
;
p = queue[i].e; head = queue[i].f; /* head為收集鏈表的頭指針*/
for(i++; i < r; i++)
if(queue[i].f != NULL) { /* 收集非空隊列 */
p-> next = queue[i].f;
p = queue[i].e;
}
p-> next = NULL;
}
(*plist)-> next = head;
}
struct Node element[11]={
0,0,0,NULL,/*表頭*/
0,3,6,NULL,/*36*/
0,0,5,NULL,/*5*/
0,1,6,NULL,/*16*/
0,9,8,NULL,/*98*/
0,9,5,NULL,/*95*/
0,4,7,NULL,/*47*/
0,3,2,NULL,/*32*/
0,3,6,NULL,/*36*/
0,4,8,NULL,/*48*/
0,1,0,NULL /*10*/
};
int main(){
int i;
RadixList p = element;
for (i = 0; i < 10; i++)
element[i].next = &element[i+1];
element[10].next = NULL;
radixSort(&p, 3, 10);
p = p-> next;
while (p != NULL){
printf( "%d ", p-> key[1]*10+p-> key[2]);
p = p-> next;
}
getchar();
return 0;
}

閱讀全文

基數排序c語言

與基數排序c語言相關的閱讀推薦