數據結構的排序演算法動畫演示

⑴ 數據結構的排序方法有哪些

冒泡排序，快速排序，堆排序。

⑵ 用flash模擬二叉樹線索化

B樹的刪除
B樹的生長過程
三元組表的轉置
中序線索化二叉樹
串的順序存儲
二分查找
二叉排序樹的刪除
二叉排序樹的生成
二叉樹的建立
克魯斯卡爾演算法構造最小生成樹
冒泡排序
分塊查找
單鏈表結點的刪除
單鏈表結點的插入
圖的深度優先遍歷
基數排序
堆排序
頭插法建單鏈表
尋找中序線索化二叉樹指定結點的前驅
尋找中序線索化二叉樹指定結點的後繼
尾插法建表
希兒排序
開放定址法建立散列表
循環隊列操作演示
快速排序
拉鏈法創建散列表
拓撲排序
數據結構和演算法Flash動畫演示.rar
最短路徑
樸素串匹配演算法過程示意
構造哈夫曼樹的演算法模擬
構造哈夫曼樹過程
棧與遞歸

⑶ 數據結構 10.10 堆排序演算法演示（一）

希賽教育計算機專業考研專業課輔導招生

希賽教育計算機專業考研專業課輔導視頻

希賽教育計算機考研專業課在線測試系統

已知關鍵字序列{ }是大頂堆 當將 和 互換之後 它就不再是個堆 但此時 已是選出的最大關鍵字 不需要再參加排序 由此只要對其餘關鍵字進行排序 如果能將它重新調整為一個大頂堆 這就等於選出了第二個最大關鍵字 而此時的關鍵字序列有下列特點 除根結點之外 其左子樹和右子樹都仍然是堆 由此只要從上到下進行篩選可將該序列重新調整為大頂堆

⑷ 數據結構中有關拓撲排序的相關知識

將入度為0的結點入隊，刪除後同時將所有相鄰頂點的先決條件減一。當某個頂點的計數為0時，將它入隊。這是關鍵思想。

⑸ 面試必會八大排序演算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

演算法適用於少量數據的排序，時間復雜度為O(n^2)。

插入排演算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

③如果該元素（已排序）大於新元素，將該元素移到下一位置

④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

⑤將新元素插入到該位置中

⑥重復步驟2

排序演示

演算法實現

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重復以上的步驟，除了最後一個。

④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

演算法實現：

三、快速排序

介紹

快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數 + 分治法。

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 「基準」（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重復第二步，直至各區間只有一個數。

排序演示

演算法實現

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；

②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。

排序演示

演算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

演算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

演算法實現

七、歸並排序

介紹

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。

演算法思想

自上而下遞歸法（假如序列共有n個元素）

① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；

③ 重復步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

④ 重復步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。

排序演示

演算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。

基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

演算法實現

九、總結

各種排序的穩定性、時間復雜度、空間復雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間復雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；

O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；

線性階O(n)排序：基數排序，此外還有桶、箱排序。

⑹ 數據結構十種排序演算法總結

部分來自 https://mp.weixin.qq.com/s/feQDjby4uYGRLbYUJq7Lpg?

首先先上張圖 好好記住

圖中的名字的意思：
n: 數據規模
k: 「桶」的個數
In-place: 佔用常數內存，不佔用額外內存
Out-place: 佔用額外內存
這么一看感覺很亂 我們分下類，瞬間感覺很簡單

然後最後三種非比較的演算法的區別是：
基數排序：根據鍵值的每位數字來分配桶
計數排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數值

⑺ 誰教我：數據結構的各種排序

1.快速排序

#include"stdio.h"
#define N 100
int a[N]={0};//存放要排序的數

int Qsort(int m,int n)//對數組中m到n的元素進行快速排序
{
int p,q;
int head,sign;
if(m!=n)//選定的數列不止一個元素
{
head=a[n];//選擇數列的末尾元素作為比較元素
p=m;//p標記數列的首元素
q=n-1;//標記末尾元素的前一個元素
sign=n;//記錄比較元素的位置，以其作為空位置
while(p<=q)//分別比較p、q所標記的元素與比較元素的大小，比其小的放在左邊，比其大的放在右邊
{
while(a[p]<head)//p所指元素比比較元素小，p右移
{
p++;
if(p>q)
{
break;
}
}
a[sign]=a[p];//將p所指元素移入空位置
sign=p;//記錄空餘位置
p++;
if(p>q)
{
break;
}
while(a[q]>head)//q所指元素比比較元素大，q左移
{
q--;
if(p>q)
{
break;
}
}
a[sign]=a[q];
sign=q;
q--;
}
a[sign]=head;//比較完成後，將比較元素移入空位置
if(sign-1>m)
{
Qsort(m,sign-1);//對m到sign-1的數列進行排序
}
if(sign+1<n)
{
Qsort(sign+1,n);//對sign+1到n的數列進行排序
}
}
return(1);
}

