七李命、排序算法
1. 插入排序
把數(shù)據(jù)分成兩部分,前面是有序的(最初只有一個(gè)數(shù)據(jù))箫老,依次將后面無序部分的數(shù)據(jù)插入到前面部分封字,逐漸擴(kuò)大有序部分,直至無序部分的數(shù)據(jù)全部插入到有序部分。
-
直接插入排序:
將待插數(shù)據(jù)逐一與有序部分的數(shù)據(jù)作比較以確定插入位置周叮。 -
折半插入排序:
先找出有序部分位于中間的關(guān)鍵字辩撑,與待插數(shù)據(jù)做比較,每比較一次仿耽,就可將有序部分的一半數(shù)據(jù)排除而不需比較合冀,在數(shù)據(jù)量大時(shí)效率很高。 -
二路插入排序:
先找出有序部分位于數(shù)據(jù)中間的關(guān)鍵字项贺,與待插數(shù)據(jù)做比較君躺,如果插在前半部分,則把前面的數(shù)據(jù)向前移(一路)开缎,反之棕叫,把后面的數(shù)據(jù)向后移(另一路),這樣可以減少移動(dòng)次數(shù)(移動(dòng)的數(shù)據(jù)少于有序部分的二分之一)奕删,但需要一個(gè)額外的數(shù)組俺泣。
實(shí)現(xiàn):
//插入排序類
template<typename D>class InsSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的插入排序類
public:
void InsertSort()
{//直接插入排序
int i, j;
for(i = 2; i <= length; i++)
if LT(elem[i].key, elem[i-1].key) //小于
{
elem[0] = elem[i]; //用 elem[0] 存入
for(j = i-1; LT(elem[0].key, elem[j].key); j--)
elem[j + 1] = elem[j];
elem[j + 1] = elem[0];
}
}
void BInsertSort()
{//折半插入排序
int i, j, m, low, high;
for(i = 2; i <= length; i++)
if LT(elem[i].key, elem[i-1].key)
{
elem[0] = elem[i];
low = 1;
high = i - 1;
while(low <= high)
{
m = (low + high) / 2;
if LT(elem[0].key, elem[m].key)
high = m - 1;
else
low = m + 1;
}
for(j = i - 1; j >= high + 1; j--)
elem[j + 1] = elem[j];
elem[high + 1] = elem[0];
}
}
void P2_InsertSort()
{//二路插入排序
int i, j, first, final, mid;
D *d;
d = new D[length];
d[0] = elem[1]; //設(shè)第一個(gè)數(shù)據(jù)為 d 中有序的數(shù)據(jù)(存在 [0])
first = final = 0; //first和final分別指示d中有序數(shù)據(jù)的第一個(gè)位置和最后一個(gè)位置
for(i = 2; i <= length; i++)
{
if (first > final)
j = length; //j 是調(diào)整系數(shù)
else
j = 0;
mid = (first + final + j) / 2 % length;
if (elem[i].key < d[mid].key)
{
j = first;
first = (first - 1 + length) % length;
while(elem[i].key > d[j].key)
{
d[(j - 1 + length) % length] = d[j];
j = (j + 1) % length;
}
d[(j - 1 + length) % length] = elem[i];
}
else
{
j = final++;
while(elem[i].key < d[j].key)
{
d[(j + 1) % length] = d[j];
j = (j - 1 + length) % length;
}
d[(j + 1) % length] = elem[i];
}
}
for(i = 1; i <= length; i++)
elem[i] = d[(first + i - 1) % length];
delete[] d;
}
};
2. 冒泡排序
冒泡排序算法是從前到后逐一比較相鄰的兩個(gè)數(shù)據(jù),將小值數(shù)據(jù)交換到前面完残。一趟排序后伏钠,最大值的數(shù)據(jù)即排到最后。如果一趟排序中沒有數(shù)據(jù)交換谨设,說明所有數(shù)據(jù)都已有序熟掂,退出排序過程。
實(shí)現(xiàn):
//冒泡排序類
template<typename D>class BubSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的冒泡排序類
public:
void BubbleSort()
{//冒泡排序
int i, j;
bool change;
for(i = length, change = true; i > 1 && change; --i)
{
change = false;
for(j = 1; j < i; ++j)
if LT(elem[j+1].key, elem[j].key)
{
swap(elem[j], elem[j+1]);
change = true;
}
}
}
};
兩種優(yōu)化思路:
- 優(yōu)化外層循環(huán):判斷上一趟排序是否發(fā)生交換扎拣,未交換則已有序
- 優(yōu)化內(nèi)層循環(huán):記住最后一次交換發(fā)生的位置 lastExchange 赴肚,該位置之后的相鄰記錄均已有序
推薦閱讀:
冒泡排序算法及其兩種優(yōu)化
3. 簡單選擇排序
簡單選擇排序算法是在一趟排序中找出關(guān)鍵字最小的數(shù)據(jù),并將它交換到正確位置二蓝。
實(shí)現(xiàn):
//簡單選擇排序類
template<typename D>class SelSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的簡單選擇排序類
private:
int SelectMinKey(int i)
{//返回在 [i ~ length] 中 key 最小的數(shù)據(jù)的序號(hào)
int j, k = i;
KeyType min = elem[i].key;
for(j = i + 1; j <= length; j++)
if (elem[j].key < min)
{
k = j;
min = elem[j].key;
}
return k;
}
public:
void SelectSort()
{//簡單選擇排序
int i, j;
for(i = 1; i < length; i++)
{
j = SelectMinKey(i);
if (i != j)
swap(elem[i], elem[j]);
}
}
};
4. 希爾排序
希爾排序算法是把數(shù)據(jù)等間隔分成若干組誉券。這樣分組的好處是:數(shù)據(jù)在兩兩交換時(shí),不是與相鄰的數(shù)據(jù)交換刊愚,而是與較遠(yuǎn)處的數(shù)據(jù)交換横朋。對(duì)于離正確位置很遠(yuǎn)的數(shù)據(jù),可以減少交換次數(shù)就能到達(dá)正確位置百拓。但這樣分組并不能保證完全有序,所以希爾排序要進(jìn)行幾次晰甚,逐漸減小兩相鄰數(shù)據(jù)的間隔衙传,最后一次排序,所有數(shù)據(jù)在一組中厕九,兩相鄰數(shù)據(jù)沒有間隔蓖捶。由于希爾排序在交換時(shí)有跳躍,所以是一種不穩(wěn)定排序扁远。
實(shí)現(xiàn):
//希爾排序類
template<typename D>class SheSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的希爾排序類
private:
int n; //增量序列長度
int *dt; //增量序列數(shù)組指針
void ShellInsert(int dk)
{//希爾插入排序俊鱼,前后數(shù)據(jù)位置增量是 dk
for(int i = dk + 1; i <= length; i++)
if LT(elem[i].key, elem[i - dk].key)
{
elem[0] = elem[i];
for(int j = i - dk; j > 0 && LT(elem[0].key, elem[j].key); j -= dk)
elem[j + dk] = elem[j];
elem[j + dk] = elem[0];
}
}
public:
SheSort(int* DT, int N)
{//構(gòu)造函數(shù)
n = N;
dt = new int[N];
for(int i = 0; i < N; i++)
dt[i] = DT[i];
assert(dt[n-1] == 1); //最后一個(gè)增量值必須等于 1 刻像,否則退出
}
~SheSort()
{//析構(gòu)函數(shù)
delete[] dt;
}
void ShellSort()
{//希爾排序
for(int k = 0; k < n; k++)
{
ShellInsert(dt[k]);
cout << endl << "dt[" << k <<"] = " << dt[k] << ",第" << k+1
<< "趟排序結(jié)果(僅輸出關(guān)鍵字)" ;
for(int i = 1; i <= length; i++)
cout << elem[i].key << " " ;
}
}
};
5. 快速排序
快速排序算法是在無序數(shù)據(jù)中任選一個(gè)作為樞軸并闲,將樞軸數(shù)據(jù)放在臨時(shí)單元 [0] 中细睡, low 和 high 指示邊界。凡是比樞軸數(shù)據(jù)小的放在 low 的左邊帝火,low 向右移溜徙;比樞軸數(shù)據(jù)大的放在 high 的右邊, high 向左移犀填。low 和 high 重合之處蠢壹,將樞軸放入。此時(shí)九巡,樞軸左邊元素都不大于樞軸的图贸,樞軸右邊元素的數(shù)據(jù)都不小于樞軸的。樞軸數(shù)據(jù)已到正確位置冕广。遞歸地對(duì)樞軸左右兩部分?jǐn)?shù)據(jù)繼續(xù)進(jìn)行快速排序疏日,遞歸到只有一個(gè)數(shù)據(jù)時(shí)退出〖岩ぃ快速排序也是一種 “不穩(wěn)定排序” 制恍。
實(shí)現(xiàn):
//快速排序類
template<typename D>class QkSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的快速排序類
private:
int Partition(int low, int high)
{//以 elem[low] 的關(guān)鍵字作為樞軸,進(jìn)行快速排序過程神凑,返回樞軸所在位置
int i = low, j = high;
elem[0] = elem[low];
while(low < high)
{//從表的兩端交替掃描
while(low < high && elem[high].key >= elem[0].key)
--high;
elem[low] = elem[high];
while(low < high && elem[low].key <= elem[0].key)
++low;
elem[high] = elem[low];
}
elem[low] = elem[0];
return low;
}
void QSort(int low, int high)
{//快速排序
if (low < high)
{
int pivotloc = Partition(low, high);
QSort(low, pivotloc - 1);
QSort(pivotloc + 1, high);
}
}
public:
void QuickSort()
{
QSort(1, length);
}
};
6. 堆排序
堆排序算法是把順序存儲(chǔ)的數(shù)據(jù)看成是一棵完全二叉樹净神。對(duì)于大頂堆,確保每棵子樹的根結(jié)點(diǎn)都是整個(gè)子樹中最大的溉委,這就保證了根結(jié)點(diǎn)是所有數(shù)據(jù)中的最大值鹃唯,但并不能保證所有數(shù)據(jù)有序。
外部排序往往也使用堆排序算法瓣喊。堆排序算法也可以用于構(gòu)建優(yōu)先隊(duì)列坡慌。堆排序也是一種 “不穩(wěn)定排序” 。
實(shí)現(xiàn):
//堆排序類
template<typename D>class HSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的堆排序類
private:
void HeapAdjust(int low, int high, bool flag)
{//已知 elem[low ~ high] 中數(shù)據(jù)的關(guān)鍵字除了elem[low].key之外均滿足大頂堆的定義
//調(diào)整 elem[low] 的位置藻三,使得都滿足大頂堆定義
int j;
elem[0] = elem[low];
for(j = 2 * low; j <= high; j *= 2)
{
if (flag) //大頂堆洪橘,升序
{
if (j < high && LT(elem[j].key, elem[j+1].key))
j++;
if (!LT(elem[0].key, elem[j].key))
break;
}
else //小頂堆,降序
{
if (j < high && GT(elem[j].key, elem[j+1].key))
j++;
if (!GT(elem[0].key), elem[j].key)
break;
}
elem[low] = elem[j];
low = j;
}
elem[low] = elem[0];
}
public:
void HeapSort(bool flag)
{//堆排序(flag == true : 大頂堆棵帽;flag == false : 小頂堆)
int i;
for(i = length / 2; i >= 1; i--)
HeapAdjust(i, length, flag);
for(i = length; i >= 2; i--)
{
swap(elem[1], elem[i]);
HeapAdjust(1, i-1, flag);
}
}
};
7. 二路歸并排序
二路歸并排序算法首先將所有數(shù)據(jù)分成每組一個(gè)數(shù)據(jù)的情況熄求,這時(shí)每組數(shù)據(jù)都是有序的;然后再把每兩組(二路)有序數(shù)據(jù)歸并成一組有序數(shù)據(jù)逗概,減少了有序數(shù)據(jù)的組數(shù)弟晚,增加每組數(shù)據(jù)的個(gè)數(shù); 最后把所有數(shù)據(jù)歸并到一個(gè)有序數(shù)組。歸并排序需要一個(gè)臨時(shí)數(shù)組用來存放已歸并的數(shù)據(jù)卿城。每次歸并后枚钓,再把臨時(shí)數(shù)組中的數(shù)據(jù)復(fù)制回去。
實(shí)現(xiàn):
//二路歸并排序類
template<typename D>class MerSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的二路歸并排序類
private:
D *temp;
void Merge(int low, int m, int high)
{//將 elem[low, m] 和 elem[m+1, high] 歸并為 elem[low, high]
int i = low, j = m+1, k = low, p;
for(; i <= m && j <= high; k++)
if LQ(elem[i].key, elem[j].key)
temp[k] = elem[i++];
else
temp[k] = elem[j++];
if (i <= m)
for(p = 0; p <= m-i; p++)
temp[k+p] = elem[i+p];
if (j <= high)
for(p = 0; p <= high-j; p++)
temp[k+p] = elem[j+p];
for(p = low; p <= high; p++)
elem[p] = temp[p];
}
void MSort(int low, int high)
{//將 elem[low ~ high] 歸并排序?yàn)?temp[low ~ high]
if (low < high)
{
int m = (low + high) / 2;
MSort(low, m);
MSort(m+1, high);
Merge(low, m, high);
}
}
public:
~MerSort()
{//析構(gòu)函數(shù)
if (temp != NULL)
delete[] temp;
}
void MergeSort()
{//二路歸并排序
temp = new D[length + 1];
MSort(1, length);
}
};
8. 靜態(tài)鏈表排序
兩種算法:
- Arrange() 算法:順著靜態(tài)鏈表的 next 域依次找到應(yīng)該排在位置 [i] 的數(shù)據(jù)目前所在位置 [p] 瑟押。將 elem[i] 和 elem[p] 交換搀捷,使得 elem[i] 排到正確位置。為了使靜態(tài)鏈表不斷鏈勉耀,令 elem[i].next = p 指煎,即到位置 [p] 去找原來在位置 [i] 的數(shù)據(jù)。該算法在最壞情況下(每個(gè)數(shù)據(jù)都不在正確位置)要做 length-1 次交換便斥。
- Rearrange() 算法:通過調(diào)用私有成員函數(shù) Sort() 至壤,給私有數(shù)據(jù)成員 adr[] 數(shù)組賦值。adr[i] 的值即是應(yīng)該排在位置 [i] 的數(shù)據(jù)目前所在位置枢纠。通過循環(huán)使得所有數(shù)據(jù)排到正確位置像街。
實(shí)現(xiàn):
//靜態(tài)鏈表插入排序類
template<typename D>class SLinkSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的靜態(tài)鏈表插入排序類
private:
int *adr;
void Sort()
{//求得 adr[i] 為靜態(tài)鏈表中第 i 個(gè)最小數(shù)據(jù)的序號(hào)
int i = 1, p = elem[0].next;
while(p != 0)
{
adr[i++] = p;
p = elem[p].next;
}
}
public:
SLinkSort()
{
adr = NULL;
}
~SLinkSort()
{
if (adr != NULL)
delete[] adr;
}
void MakeTableSorted()
{//使無序的靜態(tài)鏈表成為有序鏈表
int i, p, q;
elem[0].rc.key = INT_MAX;
elem[0].next = 0;
for(i = 1; i <= length; i++)
{
q = 0;
p = elem[0].next;
while LQ(elem[p].rc.key, elem[i].rc.key)
{
q = p;
p = elem[p].next;
}
elem[q].next = i;
elem[i].next = p;
}
}
void Arrange()
{//Arrange() 算法
int i, p, q;
p = elem[0].next;
for(i = 1; i < length; i++)
{
while(p < i)
p = elem[p].next;
q = elem[p].next;
if (p != i)
{
swap(elem[p], elem[i]);
elem[i].next = p;
}
p = q;
}
}
void Rearrange()
{//Rearrange() 算法
int i, j, k;
adr = new int[length+1];
Sort();
for(i = 1; i < length; i++)
if (adr[i] != i)
{
j = i;
elem[0] = elem[i];
while(adr[j] != i)
{
k = adr[j];
elem[j] = elem[k];
adr[j] = j;
j = k;
}
elem[j] = elem[0];
dar[j] = j;
}
}
};
9. 基數(shù)排序
基數(shù)排序算法采用靜態(tài)鏈表排序算法對(duì)字符串進(jìn)行按位排序。
推薦閱讀:
基數(shù)排序