数据结构排序算法汇总包-直接插入排序 折半插入排序 2—路插入排序 表插入排序 希尔排序 起泡排序 快速排序 简单选择...

#include <math.h> #include<malloc.h> #include<stdlib.h> #include<conio.h> #include"radixSort.h" typedef int KeyType; //基数排序数据类型 typedef struct { int key; }Node; typedef struct { Node element[MAXSIZE+1]; int length; }SqqList; typedef struct { KeyType keys[MAX_NUM_OF_KEY]; int next; }SLCell; typedef struct { SLCell cell[MAX_SPACE+1]; int keynum; int recnum; }SLList; typedef int ArrType[RADIX]; //基数排序 void Sq_convert_SLList(SqqList origin, SLList *operand) { int i = 0, j = 0; for(i = 0; i <=origin.length; i++) { for(j = MAX_NUM_OF_KEY - 1; j >= 0 ; j--) { operand->cell[i].keys[j] = origin.element[i].key % 10; origin.element[i].key = origin.element[i].key / 10; // cout<<operand.cell[i].keys[j]<<" "; } // cout<<endl; } operand->recnum = origin.length+1; for( i = 0; i < operand->recnum; ++i)operand->cell[i].next = i + 1; operand->cell[operand->recnum - 1].next = -1; operand->keynum = MAX_NUM_OF_KEY; } void SLList_convert_Sq(SqqList *handled, SLList operand) { int i = 0, j = 0, p = 0; for(i = 0; i < handled->length; i++)handled->element[i].key = 0; // for(i = 0; i < handled.length; i++) for(i = 0, p = 0; p != -1; p = operand.cell[p].next, i++) { int radix = 1; for(j = MAX_NUM_OF_KEY - 1; j >= 0 ; j--) { handled->element[i].key = handled->element[i].key + operand.cell[p].keys[j] * radix; radix = radix * RADIX; // cout<<handled.element[i].key<<" ";getch(); } /* for(j = 0; j < MAX_NUM_OF_KEY ; j++) { handled.element[i].key = handled.element[i].key + operand.cell[p].keys[j] * radix; radix = radix * RADIX; } */ // i++; } } void Distribute(SLCell cell[], int i, ArrType front, ArrType last) { int j = 0, p = 0; for(j =0; j < RADIX; ++j) { front[j] = 0; last[j] = 0; } for(p = 0; p != -1; p = cell[p].next) { j = cell[p].keys[i]; if(!front[j]) { front[j] = p; } else { cell[last[j]].next = p; } last[j] = p; } } void Collect (SLCell cell[], int i, ArrType front, ArrType last) { int j, t; for(j = 0; !front[j]; j++); cell[0].next = front[j]; t = last[j]; // printf("fuck3\n"); while(j < RADIX - 1) { for(j++; j < RADIX -1 && !front[j]; j++); if(front[j]) { cell[t].next = front[j]; t = last[j]; } cell[t].next = -1; } } void RadixSort(SqqList *handled,long time,long move) { int j; SLList L; ArrType front, last; Sq_convert_SLList(*handled, &L); // for(int i = 0; i < L.recnum + 1; ++i)L.cell[i].next = i + 1; // L.cell[L.recnum].next = 0; for( j = L.keynum - 1; j >= 0; --j) { Distribute(L.cell, j, front, last); Collect(L.cell, j, front, last); } SLList_convert_Sq(handled, L); } void turnRadixSort(int p[], long *movv, long *cmpp ) {SqqList handle;int t; handle.length =p[0]; for(t=1;t<=p[0]+1;t++){ handle.element[t].key=p[t]; } RadixSort(&handle,*movv,*cmpp); for(t=1;t<=p[0];t++){ p[t]=handle.element[t].key; //printf("%d ",handle.element[t].key); //printf("%d ",p[t]); //getch(); } }