int Print(int m,int n)//對m到n的數組序列輸出
{
int i;
for(i=m;i<=n;i++)
{
printf("%d\n",a[i]);
}
return(1);
}

int main()
{
int n,i;
scanf("%d",&n);//輸入將要排序的數的個數
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);//輸入要排序的數
}
Qsort(0,n-1);
Print(0,n-1);
}
二、 詳細設計：重要函數中的演算法設計，實現流程，傳遞參數的說明；

三、調試分析與心得體會：
快速排序的思想時從數組序列中選定一個元素，將序列中其餘元素與其進行比較，將比其小的放在左邊，比其大的放在右邊，然後以比較元素為中點，將序列分成兩部分，再將它們分別進行快速排序，依次類推，直到序列中只有一個元素為止。

2.合並排序

#include"stdio.h"
#define N 10000
int a[N];//用a數組記錄所給無序數列
int b[N]={0};//用b數組記錄每次排序之後的a數組
int sign=0;
void Merge(int m,int mid,int n)//將兩個有序數列合並成為一個有序數列
{
int i,j,k;
i=k=m;
j=mid+1;
while(i<=mid&&j<=n)//依次比較兩個有序數列中的元素，從大到小將其放入b數組相應位置中
{
if(a[i]<a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
if(i<=mid)//將比較之後的剩餘元素放入b數組相應位置
{
while(i<=mid)
{
b[k]=a[i];
k++;
i++;
}
}
else
{
while(j<=n)
{
b[k]=a[j];
k++;
j++;
}
}
for(i=m;i<=n;i++)//將合並後的數列重新放入a數組相應位置
{
a[i]=b[i];
}
}
int Msort(int m,int n)//對所給無序數列進行排序
{
int mid;
if(n!=m)
{
mid=(n+m)/2; //將數列一分為二直到其只有一個元素
Msort(m,mid);
Msort(mid+1,n);
Merge(m,mid,n);//將分割後的數列重新合並起來
}
return(1);
}
void Print(int num)//將序列依次輸出
{
int i;
for(i=0;i<num;i++)
{
printf("%d\n",a[i]);
}
}
int main()
{
int sign;
int i;
int num;
scanf("%d",&num);//輸入將要排序的數的個數
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);//依次輸入要排序的數
}
sign=Msort(0,num-1);
Print(num);//輸出完成排序後的有序數列
}
二、 詳細設計：重要函數中的演算法設計，實現流程，傳遞參數的說明；
三、調試分析與心得體會：
合並排序是排序的一種常用方法，其主要思想為：將一個無序數列依次分割直到其每個序列只有一個元素為止，然後再將兩個序列合並為一個有序數列，依此類推。

3.我的數據結構實驗課題（關於排序）

//問題描述：排序器
//要 求：實現以下六種排序演算法，將給定的不同規模大小的數據文件（data01.txt，data02.txt，data03.txt，data04.txt）進行排序，
//並將排序結果分別存儲到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。
//1）、Shell排序； 2）、Quick排序
//3）、錦標賽排序； 4）、堆排序
//5）、歸並排序； 6）、基數排序
//在實現排序演算法1）~4）時，統計數據元素比較的次數和交換的次數，進而對這四種演算法在特定數據條件下的效率進行分析和評判。

#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 10000000
#define N 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define LEN sizeof(SqList)
#define Maxr 10
#define MAXNUM 100000000

typedef struct node{
int key;
int num;
};
typedef struct {
struct node r[Maxsize+1];
long length;
}SqList,*qSqList;
typedef struct node2{
struct node r;
struct node2 *next;
}RecType;
long shifttimes;//統計移動次數
long comparetimes;//統計比較次數

