C++ to achieve a variety of sorting algorithm class summary
- 2020-04-02 02:26:14
- OfStack
C++ can achieve a variety of sorting algorithm classes, such as direct insertion sort, half insertion sort, Shell sort, merge sort, simple selection sort, radix sort, hill sort on the elements in the data array, bubble sort, recursive implementation, heap sort, with the array to achieve the radix sort.
The specific code is as follows:
#ifndef SORT_H
#define SORT_H
#include <iostream>
#include <queue>
using namespace std;
//1. Insert sort directly
template<class ElemType>
void InsertSort(ElemType data[], int n);
//2. Half insertion sort
template<class ElemType>
void BInsertSort(ElemType data[], int n);
//3. The Shell sort
//Hill sort the elements in the data array, n being the size of the array
//Increments is the incremental sequence, and incrementsLength is the size of the incremental sequence
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. Quicksort
template<class ElemType>
void QuickSort(ElemType data[], int n);
//////////////////
// Merge Sort
//////////////////
//Merge sort
template<class ElemType>
void MergeSort(ElemType data[],int n);
template<class ElemType>
void MergeSortNonRecursion(ElemType data[], int n);
//////////////////
// Selection sort
//////////////////
//Simple selection sort
template<class ElemType>
void SelectionSort(ElemType data[], int n);
//Heap sort
template<class ElemType>
void HeapSort(ElemType data[],int n);
///////////////
// Radix Sort
///////////////
//Static linked list nodes
const int DIGITS = 10;
const int RADIX = 10;
class SLList;
ostream& operator<<(ostream& os, SLList &s);//Since VC++6.0 USES using namespace STD for friends is not supported
//Therefore, the forward declaration is made before the class SLList
//These two sentences can be deleted if you use another C++ compiler
//A static linked list
//[0] : head node
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;
};
//Radix sort
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);
//Directly insert the sort, the array data is used to store the elements to be sorted, and n is the number of elements to be sorted
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]; //Save the element to be inserted
data[i] = data[i - 1];
for ( j = i - 1; j > 0 && data[j - 1] > tmp;j--)
data[j] = data[j - 1]; //Elements (one-way
data[j] = tmp; //Insert into the correct position
}
}
//Half insertion sort
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]; //Save the element to be inserted
low = 0;
high = i-1;
while (low <= high){ //Break in data[low..high] to find the ordered insertion location
mid = (low + high) / 2; //binary
if( tmp < data[mid])
high = --mid; //The insertion point is in the lower half
else
low = ++mid; //The insertion point is in the high half
}
for(j = i - 1; j >= low; j--)
data[j + 1] = data[j]; //Elements (one-way
data[low] = tmp; //Insert into the correct position
}
}
//Hill sort the elements in the data array, n being the size of the array
//Increments is the incremental sequence, and incrementsLength is the size of the incremental sequence
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++){ //Sort by 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;
}
}
}
//Bubble sort
template<class ElemType>
void BubbleSort(ElemType data[], int n)
{
int lastSwapIndex = n - 1; //The element index used to record the last exchange
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;
}
}
}
//Quick sort
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);
}
//Combine the elements of the [LPTR...rptr-1][RPTR...rightEnd] in the array data
//TmpArr is the secondary storage space when merging
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];
}
//The recursive implementation
//Merge the elements of [begin...end] in the array data
template<class ElemType>
void MSort(ElemType data[], ElemType tmpArr[], int begin, int end)
{
int middle;
if ( begin >= end)
return;
middle = (begin + end)/2; //Bisect the data into [begin..middle] and [middle..end]
MSort( data, tmpArr, begin, middle); //The first half of the recursion
MSort( data, tmpArr, middle + 1, end); //The second half of the recursion
Merge( data, tmpArr, begin, middle + 1, end); //Merge 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;
}
//Non-recursive implementation
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;
}
//Simple selection sort
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]);
}
}
//Heap sort
//I is the index of the specified element in the array
//Returns the index of the left child of the specified node in the array
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]) //Take the larger child node
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--) //Building the heap
HeapAdjust(data, i, n);
for (i = n - 1;i > 0; i--){ //Swap the root of the heap with the last leaf and adjust
Swap(data[0],data[i]);
HeapAdjust(data, 0, i);
}
}
//Radix sort with arrays
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]); //distribution
for ( k = j = 0; j < radix; j++,k++) //collect
while (!queues[j].empty()){
data[k] = queues[j].front();
queues[j].pop();
}
}
}
//distribution
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;
}
}
//collect
void SLList::Collection(int front[], int rear[], int digit)
{
int i, current;
for (i = 0; front[i] == 0; i++); //Find the first non-empty subtable
data[0].next = front[i]; //The header points to the first node in the first nonempty child table
current = rear[i++];
for (; i < RADIX; i++){
if (front[i] == 0)
continue;
data[current].next = front[i]; //Link two non-empty subtables
current = rear[i];
}
data[current].next = 0;
}
//The radix sort implemented with SLList
void SLList::RadixSort()
{
int i;
int front[RADIX],rear[RADIX];
//Allocate and collect each keyword from the lowest position first
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;
}
//Adjust the position of elements according to the pointer value of each node in the linked list, so that the elements in SLList are arranged in the positive order of keywords
void SLList::Arrange()
{
int i, tmp;
int current = data[0].next; //Current holds the current location of the first element
for (i = 1; i < length; i++){
while (current < i) //Find the I th element and use current to store its current position in the static list
current = data[current].next;
tmp = data[current].next;
if (current != i){
Swap(data[current], data[i]); //The ith element is in place
data[i].next = current; //Points to the removed element
}
current = tmp; //To prepare for the I plus 1 element
}
}
ostream& operator<<(ostream& os,SLList &s)
{
for (int i = 1; i < s.length; i++)
cout << s.data[i].info << " ";
os << endl;
return os;
}
#endif