基於C++完成的各類外部排序算法匯總。本站提示廣大學習愛好者：（基於C++完成的各類外部排序算法匯總）文章只能為提供參考，不一定能成為您想要的結果。以下是基於C++完成的各類外部排序算法匯總正文
提起排序算法信任年夜家都不生疏，也許許多人曾經把它們記得倒背如流，乃至隨時可以寫出來。是的，這些都是最根本的算法。這裡就把各類外部排序算法總結歸結了一下，包含拔出排序（直接拔出排序，折半拔出排序，希爾排序）、交流排序（冒泡排序，疾速排序）、選擇排序（簡略選擇排序，堆排序）、2-路合並排序。（另：至於堆排序算法，後面曾經有一篇文章針對堆排序的算法完成做了具體的描寫）
C++完成代碼以下：
/*************************************************************************
> File Name: sort.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
using namespace std;
typedef int ElementType;
/*
*<<直接拔出排序>>
* 為了完成N個數的排序，將前面N-1個數順次拔出到後面已排好的子序列中，
*假定剛開端第1個數是一個已排好序的子序列。經由N-1趟就可以獲得一個有序序列。
*****時光龐雜度：最好情形O(n)，最壞情形O(n^2)，均勻情形O(n^2).
*****空間龐雜度：O(1)
*****穩固性：穩固
*/
void InsertSort(ElementType A[], int n)
{
int i,j;
ElementType temp; // 暫時變量
for(i=1; i<n; ++i)
{
temp = A[i];
for(j = i; j>0 && A[j-1]>temp; --j)
A[j] = A[j-1];
A[j] = temp;
}
}
/*
*<<折半拔出排序>>
* 與直接拔出排序分歧的是，折半拔出排序不是邊比擬邊挪動，而是將比擬和移
*動操作分別出來，即先折半查找出元素的待拔出地位，然後再同一地挪動待拔出位
*置以後的一切元素。不好看出折半拔出排序僅僅是削減了比擬的次數。
*****時光龐雜度：O(n^2)
*****空間龐雜度：O(1)
*****穩固性：穩固
*/
void BinaryInsertSort(ElementType A[], int n)
{
int i, j, low, high, mid;
ElementType temp;
for(i=1; i<n; ++i)
{
temp = A[i];
low = 0; high = i-1; // 設置折半查找的規模
while(low <= high)
{
mid = (low+high)/2; // 取中央點
if(A[mid] > temp)
high = mid-1;
else
low = mid+1;
}
for(j=i-1; j>=high+1; --j) // 同一後移
A[j+1] = A[j];
A[high+1] = temp; // 拔出
}
}
/*
*<<希爾排序>>
* 希爾排序經由過程比擬相距必定距離的元素，即形如L[i,i+d,i+2d,...i+kd]的序列
*然後減少間距，再對各分組序列停止排序。直到只比擬相鄰元素的最初一趟排序為
*止，即最初的間距為1。希爾排序有時也叫做*減少增量排序*
*****時光龐雜度：依附於增量序列的選擇，但最壞情形才為O(N^2)
*****空間龐雜度：O(1)
*****穩固性：不穩固
*/
void ShellSort(ElementType A[], int n)
{
int i, j, dk; // dk是增量
ElementType temp;
for(dk=n/2; dk>0; dk/=2) // 增質變化
{
for(i=dk; i<n; ++i) // 每一個分組序列停止直接拔出排序
{
temp = A[i];
for(j=i-dk; j>=0 && A[j]>temp; j-=dk)
A[j+dk] = A[j]; // 後移
A[j+dk] = temp;
}
}
}
/*
*<<冒泡排序>>
* 冒泡排序的根本思惟是從後往前（或早年往後）兩兩比擬相鄰元素的值，若為
*逆序，則交流它們，直到序列比擬完。我們稱它為一趟冒泡。每趟冒泡都邑將一
*個元素放置到其終究地位上。
*****時光龐雜度：最好情形O(n)，最壞情形O(n^2)，均勻情形O(n^2)
*****空間龐雜度：O(1)
*****穩固性：穩固
*/
void BubbleSort(ElementType A[], int n)
{
for(int i=0; i<n-1; ++i)
{
bool flag = false; // 表現本次冒泡能否產生交流的標記
for(int j=n-1; j>i; --j) // 從後往前
{
if(A[j-1] > A[j])
{
flag = true;
// 交流
A[j-1] = A[j-1]^A[j];
A[j] = A[j-1]^A[j];
A[j-1] = A[j-1]^A[j];
}
}
if(flag == false)
return;
}
}
/*
*<<疾速排序>>
* 疾速排序是對冒泡排序的一種改良。其根本思惟是基於分治法：在待排序表L[n]
*中任取一個元素pivot作為基准，經由過程一趟排序將序列劃分為兩部門L[1...K-1]和
*L[k+1...n]，是的L[1...k-1]中的一切元素都小於pivot，而L[k+1...n]中一切元素
*都年夜於或等於pivot。則pivot放在了其終究地位L(k)上。然後，分離遞歸地對兩個子
*序列反復上述進程，直至每部門內只要一個元素或空為止，即一切元素放在了其終究
*地位上。
*****時光龐雜度：快排的運轉時光與劃分能否對稱有關，最壞情形O(n^2),最好情形
*O(nlogn),均勻情形為O(nlogn)
*****空間龐雜度：因為須要遞歸任務棧，最壞情形為O(n)，均勻情形為O(logn)
*****穩固性：不穩固
*/
int Partition(ElementType A[], int low, int high)
{
// 劃分操作有許多版本，這裡就總以以後表中第一個元素作為關鍵/基准
ElementType pivot = A[low];
while(low < high)
{
while(low<high && A[high]>=pivot)
--high;
A[low] = A[high]; // 將比關鍵值小的元素移到左端
while(low<high && A[low]<=pivot)
++low;
A[high] = A[low]; // 將比關鍵值年夜的元素移到右端
}
A[low] = pivot; // 關鍵元素放到終究地位
return low; // 前往關鍵元素的地位
}
void QuickSort(ElementType A[], int low, int high)
{
if(low < high) // 遞歸跳出的前提
{
int pivotPos = Partition(A, low, high); // 劃分操作，前往基准元素的終究地位
QuickSort(A, low, pivotPos-1); // 遞歸
QuickSort(A, pivotPos+1, high);
}
}
/*
*<<簡略選擇排序>>
* 選擇排序的算法思惟很簡略，假定序列為L[n]，第i趟排序即從L[i...n]當選擇
*症結字最小的元素與L(i)交流，每趟排序可以肯定一個元素的終究地位。經由n-1
*趟排序便可以使得序列有序了。
*****時光龐雜度：一直是O(n^2)
*****空間龐雜度：O(1)
*****穩固性：不穩固
*/
void SelectedSort(ElementType A[], int n)
{
for(int i=0; i<n-1; ++i) // 一共停止n-1趟
{
int minPos = i; // 記載最小元素的地位
for(int j=i+1; j<n; ++j)
if(A[j] < A[minPos])
minPos = j;
if(minPos != i) // 與第i個地位交流
{
A[i] = A[i]^A[minPos];
A[minPos] = A[i]^A[minPos];
A[i] = A[i]^A[minPos];
}
}
}
/*
*<<堆排序>>
* 堆排序是一種樹形選擇排序辦法，在排序進程中，將L[n]算作是一棵完整二叉
*樹的次序存儲構造，應用完整二叉樹中雙親節點和孩子節點之間的內涵關系，在當
*前無序區當選擇症結字最年夜（或最小）的元素。堆排序的思緒是：起首將序列L[n]
*的n個元素建成初始堆，因為堆自己的特色（以年夜根堆為例），堆頂元素就是最年夜
*值。輸入堆頂元素後，平日將堆底元素送入堆頂，此時根結點已不知足年夜根堆的性
*質，堆被損壞，將堆頂元素向下調劑使其持續堅持年夜根堆的性質，再輸入堆頂元素。
*如斯反復，直到堆中僅剩下一個元素為止。
*****時光龐雜度：O(nlogn)
*****空間龐雜度：O(1)
*****穩固性：不穩固
*/
void AdjustDown(ElementType A[], int i, int len)
{
ElementType temp = A[i]; // 暫存A[i]
for(int largest=2*i+1; largest<len; largest=2*largest+1)
{
if(largest!=len-1 && A[largest+1]>A[largest])
++largest; // 假如右子結點年夜
if(temp < A[largest])
{
A[i] = A[largest];
i = largest; // 記載交流後的地位
}
else
break;
}
A[i] = temp; // 被挑選結點的值放入終究地位
}
void BuildMaxHeap(ElementType A[], int len)
{
for(int i=len/2-1; i>=0; --i) // 從i=[n/2]~1，重復調劑堆
AdjustDown(A, i, len);
}
void HeapSort(ElementType A[], int n)
{
BuildMaxHeap(A, n); // 初始建堆
for(int i=n-1; i>0; --i) // n-1趟的交流和建堆進程
{
// 輸入最年夜的堆頂元素（和堆底元故舊換）
A[0] = A[0]^A[i];
A[i] = A[0]^A[i];
A[0] = A[0]^A[i];
// 調劑，把殘剩的n-1個元素整頓成堆
AdjustDown(A, 0, i);
}
}
/*
*<<2-路合並排序>>
* 望文生義，2-路合並就是將2個有序表組分解一個新的有序表。假定待排序表
*有n個元素，則可以算作是n個有序的子表，每一個子表長度為1，然後兩兩合並...不
*停反復，直到分解一個長度為n的有序序列為止。Merge()函數是將前後相鄰的兩個
*有序表合並為一個有序表，設A[low...mid]和A[mid+1...high]寄存在統一次序表的
*相鄰地位上，先將它們復制到幫助數組B中。每次從對應B中的兩個段掏出一個元素
*停止比擬，將較小者放入A中。
*****時光龐雜度：每趟合並為O(n),共log2n趟，所以時光為O(nlog2n)
*****空間龐雜度：O(n)
*****穩固性：穩固
*/
ElementType *B = new ElementType[13]; // 和數組A一樣年夜
void Merge(ElementType A[], int low, int mid, int high)
{
int i, j, k;
for(k=low; k<=high; ++k)
B[k] = A[k]; // 將A中一切元素復制到B
for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k)
{
if(B[i] <= B[j]) // 比擬B的閣下兩段序列中的元素
A[k] = B[i++]; // 將較小值復制到A中
else
A[k] = B[j++];
}
while(i<=mid) A[k++] = B[i++]; // 若第一個表未檢測完，復制
while(j<=high) A[k++] = B[j++]; // 若第二個表未檢測完，復制
}
void MergeSort(ElementType A[], int low, int high)
{
if(low < high)
{
int mid = (low + high)/2;
MergeSort(A, low, mid); // 對左邊子序列停止遞歸排序
MergeSort(A, mid+1, high); // 對右邊子序列停止遞歸排序
Merge(A, low, mid, high); // 合並
}
}
/*
* 輸入函數
*/
void print(ElementType A[], int n)
{
for(int i=0; i<n; ++i)
{
cout << A[i] << " ";
}
cout << endl;
}
/*
* 主函數
*/
int main()
{
ElementType Arr[13] = {5,2,1,8,3,6,4,7,0,9,12,10,11};
//InsertSort(Arr, 13);
//BinaryInsertSort(Arr, 13);
//ShellSort(Arr, 13);
//BubbleSort(Arr, 13);
//QuickSort(Arr, 0, 12);
//SelectedSort(Arr, 13);
//HeapSort(Arr, 13);
//MergeSort(Arr, 0, 12);
print(Arr, 13);
return 0;
}
信任本文所述實例代碼對年夜家溫習和穩固各類排序算法能起到必定的贊助感化。
