C++完成各類排序算法類匯總。本站提示廣大學習愛好者：（C++完成各類排序算法類匯總）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成各類排序算法類匯總正文
C++可完成各類排序算法類，好比直接拔出排序、折半拔出排序、Shell排序、合並排序、簡略選擇排序、基數排序、對data數組中的元素停止希爾排序、冒泡排序、遞歸完成、堆排序、用數組完成的基數排序等。
詳細代碼以下：
#ifndef SORT_H
#define SORT_H
#include <iostream>
#include <queue>
using namespace std;
// 1.直接拔出排序
template<class ElemType>
void InsertSort(ElemType data[], int n);
// 2.折半拔出排序
template<class ElemType>
void BInsertSort(ElemType data[], int n);
// 3.Shell排序
// 對data數組中的元素停止希爾排序，n為該數組年夜小
// increments為增量序列，incrementsLength為增量序列的年夜小
template<class ElemType>
void ShellSort(ElemType data[],int increments[], int n, int incrementsLength);
// 1.Bubble Sort
template<class ElemType>
void BubbleSort(ElemType data[], int n);
// 2.疾速排序
template<class ElemType>
void QuickSort(ElemType data[], int n);
//////////////////
// Merge Sort
//////////////////
// 合並排序
template<class ElemType>
void MergeSort(ElemType data[],int n);
template<class ElemType>
void MergeSortNonRecursion(ElemType data[], int n);
//////////////////
// Selection sort
//////////////////
// 簡略選擇排序
template<class ElemType>
void SelectionSort(ElemType data[], int n);
// 堆排序
template<class ElemType>
void HeapSort(ElemType data[],int n);
///////////////
// Radix Sort
///////////////
// 靜態鏈表結點
const int DIGITS = 10;
const int RADIX = 10;
class SLList;
ostream& operator<<(ostream& os, SLList &s);// 因為VC++6.0應用using namespace std關於友元不支撐
// 故在類SLList之前做前向聲明
// 若應用其他C++編譯器，這兩句可刪去
// 靜態鏈表static linked list
// [0]：頭結點
class SLList
{
struct Node
{
int key[DIGITS];
int info;
int next;
};
friend ostream& operator<<(ostream& os, SLList &s);
public:
SLList():data(NULL),length(0){};
~SLList();
void Arrange();
void Init(int arr[],int n);
void RadixSort();
private:
void Distribute( int[], int[], int);
void Collection( int[], int[], int);
Node *data;
int length;
};
// 基數排序
void RadixSort(int data[], int n);
//void RadixSort(SLList&);
///////////////
// util
///////////////
template<class ElemType>
void Swap( ElemType& a, ElemType& b)
{
ElemType c = a;
a = b;
b = c;
}
int init(int** data);
template<class ElemType>
void print(ElemType data[],int begin,int end);
// 直接拔出排序,數組data用於寄存待排序元素，n為待排序元素個數
template<class ElemType>
void InsertSort(ElemType data[], int n)
{
ElemType tmp;
int i, j;
for (i = 1; i < n; i++){
if ( data[i] > data[i - 1])
continue;
tmp = data[i]; // 保留待拔出的元素
data[i] = data[i - 1];
for ( j = i - 1; j > 0 && data[j - 1] > tmp;j--)
data[j] = data[j - 1]; // 元素後移
data[j] = tmp; // 拔出到准確地位
}
}
// 折半拔出排序
template<class ElemType>
void BInsertSort(ElemType data[], int n)
{
ElemType tmp;
int i, j, mid, low, high;
for (i = 1; i < n; i++){
tmp = data[i]; // 保留待拔出的元素
low = 0;
high = i-1;
while (low <= high){ // 在data[low..high]中折半查找有序拔出的地位
mid = (low + high) / 2; // 折半
if( tmp < data[mid])
high = --mid; // 拔出點在低半區
else
low = ++mid; // 拔出點在高半區
}
for(j = i - 1; j >= low; j--)
data[j + 1] = data[j]; // 元素後移
data[low] = tmp; // 拔出到准確地位
}
}
// 對data數組中的元素停止希爾排序，n為該數組年夜小
// increments為增量序列，incrementsLength為增量序列的年夜小
template<class ElemType>
void ShellSort(ElemType data[], int increments[], int n, int incrementsLength)
{
int i, j, k;
ElemType tmp;
for ( k = 0; k < incrementsLength; k++){ // 停止以increments[k]為增量的排序
for ( i = increments[k]; i < n; i++){
tmp = data[i];
for ( j = i; j >= increments[k]; j -= increments[k]){
if ( tmp >= data[j - increments[k]])
break;
data[j] = data[j - increments[k]];
}
data[j] = tmp;
}
}
}
// 冒泡排序
template<class ElemType>
void BubbleSort(ElemType data[], int n)
{
int lastSwapIndex = n - 1; // 用於記載最初一次交流的元素下標
int i, j;
for (i = lastSwapIndex; i > 0;i = lastSwapIndex)
{
lastSwapIndex = 0;
for (j = 0; j < i; j++)
if (data[j] > data[j + 1]){
Swap( data[j],data[j + 1]);
lastSwapIndex = j;
}
}
}
//疾速排序
template<class ElemType>
int Partition(ElemType data[] , int low , int high)
{
ElemType pivot = data[low];
while (low < high){
while (low < high && data[high] >= pivot)
high--;
data[low] = data[high];
while (low < high && pivot >= data[low])
low++;
data[high] = data[low];
}
data[low] = pivot;
return low;
}
template<class ElemType>
void QuickSort(ElemType data[], int begin, int end)
{
if (begin >= end)
return;
int pivot = Partition(data , begin , end);
QuickSort(data , begin , pivot - 1);
QuickSort(data , pivot + 1, end);
}
template<class ElemType>
void QuickSort(ElemType data[], int n)
{
if (n < 2)
return;
QuickSort(data, 0, n-1);
}
// 將數組data中，[lptr...rptr-1][rptr...rightEnd]兩部門的元素停止歸並
// tmpArr為歸並時的輔存空間
template<class ElemType>
void Merge(ElemType data[], ElemType tmpArr[], int lptr, int rptr, int rightEnd)
{
int leftEnd = rptr - 1;
int ptr,i;
ptr = i = lptr;
while (lptr <= leftEnd && rptr <= rightEnd)
if (data[lptr] <= data[rptr])
tmpArr[ptr++] = data[lptr++];
else
tmpArr[ptr++] = data[rptr++];
while (lptr <= leftEnd)
tmpArr[ptr++] = data[lptr++];
while (rptr <= rightEnd)
tmpArr[ptr++] = data[rptr++];
for (;i <= rightEnd; i++)
data[i] = tmpArr[i];
}
// 遞歸完成
// 將數組data中，[begin...end]的元素停止合並排序
template<class ElemType>
void MSort(ElemType data[], ElemType tmpArr[], int begin, int end)
{
int middle;
if ( begin >= end)
return;
middle = (begin + end)/2; // 將data等分為[begin..middle]和[middle..end]
MSort( data, tmpArr, begin, middle); // 遞歸前半部門
MSort( data, tmpArr, middle + 1, end); // 遞歸後半部門
Merge( data, tmpArr, begin, middle + 1, end); // 將data[begin..middle]，data[middle..end]停止合並
}
template<class ElemType>
void MergeSort(ElemType data[], int n)
{
ElemType* pArr = NULL;
pArr = new ElemType[n];
MSort( data,pArr,0,n-1);
delete[] pArr;
}
// 非遞歸完成
template<class ElemType>
void MPass(ElemType data[], ElemType tmpArr[], int n, int mergeLength)
{
int i = 0;
while (i <= n - 2 * mergeLength){
Merge(data, tmpArr, i, i + mergeLength, i + 2 * mergeLength - 1);
i = i + 2 * mergeLength;
}
if (i + mergeLength < n)
Merge(data, tmpArr, i, i + mergeLength, n - 1);
}
template<class ElemType>
void MergeSortNonRecursion(ElemType data[], int n)
{
int mergeLength = 1;
ElemType* pArr = NULL;
pArr = new ElemType[n];
while (mergeLength < n){
MPass(data, pArr, n, mergeLength);
mergeLength *= 2;
}
delete[] pArr;
}
// 簡略選擇排序
template<class ElemType>
void SelectionSort(ElemType data[], int n)
{
int i, j, min;
for (i = 0; i < n; i++){
min = i;
for (j = i + 1; j < n; j++){
if ( data[j] < data[min])
min = j;
}
Swap(data[i],data[min]);
}
}
// 堆排序
// i為指定元素在數組中的下標
// 前往指定結點的左孩子在數組中的下標
inline int LeftChild(int i)
{
return 2 * i + 1;
}
template<class ElemType>
void HeapAdjust(ElemType data[], int i, int n)
{
ElemType tmp;
int child;
for ( tmp = data[i]; LeftChild(i) < n; i = child){
child = LeftChild(i);
if (child != n - 1 && data[child + 1] > data[child]) // 取較年夜的孩子結點
child++;
if (tmp < data[child])
data[i] = data[child];
else
break;
}
data[i] = tmp;
}
template<class ElemType>
void HeapSort(ElemType data[], int n)
{
int i;
for (i = n/2; i >= 0; i--) // 建堆
HeapAdjust(data, i, n);
for (i = n - 1;i > 0; i--){ // 將堆的根結點與最初的一個葉結點交流,並停止調劑
Swap(data[0],data[i]);
HeapAdjust(data, 0, i);
}
}
// 用數組完成的基數排序
void RadixSort(int data[], int n)
{
const int radix = 10;
const int digits = 10;
int i,j,k,factor;
queue<int> queues[radix];
for ( i = 0,factor = 1; i < digits;i++,factor *= radix){
for ( j = 0;j < n; j++)
queues[(data[j]/factor)%radix].push(data[j]); // 分派
for ( k = j = 0; j < radix; j++,k++) // 搜集
while (!queues[j].empty()){
data[k] = queues[j].front();
queues[j].pop();
}
}
}
// 分派
void SLList::Distribute(int front[], int rear[], int digit)
{
int i, index;
for (i = 0; i < RADIX; i++)
front[i] = 0;
for (i = data[0].next; i > 0; i = data[i].next){
index = data[i].key[digit];
if (front[index] == 0)
front[index] = i;
else
data[rear[index]].next = i;
rear[index] = i;
}
}
// 搜集
void SLList::Collection(int front[], int rear[], int digit)
{
int i, current;
for (i = 0; front[i] == 0; i++); // 找到第一個非空子表
data[0].next = front[i]; // 頭結點指向第一個非空子表中第一個結點
current = rear[i++];
for (; i < RADIX; i++){
if (front[i] == 0)
continue;
data[current].next = front[i]; // 鏈接兩個非空子表
current = rear[i];
}
data[current].next = 0;
}
// 用SLList完成的基數排序
void SLList::RadixSort()
{
int i;
int front[RADIX],rear[RADIX];
// 從最低位優先順次對各症結字停止分派搜集
for ( i = 0; i < DIGITS; i++){
Distribute(front, rear, i);
Collection(front, rear, i);
}
}
SLList::~SLList()
{
delete[] data;
length = 0;
}
void SLList::Init(int arr[], int n)
{
length = n + 1;
if (data != NULL)
delete[] data;
data = new Node[n + 1];
data[0].next = 1;
for ( int i = 1; i <= n; i++){
int value = data[i].info = arr[i - 1];
for (int j = 0;j < 10; j++){
data[i].key[j] = value % 10;// + '0';
value /= 10;
}
data[i].next = i + 1;
}
data[n].next = 0;
}
// 依據鏈表中各結點的指針值調劑元素地位，使得SLList中元素按症結字正序分列
void SLList::Arrange()
{
int i, tmp;
int current = data[0].next; // current寄存第一個元素確當前地位
for (i = 1; i < length; i++){
while (current < i) // 找到第i個元素，並用current寄存其在靜態鏈表中以後地位
current = data[current].next;
tmp = data[current].next;
if (current != i){
Swap(data[current], data[i]); // 第i個元素調劑到位
data[i].next = current; // 指向被移走的元素
}
current = tmp; // 為找第i + 1個元素做預備
}
}
ostream& operator<<(ostream& os,SLList &s)
{
for (int i = 1; i < s.length; i++)
cout << s.data[i].info << " ";
os << endl;
return os;
}
#endif