qSqList creat(char filename[])//讀入文件並且將數據保存
{
FILE *fp;
long i;
qSqList L;
L=(qSqList)malloc(LEN);
L->length=0;
if((fp=fopen(filename,"r"))==NULL)//文件不存在時終止程序
{
printf("cannot open file\n");
exit(0);
}
for(i=1;i<Maxsize+1;i++)
{
fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num));
if(L->r[i].key<0)
break;
L->length++;//記錄讀入的數據長度
}
fclose(fp);
return(L);
}

void Print2(qSqList L)//將序列輸出到指定的文件中
{
long i;
FILE *fp;
char filename[N];
printf("\n\t請輸入存儲文件名：");
scanf("%s",filename);//輸入將要儲存的文件名
fp=fopen(filename,"w");
for(i=1;i<=L->length;i++)//將鏈表中數據逐一寫入文件中
{
fprintf(fp,"%d (%d)\n",L->r[i].key,L->r[i].num);
}
fclose(fp);
}

void Print(qSqList L)//列印數據個數以及排序過程中的比較次數和移動次數
{
printf("\n\t數據個數:%ld",L->length);
printf("\n\t比較次數:%ld",comparetimes);
printf("\n\t移動次數:%ld",shifttimes);
}

struct node Min1(struct node a,struct node b)//比較兩接點關鍵字的大小
{
struct node temp;
if(a.key>b.key)
temp=b;
else
temp=a;
comparetimes++;
return(temp);
}

qSqList shellinsert(qSqList L,int dk)//對順序表以dk為增量作直接插入排序
{
int i,j;
for(i=dk+1;i<=L->length;i++)
{
if(LT(L->r[i].key,L->r[i-dk].key))//將L->r[i]插入到有序增量子表
{
L->r[0]=L->r[i];//將L->r[i]暫時存儲在L->r[0]
shifttimes++;
for(j=i-dk;j>0&<(L->r[0].key,L->r[j].key);j-=dk)//記錄後移，查找插入位置
{
L->r[j+dk]=L->r[j];
comparetimes++;
shifttimes++;
}
if(j>0)
comparetimes++;
L->r[j+dk]=L->r[0];//插入
shifttimes++;
}
comparetimes++;
}
// Print(L);
return(L);
}

qSqList shell(qSqList L)//希爾排序
{
int i,t=0;
int k;
for(t=0;LQ(pow(2,t),(L->length+1));t++);
t=t-1;
// printf("%d",t);
for(i=1;i<=t;++i)
{
k=(int)pow(2,t-i+1)-1;//計算排序增量
L=shellinsert(L,k);
}
Print(L);
Print2(L);
return(L);
}

long Quicksort(qSqList L,long low,long high)//交換順序表L中子表L->r[low..high]的記錄，使樞軸記錄到位，並返回其所在位置
{
int pivotkey;
pivotkey=L->r[low].key;//用序列的第一個記錄作樞軸記錄
while(low<high)//從表的兩端交替地向中間掃描
{
while(low<high&&L->r[high].key>=pivotkey)//將比樞軸記錄小的記錄交換到低端
{
comparetimes++;
high--;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
while(low<high&&L->r[low].key<=pivotkey)//將比樞軸記錄大的記錄交換到高端
{
comparetimes++;
low++;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
}
return(low);//返回樞軸所在位置
}

qSqList Quick2(qSqList L,long low,long high)//對順序表L中的子序列L.r[low..high]作快速排序
{
long pivot;
if(low<high)//序列長度大於1
{
pivot=Quicksort(L,low,high);//將序列一分為二
Quick2(L,low,pivot-1);//對低位子表遞歸排序
Quick2(L,pivot+1,high);//對高位子表遞歸排序
}
return(L);
}

qSqList Quick(qSqList L)//對順序表作快速排序
{
long low,high;
low=1;//將第一個數據所在位置定義為低位
high=L->length;//將最後一個數據所在位置定義為高位
L=Quick2(L,low,high);//對順序表作快速排序
Print(L);
Print2(L);
return(L);
}

void TourSort(SqList *L,long n)//錦標賽排序
{
qSqList Lp;
long i=0,t=1,k=1,w;
while(t<n)//t表示完全二叉樹的結點個數
{
t=(long)pow(2,i);
i++;
}
t=2*t;
Lp=(qSqList)malloc((sizeof(SqList)));
Lp->length=t-1;
for(i=t-1;i>=t/2;i--)
{
if(k>n)
Lp->r[i].key=MAXNUM;
else
{
Lp->r[i]=L->r[k];

}
shifttimes++;
k++;
}
i=t-1;
while(i!=1)
{
Lp->r[i/2]=Min1(Lp->r[i],Lp->r[i-1]);
i-=2;
comparetimes++;
shifttimes++;
}
for(i=1;i<=n;i++)
{
L->r[i]=Lp->r[1];
shifttimes++;
w=1;
while(w<t/2)
{
if(Lp->r[2*w].key==Lp->r[w].key)
w*=2;
else
w=2*w+1;
}
Lp->r[w].key=MAXNUM;//將其賦為最大值
shifttimes++;
if(w%2)
Lp->r[w/2]=Lp->r[w-1];
else
Lp->r[w/2]=Lp->r[w+1];
shifttimes++;
while(w!=1)
{
if(w%2)
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w-1]);
else
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w+1]);
comparetimes++;
shifttimes++;
w/=2;
}
}
Print(L);
Print2(L);
}

