標題: 數(shù)據(jù)結構-排序 [打印本頁] 作者: 51hei人人 時間: 2016-3-12 16:09 標題: 數(shù)據(jù)結構-排序 沒學數(shù)據(jù)結構之前，就知道冒泡排序呵呵！學了之后才知道排序有這么多種方法，真是不學不知道，一學嚇一跳！那我們看看都有哪些排序方法吧！
一.插入排序
1.直接插入排序
2.折半插入排序
二.交換排序
1.冒泡排序
2.快速排序
三.選擇排序
1.直接選擇排序
2.堆排序
四.歸并排序
1.歸并2個有序序列
2.歸并排序
呵呵一共四大類：7種排序方法.
可能還有其他更多的排序方法，只是還不為所知吧。先來看看第一類插入排序!
插入排序：故名思意就是把待元素一個一個插入到數(shù)組中，插入之前于前面的元素進行比較，然后決定插入的位置。
1.直接插入排序：
C語言:
typedef strcut
{ int key;
}NODE;
NODE a[Max];
#define Max 100
void disort(NODE a[],int n)
/*對存放在a[]中,長度為n的序列進行排序*/
{int i,j;
NODE temp;
for(i=1;i<n;i++)
{ temp=a;
j=i-1;
while(j>=0&&temp.key<a[j].key)
{ a[j+1]=a;
j--;
}
a[j+1]=temp;
}
}
VB:
Private Type NODE
key as long
End Type
Private Sub disort(a（） as NODE,ByVal n as long)
Dim i as long,j as long,temp as NODE
for i=1 to n-1
temp=a（i）
j=i-1
Do While((j>0 or j=0) And (temp.key<a（j）))
a（j+1)=a(j)
j=j-1
loop
a(j+1)=temp
next i
End Sub 作者: 51hei人人 時間: 2016-3-12 16:10
2.折半插入排序
折半插入排序是對直接插入排序的一個改進，當數(shù)組元素較多時候，直接插入排序的效率不高.而折半排序能減少比較的次數(shù)，從而效率。我們來看看它是怎么減少比較次數(shù)的。
1.我們設3個變量low,high,mid,low為待比較的區(qū)間的最低位，high為待比較區(qū)間的最高位,mid為[low+mid]/2區(qū)間的中間位置.
2.我們比較中間位置和待插入元素的大小,若中間元素大于待插入元素那么只可能在中間元素的左邊插入，我們令high=mid-1。若中間元素小于待插入元素，那么插入位置只可能在中間元素右邊，此時我們令low=mid+1.
3.循環(huán)執(zhí)行步驟2，直到low>high，此時high+1為插入的位置.我們再將high+1以后的元素依次后移，再將待插入的元素插入.
C:
void binsort(NODE a[],int n)
{ int low,high,mid,temp;
int i,j;
for(i=1;i<n;i++)
{ low=0;
high=i-1;
temp=a.key;
while(low<=high)
{ mid=(low+high)/2;
if(temp<mid) high=mid-1;
else low=mid+1;
}
for(j=i-1;j>=high+1;j--) a[j+1]=a[j];
a[j+1]=temp;
}
}
VB:
Private Sub binsort( a（） as NODE, n as long)
Dim low as long,high as long,mid as long,temp as long,i as long,j as long
for i=1 to n-1
low=0
high=i-1
temp=a(i）.key
Do While(low<high Or low=high)
mid=int((low+high)/2)
if temp<a（mid）.key then
high=mid-1
else
low=mid+1
end if
loop
for j=i-1 to high+1 step -1
a(j+1）=a（j）
next j
a（j+1)=temp
next i
End Sub