|
直接插入排序的基本方法：每步將一個(gè)待排序的元素,，按其排序碼的大小,，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上去，直到元素全部插入為止,。
插入排序（insert sorting)思想：當(dāng)插入第i個(gè)元素時(shí),，前面的v[0],v[1],v[2]......v[i-1],已經(jīng)排好序了.這時(shí)用v[i]的插入碼與v[i-1],v[i-2],......排序碼進(jìn)行比較，找到插入的位置即插入v[i],原來(lái)位置上的元素從后向前依次后移,。
時(shí)間復(fù)雜度: 平均比較次數(shù)O(n2),平均移動(dòng)次數(shù) O(n2).
直接插入排序是一種穩(wěn)定的排序,。元素大部分有序時(shí)效率會(huì)更高，這時(shí)比較次數(shù)和移動(dòng)次數(shù)都會(huì)減少,。
參考代碼：
void Sort<T>::insertSort(DataList<T> &datalist, int n)
{
if ( -1 == n)
{
for (int i = 1; i < datalist.m_nCurrentSize; i++)
{
insertSort(datalist, i);
}
return;
}
Element<T> temp = datalist.m_pvector[n];
int j;
for ( j = n; j > 0; j--)
{
if (temp > datalist.m_pvector[j-1])
{
break;
}else
{
datalist.m_pvector[j] = datalist.m_pvector[j-1];
}
}
datalist.m_pvector[j] = temp;
}
二分（折半）插入（Binary insert sort)排序基本思想：設(shè)在數(shù)據(jù)表中有一個(gè)元素序列v[0],v[1],v[2]......v[n].其中v[0],v[1],v[2]......v[i-1]是已經(jīng)排好序的元素,。在插入v[i]。利用折半搜索尋找v[i]的插入位置,。
二分插入排序是一種穩(wěn)定的排序,。當(dāng)n較大時(shí)，總排序碼比較次數(shù)比直接插入排序的最差情況好得多,，但比最好情況要差,，所元素初始序列已經(jīng)按排序碼接近有序時(shí)，直接插入排序比二分插入排序比較次數(shù)少,。二分插入排序元素移動(dòng)次數(shù)與直接插入排序相同,，依賴(lài)于元素初始序列。
參考代碼：
template <class T>
void Sort<T>::binaryInsert(DataList<T> &datalist, int n)
{
if (-1 == n)
{
for (int i = 1; i < datalist.m_nCurrentSize; i++)
{
binaryInsert(datalist, i);
}
return;
}
Element<T> temp = datalist.m_pvector[n];
int left = 0, right = n - 1;
while(left <= right)
{
int middle = (left + right) / 2;
if (temp > datalist.m_pvector[middle])
{
left = middle + 1;
}else
{
right = middle - 1;
}
}
for (int j = n - 1; j >= left; j--)
{
datalist.m_pvector[j+1] = datalist.m_pvector[j];
}
datalist.m_pvector[left] = temp;
}
希爾排序（Shell sort）基本思想: 改進(jìn)的直接插入算法,。設(shè)待排序的元素序列有n個(gè)元素，首先取一整數(shù)gap（<n）作為間隔,，將全部元素分為gap個(gè)子序列,，所有距離為gap的元素放在同一序列中，在每個(gè)子序列中分別進(jìn)行直接插入排序,。然后縮小gap,，例如gap=gap/2,重復(fù)上述的子序列劃分與排序工作。開(kāi)始由于gap取直大,，每個(gè)子序列元素少,，排序速度快，待排序后期,，gap值逐漸變小,，子序列元素變多，但由于前面的工作基礎(chǔ),，大多數(shù)元素已經(jīng)有序,，所以排序速度快。
希爾排序是一種不穩(wěn)定的排序。
參考代碼：
void swap(int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}
void insertion_sort(int data[], int n, int increment)
{
int i, j;
for (i = increment; i < n; i += increment)
{
for (j = i; j >= increment && data[j] < data[j-increment]; j -= increment)
{
swap(&data[j], &data[j-increment]);
}
}
}
void shellsort(int data[], int n)
{
int i, j;
for (i = n / 2; i > 0; i /= 2)
{
for (j = 0; j < i; j++)
{
insertion_sort(data, n, i);
}
}
}
另一種參考代碼：
template <class T>
void Sort<T>::shellSort(DataList<T> &datalist, int gap /* = -1 */)
{
if (-1 == gap)
{
int gap = datalist.m_nCurrentSize / 2;
while(gap)
{
shellSort(datalist, gap);
gap = gap / 2;
}
return;
}
for (int i = gap; i < datalist.m_nCurrentSize; i++)
{
insert(datalist, i, gap);
}
}
template <class T>
void Sort<T>::insert(DataList<T> &dataList, int n, int gap)
{
for (int i = n; i >= gap; i -= gap)
{
if (dataList.m_pvector[i] < dataList.m_pvector[i-gap])
{
Element<T> temp = dataList.m_pvector[i];
dataList.m_pvector[i] = dataList.m_pvector[i-1];
dataList.m_pvector[i-1] = temp;
}
}
}
總結(jié)：以上三種排序方法的核心都是直接插入排序,，直接插入排序?qū)τ诖蟛糠钟行虻男蛄信判驎r(shí)速度快,。二分插入排序在直接插入的基本上改變了查找元素插入位置的方法，對(duì)于完全無(wú)序的序列來(lái)說(shuō),，速度會(huì)變快,，但是對(duì)開(kāi)大部分有序的序列反而會(huì)更慢，希爾排序則利用直接插入排序?qū)τ诖蟛糠钟行虻男蛄兴俣瓤斓奶攸c(diǎn),，先讓大部分序列有序,，以此來(lái)提高排序效率。
|