void Heapadjust(qSqList L,long s,long m)//調整L->[s]的關鍵字，使L->r[s..m]成為一個大頂堆
{
long j;
struct node rc;
rc=L->r[s];
for(j=2*s;j<=m;j*=2)//沿key較大的接點向下篩選
{
if(j<m&<(L->r[j].key,L->r[j+1].key))//j為key較大的記錄的下標
{
j++;
comparetimes++;
}
if(!LT(rc.key,L->r[j].key))
{
comparetimes++;
break;
}
L->r[s]=L->r[j];//rc插入位置s
shifttimes++;
s=j;
}
L->r[s]=rc;//插入
shifttimes++;
}

qSqList Heap(qSqList L)//堆排序
{
long i;
for(i=L->length/2;i>0;--i)//把L建成大頂堆
Heapadjust(L,i,L->length);
for(i=L->length;i>1;--i)//將堆頂記錄和當前未經排序子序列中最後一個記錄交換
{
L->r[0]=L->r[1];
L->r[1]=L->r[i];
L->r[i]=L->r[0];
shifttimes=shifttimes+3;
Heapadjust(L,1,i-1);//將L重新調整為大頂堆
}
Print(L);
Print2(L);
return(L);
}

void Merge(qSqList L,int low,int m,int high)//將兩個有序表R[low..m]he R[m+1..high]歸並為一個有序表R[low,high]
{
int i=low,j=m+1,k=0;//k是temp的下標，i,j分別為第1，2段的下標
struct node *temp;
temp=(struct node*)malloc((high-low+1)*sizeof(struct node));//用於臨時保存有序序列
while(i<=m&&j<=high)//在第1段和第2段均未掃描完時循環
{
if(LT(L->r[j].key,L->r[i].key))//將第1段中的記錄放入temp中
{
temp[k]=L->r[j];
j++;
k++;
}
else//將第2段中的記錄放入temp中
{
temp[k]=L->r[i];
k++;
i++;
}
}
while(i<=m)//將第1段餘下的部分復制到temp
{
temp[k]=L->r[i];
k++;
i++;
}
while(j<=high)//將第2段餘下的部分復制到temp
{
temp[k]=L->r[j];
k++;
j++;
}
for(k=0,i=low;i<=high;i++,k++)//將temp復制回L中
{
L->r[i]=temp[k];
}
}

void MSort(qSqList L,int low,int high)//二路歸並排序
{
int m;
if (low<high)
{
m=(low+high)/2;
MSort(L,low,m);
MSort(L,m+1,high);
Merge(L,low,m,high);
}
}

void Merging(qSqList L)//歸並排序
{
MSort(L,1,L->length);
Print2(L);
}

