Ⅰ 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。
排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。
1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；
學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。
排序（sort）或分類
所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。
2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。
排序的穩定性
當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。
排序方法的分類
1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。
2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。
排序演算法分析
1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。
2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）
（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；
（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。
3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度
（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。
（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。
文件的順序存儲結構表示
#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。
按平均時間將排序分為四類：
（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；
（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；
（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；
（4）線性階(O(n))排序
如桶、箱和基數排序。
各種排序方法比較
簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。
影響排序效果的因素
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。
不同條件下，排序方法的選擇
(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。
4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。
Ⅱ 誰教我：數據結構的各種排序
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));
}
}
Ⅲ 數組的幾種排序演算法的實現
JAVA中在運用數組進行排序功能時，一般有四種方法：快速排序法、冒泡法、選擇排序法、插入排序法。
快速排序法主要是運用了Arrays中的一個方法Arrays.sort（）實現。
冒泡法是運用遍歷數組進行比較，通過不斷的比較將最小值或者最大值一個一個的遍歷出來。
選擇排序法是將數組的第一個數據作為最大或者最小的值，然後通過比較循環，輸出有序的數組。
插入排序是選擇一個數組中的數據，通過不斷的插入比較最後進行排序。下面我就將他們的實現方法一一詳解供大家參考。
<1>利用Arrays帶有的排序方法快速排序
public class Test2{ public static void main(String[] args){ int[] a={5,4,2,4,9,1}; Arrays.sort(a); //進行排序 for(int i: a){ System.out.print(i); } } }
<2>冒泡排序演算法
public static int[] bubbleSort(int[] args){//冒泡排序演算法 for(int i=0;i<args.length-1;i++){ for(int j=i+1;j<args.length;j++){ if (args[i]>args[j]){ int temp=args[i]; args[i]=args[j]; args[j]=temp; } } } return args; }
<3>選擇排序演算法
public static int[] selectSort(int[] args){//選擇排序演算法 for (int i=0;i<args.length-1 ;i++ ){ int min=i; for (int j=i+1;j<args.length ;j++ ){ if (args[min]>args[j]){ min=j; } } if (min!=i){ int temp=args[i]; args[i]=args[min]; args[min]=temp; } } return args; }
<4>插入排序演算法
public static int[] insertSort(int[] args){//插入排序演算法 for(int i=1;i<args.length;i++){ for(int j=i;j>0;j--){ if (args[j]<args[j-1]){ int temp=args[j-1]; args[j-1]=args[j]; args[j]=temp; }else break; } } return args; }
Ⅳ 數據排序的一般方法有什麼
數據排序方法
好的排序方法可以有效提高排序速度，提高排序效果。
在計算機領域主要使用數據排序方法根據佔用內存的方式不同分為2大類：內部排序方法與外部排序方法。
內部排序方法
若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。
內排序的方法有許多種，按所用策略不同，可歸納為五類：插入排序、選擇排序、交換排序、歸並排序和基數排序。
其中，插入排序主要包括直接插入排序和希爾排序兩種；選擇排序主要包括直接選擇排序和堆排序；交換排序主要包括氣（冒）泡排序和快速排序。
外部排序方法
外部排序基本上由兩個相互獨立的階段組成。首先，按可用內存大小，將外存上含n個記錄的文件分成若干長度為k的子文件或段(segment)，依次讀入內存並利用有效的內部排序方法對它們進行排序，並將排序後得到的有序子文件重新寫入外存。通常稱這些有序子文件為歸並段或順串；然後，對這些歸並段進行逐趟歸並，使歸並段(有序子文件)逐漸由小到大，直至得到整個有序文件為止。
Ⅳ JAVA中有哪幾種常用的排序方法
最主要的是冒泡排序、選擇排序、插入排序以及快速排序
1、冒泡排序
冒泡排序是一個比較簡單的排序方法。在待排序的數列基本有序的情況下排序速度較快。若要排序的數有n個，則需要n-1輪排序，第j輪排序中，從第一個數開始，相鄰兩數比較，若不符合所要求的順序，則交換兩者的位置；直到第n+1-j個數為止，第一個數與第二個數比較，第二個數與第三個數比較，......，第n-j個與第n+1-j個比較，共比較n-1次。此時第n+1-j個位置上的數已經按要求排好，所以不參加以後的比較和交換操作。
例如：第一輪排序：第一個數與第二個數進行比較，若不符合要求的順序，則交換兩者的位置，否則繼續進行二個數與第三個數比較......。直到完成第n-1個數與第n個數的比較。此時第n個位置上的數已經按要求排好，它不參與以後的比較和交換操作；第二輪排序：第一個數與第二個數進行比較，......直到完成第n-2個數與第n-1個數的比較；......第n-1輪排序：第一個數與第二個數進行比較，若符合所要求的順序，則結束冒泡法排序；若不符合要求的順序，則交換兩者的位置，然後結束冒泡法排序。
共n-1輪排序處理，第j輪進行n-j次比較和至多n-j次交換。
從以上排序過程可以看出，較大的數像氣泡一樣向上冒，而較小的數往下沉，故稱冒泡法。
public void bubbleSort(int a[])
{
int n = a.length;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
2、選擇排序
選擇法的原理是先將第一個數與後面的每一個數依次比較,不斷將將小的賦給第一個數,從而找出最小的,然後第二個數與後面的每一個數依次比較,從而找出第二小的,然後第三個數與後面的每一個數依次比較,從而找出第三小的.....直到找到最後一個數。
public void sort(int x[])
{
int n=x.length;
int k,t;
for(int i=0;i<n-1;i++)
{
k=i;
for(int j=i+1;j=n;j++)
{
if(x[j]>x[k])k=j;
if(k!=i)
{
t=x[i];
x[i]=x[k];
x[k]=t;
}
}
}
}
3、插入排序
插入排序的原理是對數組中的第i個元素，認為它前面的i-1個已經排序好，然後將它插入到前面的i-1個元素中。插入排序對少量元素的排序較為有效.
public void sort(int obj[])
{
for(int j=1;j<obj.length;j++)
{
int key=obj[j];
int i=j-1;
while(i>=0&&obj[i]>key)
{
obj[i+1]=obj[i];
i--;
}
obj[i+1]=key;
}
}
4、快速排序
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一次排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此大道整個數據變成有序序列。
public void quickSort(int obj[],int low,int high)
{
int i=low;
int j=high;
int keyValue=obj[i];
while(i<j)
{
int temp=0;
while(i<j&&obj[j]>=keyValue)
{
j=j-1;
}
temp=obj[j];
obj[j]=obj[i];
obj[i]=temp;
while(i<j&&obj[i]<=keyValue)
{
i=i+1;
}
temp=obj[j];
obj[j]=ojb[i];
obj[i]=temp;
}
obj[i]=keyValue;
if(low<i-1)
{
quickSort(obj,low,i-1);
}
if(high>i+1)
{
quickSort(obj,i+1,high);
}
}
Ⅵ 數據結構中排序方法有多少種
1、插入排序（直接插入排序和希爾排序）
2、選擇排序（直接選擇排序和堆排序）
3、交換排序（冒泡排序和快速排序）
4、歸並排序
5、基數排序
直接插入排序：逐個將後一個數加到前面的排好的序中。在直接插入排序過程中，對其中一個記錄的插入排序稱為一次排序；直接插入排序是從第二個記錄開始進行的，因此，長度為n的記錄序列需要進行n-1次排序才能完成整個序列的排序。時間復雜度為O(n2)。
希爾排序：希爾排序又稱縮小增量排序，增量di可以有各種不同的取法，但最後一次排序時的增量必須為1，最簡單可取di+1=di/2（取小）。時間復雜度為O(n(log2n)2)。
直接選擇排序
說明：每次將後面的最小的找出來插入前面的已排好的序中。同理，具有n個記錄的序列要做n-1次排序。
時間復雜度為O(n2)。
冒泡排序：兩個兩個比較，將大的往後移。通過第一次冒泡排序，使得待排序的n個記錄中關鍵字最大的記錄排到了序列的最後一個位置上。然後對序列中前n-1個記錄進行第二次冒泡排序。。。對於n個記錄的序列，共需進行n次冒泡排序。時間復雜度為O(n2)。
快速排序：又叫分區交換排序，是對冒泡排序方法的一種改進。時間復雜度為O(nlog2n)。
歸並排序：將兩個或兩個以上的有序數據序列合並成一個有序數據序列的過程。時間復雜度為O(nlog2n)。
Ⅶ 排序有幾種方法
一. 冒泡排序
冒泡排序是是一種簡單的排序演算法。它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把它們交換過來。遍歷數列的工作是重復的進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端
1.冒泡排序演算法的運作如下：
（1）比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個
（2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素還是最大的數
（3）針對所有的元素重復以上的步驟，除了最後一個
二. 選擇排序
選擇排序是一種簡單直觀的排序演算法。他的工作原理如下：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置（末尾位置），然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢
選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，他們當中至少有一個將被移到最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動 元素的排序方法中，選擇排序屬於非常好的一種
三. 插入排序
插入排序是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在從後向前掃描的過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間
四. 快速排序
快速排序，又稱劃分交換排序。通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都要小，然後再按此方法對兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列
五 希爾排序過程
希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
六. 歸並排序
歸並排序是採用分治法（把復雜問題分解為相對簡單的子問題，分別求解，最後通過組合起子問題的解的方式得到原問題的解）的一個非常典型的應用。歸並排序的思想就是先遞歸分解數組，再合並數組
將數組分解最小之後，然後合並兩個有序數組，基本思路是比較兩個數組的最前面的數，水小九先取誰，取了後相應的指針就往後移一位。然後比較，直至一個數組為空，最後把另一個數組的剩餘部分復制過來即可
Ⅷ Excel表格排序的幾種方法
方法一：日期按時間排序
進入到操作界面，如圖所示，首先選中需要排序的單元格區域，在選中開始菜單上的“數據”，至“排序”選項卡，在彈出的“自定義排序次序”中找到日期的排序方式即可，然後在點擊確定即可完成操作，如圖所示：
相關教程：excel輸入日期
現在我們來預覽排序完成後的效果吧。如圖所示：
方法二：數據按住數字大小排序
進入到操作幾面，小編隨便輸入幾個數字，如圖所示：
選中需要排序的單元格，在選中開始菜單上的“數據”，至“排序”選項卡，然後在點擊“選項”命令，彈出“排序選項”，然後直接點擊“按列排序”方式，即可這樣單元格裡面的數字就是按列小到大的排序了。如圖所示：
方法三：名稱按字母來排序
小編就隨便輸入幾個名字。同樣按照上面的方式，進入到排序選項窗口，如圖所示：
然後在“排序選項”上選擇“按字母排序”即可完成操作了，如圖所示：
你可以還想了解：excel中如何拆分和凍結單元格
方法四：當然，這幾種方式還是比較簡單的，常用的幾種方法。有的時候需要按別的方式排序的話，就可以再“自定義選項”中添加排序方式即可，如圖所示：
以上就是Excel表格排序的幾種方法。所有的排序要先選擇要排序的內容，要包括每列表頭，然後點“數據
-
排序
”在對話框里選擇“主關鍵字”、或次關鍵字，再選擇排序順序，排序方式按從大到小或從小到大。