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
【C++实现各种排序算法类汇总】相关文章：