算法分析
希爾排序
對于大規(guī)模亂序數(shù)組插入排序很慢，效率較低，例如最小數(shù)在數(shù)組最右，要將其挪到正確位置就要N-1次移動(dòng)。希爾排序?yàn)榱思涌焖俣群唵蔚母倪M(jìn)了插入排序，交換不相鄰的元素以對數(shù)組的局部進(jìn)行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。
步驟
1.使用元素總數(shù)量的一半5作為增量，將元素劃分為五個(gè)序列，對這五個(gè)序列分別進(jìn)行排序；
2.使用5/2=2作為增量，將元素劃分成兩個(gè)序列分別排序；
3.最后使用插入排序，將元素排序，結(jié)果為：
優(yōu)劣：
- 不需要大量的輔助空間，和歸并排序一樣容易實(shí)現(xiàn)；
- 希爾排序的時(shí)間復(fù)雜度與增量序列的選取有關(guān)，例如希爾增量時(shí)間復(fù)雜度為O(n2),而Hibbard增量的希爾排序的時(shí)間復(fù)雜度為O(n3/2)，希爾排序時(shí)間復(fù)雜度的下界是n*log2n;
- 希爾排序沒有快速排序算法快 O(n*logn)，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇;
- 希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，而快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。
快速排序（挖坑填數(shù)+分治法）
快速排序(Quick Sort)是對冒泡排序的一種改進(jìn)，基本思想是選取一個(gè)記錄作為樞軸，經(jīng)過一趟排序，將整段序列分為兩個(gè)部分，其中一部分的值都小于樞軸，另一部分都大于樞軸。然后繼續(xù)對這兩部分繼續(xù)進(jìn)行排序，從而使整個(gè)序列達(dá)到有序。
快速排序之所比較快，因?yàn)橄啾让芭菖判?，每次交換是跳躍式的。每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個(gè)數(shù)進(jìn)行了交換。因此快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是O(n2)，它的平均時(shí)間復(fù)雜度為O(n*logn)。
步驟
堆排序
作為選擇排序的改進(jìn)版，堆排序可以把每一趟元素的比較結(jié)果保存下來，以便我們在選擇最小/大元素時(shí)對已經(jīng)比較過的元素做出相應(yīng)的調(diào)整。
堆排序是一種樹形選擇排序，在排序過程中可以把元素看成是一顆完全二叉樹，每個(gè)節(jié)點(diǎn)都大（?。┯谒膬蓚€(gè)子節(jié)點(diǎn)，當(dāng)每個(gè)節(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)時(shí)，就稱為大頂堆，也叫堆有序； 當(dāng)每個(gè)節(jié)點(diǎn)都小于等于它的兩個(gè)子節(jié)點(diǎn)時(shí)，就稱為小頂堆。
算法思想(以大頂堆為例)：
1.將長度為n的待排序的數(shù)組進(jìn)行堆有序化構(gòu)造成一個(gè)大頂堆；
2.將根節(jié)點(diǎn)與尾節(jié)點(diǎn)交換并輸出此時(shí)的尾節(jié)點(diǎn)；
4.重復(fù)第二、三步直至構(gòu)造成一個(gè)有序序列。
歸并排序
歸并排序算法有兩個(gè)基本的操作，一個(gè)是分，也就是把原數(shù)組劃分成兩個(gè)子數(shù)組的過程。另一個(gè)是治，它將兩個(gè)有序數(shù)組合并成一個(gè)更大的有序數(shù)組。
它將數(shù)組平均分成兩部分: center=(left+right)/2，當(dāng)數(shù)組分得足夠小時(shí)即數(shù)組中只有一個(gè)元素時(shí)，只有一個(gè)元素的數(shù)組自然而然地就可以視為是有序的，此時(shí)就可以進(jìn)行合并操作了。因此，上面講的合并兩個(gè)有序的子數(shù)組，是從只有一個(gè)元素的兩個(gè)子數(shù)組開始合并的，合并后的元素個(gè)數(shù)：從 1->2->4->8……
由歸并排序的遞歸公式：T(n)=2T(n/2)+O(n)可知時(shí)間復(fù)雜度為O(n*logn)。
此外，歸并排序中的比較次數(shù)是所有排序中最少的。原因是，它一開始是不斷地劃分，比較只發(fā)生在合并各個(gè)有序的子數(shù)組時(shí)。
步驟
程序代碼
#pragma once
#include <time.h>
#include <iostream>
#include <fstream>
using namespace std;
#ifndef _SORT_H
#define _SORT_H
struct Record
{
int key;
};
#endif
//產(chǎn)生隨機(jī)數(shù)
Record* GenerateData(Record r[], int n)
{
srand((unsigned)time(NULL));
for(int i = 0; i < n; i++)
{
r[i].key = rand() % n; //生成n個(gè)取值為[0,n-1]的整數(shù)
}
return r;
}
//寫入文件
Record* CreateFile(Record r[], int n, const char* filename)
{
fstream fout(filename, ios::out);
if (!fout)
{
cout << "無法創(chuàng)建文件！" << endl;
exit(1);
}
else
{
for (int i = 0; i < n; i++)
{
fout << r[i].key << " ";
if ((i + 1) % 15 == 0)
fout << endl;// '\n';
}
}
fout.close();
return r;
}
//讀取文件
Record* ReadFile(int n, const char* filename)
{
fstream fin(filename, ios::in);
Record* r = new Record[n];
if (!fin)
{
cout << "無法打開文件！" << endl;
exit(1);
}
else
{
for (int i = 0; i < n; i++)
fin >> r[i].key;
}
fin.close();
return r;
}
#include <iostream>
#include <fstream>
#include "Sort.h"
#include "File.h"
#define N 10000
using namespace std;
int Menu();
void Procedure();
int Menu()
{
cout << "__________*******************************************************__________\n\n";
cout << " 1.產(chǎn)生隨機(jī)數(shù)作為待排序的數(shù)據(jù)，并將其存入磁盤文件中\(zhòng)n";
cout << " 2.執(zhí)行【希爾排序】算法，將排序結(jié)果存入文件\n";
cout << " 3.執(zhí)行【快速排序】算法，將排序結(jié)果存入文件\n";
cout << " 4.執(zhí)行【堆排序】算法， 將排序結(jié)果存入文件\n";
cout << " 5.執(zhí)行【歸并排序】算法，將排序結(jié)果存入文件\n";
cout << " 0.退出操作\n\n";
cout << "__________*******************************************************__________\n\n";
cout << "請依次輸入以上5個(gè)步驟的代號(hào): ";
Sleep(2000);
int choice;
cin >> choice;
cout << endl;
return choice;
}
void Procedure()
{
while (1)
{
int choice = Menu();
if (choice == 0)
break;
switch (choice)
{
case 1:
{
cout << "提示：本程序中待排序數(shù)據(jù)的個(gè)數(shù)為" << N << endl;
Record* r = new Record[N];
GenerateData(r, N);
Sleep(1000);
CreateFile(r, N, "隨機(jī)數(shù).txt");
Sleep(1000);
cout << "數(shù)據(jù)已存入【隨機(jī)數(shù).txt】文件\n\n";
Sleep(1500);
break;
}
case 2:
{
Record* rec = ReadFile(N, "隨機(jī)數(shù).txt");
Sleep(1000);
ShellSort(rec, N);
cout << "對待排序數(shù)據(jù)進(jìn)行希爾排序\n\n";
Sleep(1000);
CreateFile(rec, N, "希爾排序.txt");
cout << "排序的結(jié)果已存入【希爾排序.txt】文檔\n\n";
Sleep(1500);
break;
}
case 3:
{
Record *rec = ReadFile(N, "隨機(jī)數(shù).txt");
Sleep(1000);
QuickSort(rec, 0, N - 1);
cout << "對待排序數(shù)據(jù)用快速排序方法進(jìn)行排序\n\n";
Sleep(1000);
CreateFile(rec, N, "快速排序.txt");
cout << "排序的結(jié)果已存入【快速排序.txt】文檔\n\n";
Sleep(1500);
break;
}
case 4:
{
Record* rec = ReadFile(N, "隨機(jī)數(shù).txt");
Sleep(1000);
HeapSort(rec, N);
cout << "對待排序數(shù)據(jù)用堆排序方法進(jìn)行排序\n\n";
Sleep(1000);
CreateFile(rec, N, "堆排序.txt");
cout << "排序的結(jié)果已存入【堆排序.txt】文檔\n\n";
Sleep(1500);
break;
}
case 5:
{
Record* rec = ReadFile(N, "隨機(jī)數(shù).txt");
Sleep(1000);
MergeSort(rec, N);
cout << "對待排序數(shù)據(jù)用歸并排序方法進(jìn)行排序\n\n";
Sleep(1000);
CreateFile(rec, N, "歸并排序.txt");
cout << "排序的結(jié)果已存入【歸并排序】.txt文檔\n\n";
Sleep(1500);
break;
}
default:
cout << "輸入錯(cuò)誤！\n\n";
}
}
}
int main()
{
Procedure();
return 0;
}
#pragma once
#include <iostream>
#include <time.h>
#include <windows.h>
using namespace std;
#ifndef _SORT_H
#define _SORT_H
struct Record
{
int key;
};
#endif
//希爾排序算法
void ShellSort(Record r[], int n)
{
for (int d = n / 2; d >= 1; d = d / 2)
{
for (int i = d; i < n; i++)
{
Record temp = r[i];
int j;
for (j = i - d; j >= 0 && temp.key < r[j].key; j = j - d)
r[j + d] = r[j];
r[j + d] = temp;
}
}
}
//快速排序的一次劃分算法
int Partition(Record r[], int i, int j)
{
Record temp = r[i];
while (i < j)
{
while (i < j && r[j].key >= temp.key)
j--;
if (i < j)
r[i++] = r[j];
while (i < j && r[i].key <= temp.key)
i++;
if (i < j)
r[j--] = r[i];
}
r[i] = temp;
return i;
}
//快速排序算法
void QuickSort(Record r[], int i, int j)
{
if (i < j)
{
int pivot = Partition(r, i, j);
QuickSort(r, i, pivot - 1);
QuickSort(r, pivot + 1, j);
}
}
//堆排序中的篩選算法
void Sift(Record r[], int k, int m)
{
int i = k;
int j = 2 * i + 1; //置i為要篩的結(jié)點(diǎn)，j為i的左孩子
while (j <= m) //篩選還沒進(jìn)行到葉子
{
if (j < m && r[j].key < r[j + 1].key)
j++; //比較i的左右孩子，j為較大者
if (r[i].key > r[j].key)
break; //根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者
else
{
Record temp = r[i];
r[i] = r[j];
r[j] = temp;
i = j;
j = i * 2 + 1; //被篩選點(diǎn)位于原來結(jié)點(diǎn)j的位置
}
}
}
//堆排序算法
void HeapSort(Record r[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--) //初始建堆，從最后一個(gè)非終端結(jié)點(diǎn)至根結(jié)點(diǎn)進(jìn)行篩選
Sift(r, i, n - 1);
for (int i = 1; i < n; i++) //重復(fù)執(zhí)行移走堆頂及重建堆的操作
{
Record temp = r[0];
r[0] = r[n - i];
r[n - i] = temp;
Sift(r, 0, n - i - 1);
}
}
//一次歸并算法
void Merge(Record r[], Record r1[], int s, int m, int t)
{
int i = s;
int j = m + 1;
int k = s;
while (i <= m && j <= t)
if (r[i].key <= r[j].key)
r1[k++] = r[i++]; //取r[i]和r[j]中較小者放入r1[k]
else
r1[k++] = r[j++];
if (i <= m)
while (i <= m)
r1[k++] = r[i++]; //若第一個(gè)子序列沒處理完，則進(jìn)行收尾處理
else
while (j <= t)
r1[k++] = r[j++]; //若第二個(gè)子序列沒處理完，則進(jìn)行收尾處理
}
//一趟歸并排序算法
void MergePass(Record r[], Record r1[], int n, int h)
{
int i = 0;
while (i <= n - 2 * h + 1) //待歸并記錄至少有兩個(gè)長度為h的子序列
{
Merge(r, r1, i, i + h - 1, i + 2 * h - 1);
i += 2 * h;
}
if (i < n - h + 1)
Merge(r, r1, i, i + h - 1, n); //待歸并序列中有一個(gè)長度小于h
else
for (int k = i; k <= n; k++)
r1[k] = r[k]; //待歸并序列中只剩下一個(gè)子序列
}
//歸并排序的非遞歸算法
void MergeSort(Record r[], int n)
{
int h = 1;
Record* r1 = new Record[n];
while (h < n)
{
MergePass(r, r1, n - 1, h);
h = 2 * h;
MergePass(r1, r, n - 1, h);
h = 2 * h;
}
}
經(jīng)驗(yàn)總結(jié)
- 從平均時(shí)間來看，快速排序是效率最高的，但快速排序在最壞情況下的時(shí)間性能不如堆排序和歸并排序。而后者相比較的結(jié)果是，在n較大時(shí)歸并排序使用時(shí)間較少，但使用輔助空間較多；
- 上面說的簡單排序包括除希爾排序之外的所有冒泡排序、插入排序、簡單選擇排序。其中直接插入排序最簡單，但序列基本有序或者n較小時(shí)，直接插入排序是好的方法，因此常將它和其他的排序方法，如快速排序、歸并排序等結(jié)合在一起使用；
- 快速排序、堆排序、希爾排序等時(shí)間性能較好的排序方法都是不穩(wěn)定的。穩(wěn)定性需要根據(jù)具體需求選擇；
- 上面的算法實(shí)現(xiàn)大多數(shù)是使用線性存儲(chǔ)結(jié)構(gòu)，像插入排序這種算法用鏈表實(shí)現(xiàn)更好，省去了移動(dòng)元素的時(shí)間。具體的存儲(chǔ)結(jié)構(gòu)在具體的實(shí)現(xiàn)版本中也是不同的。