void Radixsort(qSqList L)//基數排序
{
int g,i,j,k,d=2;
struct node2 *p,*s,*t,*head[10],*tail[10];//定義各鏈隊的首尾指針
for(i=1;i<=L->length;i++) //建立鏈表
{
s = (struct node2*)malloc(sizeof(struct node2));
s->r.key = L->r[i].key;
s->r.num= L->r[i].num;
if(i==1)
{
t = s;
p = s;
g++;}
else
{
t->next = s;
t = s;
g++;
}
t->next = NULL;
}
d=1;
for(i=1;i<6;i++)
{
for(j=0;j<10;j++)
{head[j] = tail[j] = NULL;} //初始化各鏈隊首、尾指針
while(p!=NULL)//對於原鏈表中的每個結點循環
{
k = p->r.key/d;
k = k%10;
if(head[k]==NULL)//進行分配
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p = p->next;//取下一個待排序的元素
}
p=NULL;
for(j=0;j<10;j++)//對每一個鏈隊循環
{
if(head[j]!=NULL)//進行搜集
{
if(p == NULL)
{
p = head[j];
t = tail[j];
}
else
{
t->next=head[j];
t = tail[j];
}
}
}
t->next=NULL;//最後一個結點的next置為空
d=d*10;
}
i=1;
while(p!=NULL)
{
L->r[i] = p->r;
i++;
p=p->next;}
Print2(L);
}

char chmenu()//對排序方法進行選擇
{
char ch;
printf("\n\t請選擇排序方法:"
"\n\t*************"
"\n\t1.Shell排序"
"\n\t2.Quick排序"
"\n\t3.錦標賽排序"
"\n\t4.堆排序"
"\n\t5.歸並排序"
"\n\t6.基排序"
"\n\t7.結束"
"\n\t*************");
do{
printf("\n\tplease choose (1-7):");
getchar();
ch=getchar();
}while(!(ch>'0'&&ch<'8'));
return(ch);
}

void main()
{
int a=1;
FILE *fp;
char ch,filename[N];
qSqList L;
while(a)
{
printf("\n\t請輸入讀入文件名:");//輸入要讀入的文件名
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("cannot open the file\n");
exit(0);
}
L=creat(filename);
while(1)
{
if((ch=chmenu())=='7')
break;
switch(ch)
{
case'1':{shifttimes=comparetimes=0;shell(L);}break;
case'2':{shifttimes=comparetimes=0;Quick(L);}break;
case'3':{shifttimes=comparetimes=0;TourSort(L,L->length);}break;
case'4':{shifttimes=comparetimes=0;Heap(L);}break;
case'5':{shifttimes=comparetimes=0;Merging(L);}break;
case'6':{shifttimes=comparetimes=0;Radixsort(L);}break;
}
}
printf("\n\t***************"
"\n\t1.繼續讀入文件"
"\n\t0.結束"
"\n\t***************");
do{
printf("\n\tplease choose (0-1):");
getchar();
scanf("%d",&a);
}while(!(a==1||a==0));

}
}

⑻ 數據結構堆排序演算法

