算法:核心思想是掃描數據清單,尋找出現亂序的兩個相鄰的項目。當找到這兩個項目後,交換項目的位置然後繼續掃描。重復上面的操作直到所有的項目都按順序排好
bubblesort(struct rec r[],int n)
{
int i,j;
struct rec w;
unsigned long int compare=0,move=0;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
{
if(r[j].key<r[j-1].key)
{
w=r[j];
r[j]=r[j-1];
r[j-1]=w;
move=move+3;
}
compare++;
}
printf("
BubbleSort compare= %ld,move= %ld
",compare,move);
}
2、直接插入排序
算法:經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置,使得L[1..i]又是排好序的序列。要達到這個目的,我們可以用順序比較的方法。首先比較L[i]和L[i-1],如果L[i-1]≤ L[i],則L[1..i]已排好序,第i遍處理就結束了;否則交換L[i]與L[i-1]的位置,繼續比較L[i-1]和L[i-2],直到找到某壹個位置j(1≤j≤i-1),使得L[j] ≤L[j+1]時為止
insertsort(struct rec r[],int n)
{
int i,j;
unsigned long int compare=0,move=0;
for(i=2;i<=n;i++)
{compare++;
r[0]=r[i];
move++;
j=i-1;
while(r[0].key {r[j+1]=r[j];
j--;
move++;
++compare;}
r[j+1]=r[0];
move++;
}
printf("
InsertSort compare= %ld,move= %ld
",compare,move);
}
3、簡單選擇排序
算法:首先找到數據清單中的最小的數據,然後將這個數據同第壹個數據交換位置;接下來找第二小的數據,再將其同第二個數據交換位置,以此類推。
selectsort(struct rec r[],int n)
{
unsigned long int compare=0,move=0;
int i,j,k;
struct rec w;
for(i=1;i<=n-1;i++)
{ k=i;
for(j=i+1;j<=n;j++)
{ if(r[j].key>r[k].key) {k=j; compare++; }
w=r[i];
r[i]=r[k];
r[k]=w;
move=move+3;
}
}
printf("
SelectSort compare= %ld,move= %ld
",compare,move);
}
4、快速排序
算法:首先檢查數據列表中的數據數,如果小於兩個,則直接退出程序。如果有超過兩個以上的數據,就選擇壹個分割點將數據分成兩個部分,小於分割點的數據放在壹組,其余的放在另壹組,然後分別對兩組數據排序。
通常分割點的數據是隨機選取的。這樣無論妳的數據是否已被排列過,妳所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不多
q(struct rec r[],int s,int t)
{
int i=s,j=t;
if(s<t)
{
r[0]=r[s]; ++a; c++;
do{
while(j>i&&r[j].key>=r[0].key)
{j--;
++a; }
if(i<j)
{ r[i]=r[j];
i++;
c++; }
while(i<j&&r[i].key<=r[0].key)
{i++;
++a; }
if(i<j)
{ r[j]=r[i];
j--;
c++; }
} while(i<j);
r[i]=r[0];
c++;
q(r,s,j-1);
q(r,j+1,t);
}
}
5. 堆排序
(1) 基本思想:
堆排序是壹樹形選擇排序,在排序過程中,將R[1..N]看成是壹顆完全二叉樹的順序存儲結構,利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
(2) . 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆,當且僅當該序列滿足特性:
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
sift(struct rec r[],int l,int m)
{
int i,j;
struct rec w;
i=l; j=2*i;
w=r[i];
while(j<=m)
{
if(j<m&&r[j].key<r[j+1].key) { j++;
}
if(w.key<r[j].key)
{
r[i]=r[j];
i=j;
j=2*i;
}
else j=m+1;
}
r[i]=w;
}
heapsort(struct rec r[],int n)
{
unsigned long int compare=-1,move=-1;
struct rec w;
int i;
int a;
for(i=n/2;i>=1;i--) a=sift(r,i,n);
compare++;
move++;
for(i=n;i>=2;i--)
{
w=r[i];
r[i]=r[1];
r[1]=w;
a=sift(r,1,i-1);
compare+=a;
move+=a;
}
}