初始堆： 49 a[1] 38 65 a[2] a[3] 97 76 13 27 a[4] a[5] a[6] a[7] 50 a[8]procere heap(nn,ii:integer); var x,i,j:integer; begin i:=ii;x:=a[ii];j:=2*ii; while j<=nn do begin if (j<nn) and(a[j]<a[j+1] then j:=j+1; if x<a[j] then begin a[i]:=a[j];i:=j;j:=2*i;end else j:=nn+1; end; end;主程序：for i:=n div 2 downto 1 do heap(n,i); /heap相當於搜索頂點i的所有子節點，找出最大的和它替換for i:=n downto 2 do begin temp:=a[1];a[1]:=a[i];a[i]:=temp; /將當前最大的數（放在a[1]）和第i個數交換，保證從後面往前數是 heap(i-1,1); 從大到小，則程序完成時，數組a從前往後是從小到大 end; 至於過程自己用筆算，很快就會明白，不明白算了就明白。

⑼ 基數排序怎麼排

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:005px0;padding:5px;border:1pxsolid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc100px);background-image:linear-gradient(#fff,#e5eecc100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1pxsolid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1pxsolid#d4d4d4;width:98%}div.code{width:98%;border:1pxsolid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.codediv{font-size:110%}div.codediv,div.codep,div.example_codep{font-family:"couriernew"}pre{margin:15pxauto;font:12px/20pxMenlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1pxsolid#ddd;border-left-width:4px;padding:10px15px}排序演算法是《數據結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。以下是基數排序演算法：
基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。
1.基數排序vs計數排序vs桶排序基數排序有兩種方法：
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶；計數排序：每個桶只存儲單一鍵值；桶排序：每個桶存儲一定范圍的數值；2.LSD基數排序動圖演示
代碼實現javaScript實例//LSDRadixSortvarcounter=[];functionradixSort(arr,maxDigit){varmod=10;vardev=1;for(vari=0;i<maxDigit;i++,dev*=10,mod*=10){for(varj=0;j<arr.length;j++){varbucket=parseInt((arr[j]%mod)/dev);if(counter[bucket]==null){counter[bucket]=[];}counter[bucket].push(arr[j]);}varpos=0;for(varj=0;j<counter.length;j++){varvalue=null;if(counter[j]!=null){while((value=counter[j].shift())!=null){arr[pos++]=value;}}}}returnarr;}Java實例/***基數排序*考慮負數的情況還可以參考：https://code.i-harness.com/zh-CN/q/e98fa9*/{@Overridepublicint[]sort(int[]sourceArray)throwsException{//對arr進行拷貝，不改變參數內容int[]arr=Arrays.Of(sourceArray,sourceArray.length);intmaxDigit=getMaxDigit(arr);returnradixSort(arr,maxDigit);}/***獲取最高位數*/privateintgetMaxDigit(int[]arr){intmaxValue=getMaxValue(arr);returngetNumLenght(maxValue);}privateintgetMaxValue(int[]arr){intmaxValue=arr[0];for(intvalue:arr){if(maxValue<value){maxValue=value;}}returnmaxValue;}protectedintgetNumLenght(longnum){if(num==0){return1;}intlenght=0;for(longtemp=num;temp!=0;temp/=10){lenght++;}returnlenght;}privateint[]radixSort(int[]arr,intmaxDigit){intmod=10;intdev=1;for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){//考慮負數的情況，這里擴展一倍隊列數，其中[0-9]對應負數，[10-19]對應正數(bucket+10)int[][]counter=newint[mod*2][0];for(intj=0;j<arr.length;j++){intbucket=((arr[j]%mod)/dev)+mod;counter[bucket]=arrayAppend(counter[bucket],arr[j]);}intpos=0;for(int[]bucket:counter){for(intvalue:bucket){arr[pos++]=value;}}}returnarr;}/***自動擴容，並保存數據**@paramarr*@paramvalue*/privateint[]arrayAppend(int[]arr,intvalue){arr=Arrays.Of(arr,arr.length+1);arr[arr.length-1]=value;returnarr;}}PHP實例functionradixSort($arr,$maxDigit=null){if($maxDigit===null){$maxDigit=max($arr);}$counter=[];for($i=0;$i<$maxDigit;$i++){for($j=0;$j<count($arr);$j++){preg_match_all('/d/',(string)$arr[$j],$matches);$numArr=$matches[0];$lenTmp=count($numArr);$bucket=array_key_exists($lenTmp-$i-1,$numArr)?intval($numArr[$lenTmp-$i-1]):0;if(!array_key_exists($bucket,$counter)){$counter[$bucket]=[];}$counter[$bucket][]=$arr[$j];}$pos=0;for($j=0;$j<count($counter);$j++){$value=null;if($counter[$j]!==null){while(($value=array_shift($counter[$j]))!==null){$arr[$pos++]=$value;}}}}return$arr;}C++實例intmaxbit(intdata[],intn)//輔助函數，求數據的最大位數{intmaxData=data[0];///<最大數///先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優化點。for(inti=1;i<n;++i){if(maxData<data[i])maxData=data[i];}intd=1;intp=10;while(maxData>=p){//p*=10;//MaybeoverflowmaxData/=10;++d;}returnd;/*intd=1;//保存最大的位數intp=10;for(inti=0;i<n;++i){while(data[i]>=p){p*=10;++d;}}returnd;*/}voidradixsort(intdata[],intn)//基數排序{intd=maxbit(data,n);int*tmp=newint[n];int*count=newint[10];//計數器inti,j,k;intradix=1;for(i=1;i<=d;i++)//進行d次排序{for(j=0;j<10;j++)count[j]=0;//每次分配前清空計數器for(j=0;j<n;j++){k=(data[j]/radix)%10;//統計每個桶中的記錄數count[k]++;}for(j=1;j<10;j++)count[j]=count[j-1]+count[j];//將tmp中的位置依次分配給每個桶for(j=n-1;j>=0;j--)//將所有桶中記錄依次收集到tmp中{k=(data[j]/radix)%10;tmp[count[k]-1]=data[j];count[k]--;}for(j=0;j<n;j++)//將臨時數組的內容復制到data中data[j]=tmp[j];radix=radix*10;}delete[]tmp;delete[]count;}C實例#include<stdio.h>#defineMAX20//#defineSHOWPASS#defineBASE10voidprint(int*a,intn){inti;for(i=0;i<n;i++){printf("%d ",a[i]);}}voidradixsort(int*a,intn){inti,b[MAX],m=a[0],exp=1;for(i=1;i<n;i++){if(a[i]>m){m=a[i];}}while(m/exp>0){intbucket[BASE]={0};for(i=0;i<n;i++){bucket[(a[i]/exp)%BASE]++;}for(i=1;i<BASE;i++){bucket[i]+=bucket[i-1];}for(i=n-1;i>=0;i--){b[--bucket[(a[i]/exp)%BASE]]=a[i];}for(i=0;i<n;i++){a[i]=b[i];}exp*=BASE;#ifdefSHOWPASSprintf("
PASS:");print(a,n);#endif}}intmain(){intarr[MAX];inti,n;printf("Entertotalelements(n<=%d):",MAX);scanf("%d",&n);n=n<MAX?n:MAX;printf("Enter%dElements:",n);for(i=0;i<n;i++){scanf("%d",&arr[i]);}printf("
ARRAY:");print(&arr[0],n);radixsort(&arr[0],n);printf("
SORTED:");print(&arr[0],n);printf("
");return0;}Lua實例--獲取表中位數localmaxBit=function(tt)localweight=10;--十_制localbit=1;fork,vinpairs(tt)dowhilev>=weightdoweight=weight*10;bit=bit+1;endendreturnbit;end--基數排序localradixSort=function(tt)localmaxbit=maxBit(tt);localbucket={};localtemp={};localradix=1;fori=1,maxbitdoforj=1,10dobucket[j]=0;---清空桶endfork,vinpairs(tt)dolocalremainder=math.floor((v/radix))%10+1;bucket[remainder]=bucket[remainder]+1;--每_桶_量自_增加1endforj=2,10dobucket[j]=bucket[j-1]+bucket[j];--每個桶的數量=以前桶數量和+自個數量end--按照桶的位置，排序--這個是桶式排序，必須使用倒序，因為排序方法是從小到大，順序下來，會出現大的在小的上面清空。fork=#tt,1,-1dolocalremainder=math.floor((tt[k]/radix))%10+1;temp[bucket[remainder]]=tt[k];bucket[remainder]=bucket[remainder]-1;endfork,vinpairs(temp)dott[k]=v;endradix=radix*10;endend;參考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md
https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
以下是熱心網友對基數排序演算法的補充，僅供參考：熱心網友提供的補充1：
java代碼里，mod每次循環會乘10，但counter的行數是不需要變的，能包含[-9,9]就可以了。


for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){
//考慮負數的情況，這里擴展一倍隊列數，其中[0-9]對應負數，[10-19]對應正數(bucket+10)
int[][]counter=newint[20][0];

for(intj=0;j<arr.length;j++){
intbucket=((arr[j]%mod)/dev)+10;
counter[bucket]=arrayAppend(counter[bucket],arr[j]);
}

intpos=0;
for(int[]bucket:counter){
for(intvalue:bucket){
arr[pos++]=value;
}
}
}熱心網友提供的補充2：
艾孜爾江補充使用C#基數排序演算法如下:


///基數排序
staticvoidRadixSort(List<int>list)
{
intmaxValue=list.Max();//列表內部方法拿過來用用（在Linq中）
intit=0;//需要幾趟
//maxvalue9-199-2999-3
//10^0<=910^1>9it=1
//10^0<9910^1<9910^2>99it=2
while(Math.Pow(10,it)<=maxValue)
{
List<List<int>>buckets=newList<List<int>>(10);//分10個桶對應0-9
for(inti=0;i<10;i++)
{
buckets.Add(newList<int>());
}//列表初始化大小
for(inti=0;i<list.Count;i++)//入桶
{
//989it=0989/10^it=989989%10=9;
intdigit=(int)((list[i])/(Math.Pow(10,it))%10);//得到對應桶
buckets[digit].Add(list[i]);
}//全部入桶
list.Clear();//依次取出來
for(inti=0;i<buckets.Count;i++)
{