1. 前文汇总

前面陆陆续续总结过常用排序算法，如下：

数据结构与算法——快排序

数据结构与算法——插入排序

C++——归并排序，从固定数据类型到函数模板以及使用函数对象自定义递增/递减

数据结构与算法——插入排序——使用C++实现函数模板、

数据结构与算法——希尔排序

数据结构与算法——选择排序

2. 常用排序算法整理

将常用的排序算法进行了实现，写成了模板，并放在了一个命名空间下面。包括插入排序，选择排序，希尔排序，快排序，堆排序和归并排序。

需要注意的就是模板的特化，不能将模板函数的定义放在头文件（.h）而声明放在源文件（.cpp）中，这样会报错。

使用了VS自带的region进行代码分区，加了点注释。

排序算法写在sort.h里面，如下：

#pragma once #include <vector> using namespace std; namespace zzs_sort { template<typename T> void swap(T* a, T* b) { if (*a == *b)return; T tmp = *a; *a = *b; *b = tmp; } #pragma region insertSort template<typename T, class compare = std::less<T>> void insertSort(vector<T>& nums, compare cmp = std::less<T>()) {//实现插入排序功能的函数 int n = nums.size(); if (n == 0)return; int i = 1, j = 1; T tmp; for (; i < n; i++) { tmp = nums[i]; for (j = i - 1; j >= 0 && cmp(tmp, nums[j]); j--) {//如果nums[j]大于nums[i] nums[j + 1] = nums[j]; //将nums[j]后移 } //内层循环结束之后，nums[j]<tmp，此时nums[j+1]是tmp的位置 nums[j + 1] = tmp; } } #pragma endregion #pragma region selectSort template<typename T, class compare = std::less<T>> void selectSort(vector<T>& nums, compare cmp = less<T>()) { int n = nums.size(); if (n == 0)return; for (int i = 0; i < n; i++) { T tmp = nums[i]; int idx = i; for (int j = i; j < n; j++) { if (cmp(nums[j], tmp)) { tmp = nums[j]; idx = j; } } nums[idx] = nums[i]; nums[i] = tmp; } } #pragma endregion #pragma region shellSort //生成Hibbard增量序列，Dk=2^k-1,{1, 3, 7, 15, 31...} struct getHibbardGaps { void operator()(int n, vector<int>& gaps) { int i = 1; gaps.clear(); int tmp = 0; while ((tmp = (1 << i) - 1) <= n) { gaps.push_back(tmp); i++; } } }; //生成一般增量序列，{n/2, (n/2)/2,..., 1} struct getNormalGaps { void operator()(int n, vector<int>& gaps) { int i = 1; gaps.clear(); int tmp = n; while ((tmp /= 2) > 0) { gaps.push_back(tmp); i++; } reverse(gaps.begin(), gaps.end()); } }; template<typename T, typename compare = std::less<T>, typename getGaps = zzs_sort::getNormalGaps> void shellSort(vector<T>& nums, compare cmp = std::less<T>(), getGaps funGaps = zzs_sort::getNormalGaps()) { int n = nums.size(); if (n == 0)return; vector<int> gaps; funGaps(n, gaps); for (auto it = gaps.rbegin(); it != gaps.rend(); it++) { int gap = *it; for (int i = gap; i < n; i++) { T tmp = nums[i]; int j; for (j = i - gap; j >= 0 && !(cmp(nums[j], tmp)); j -= gap) { nums[j + gap] = nums[j]; } nums[j + gap] = tmp; } } } #pragma endregion #pragma region quickSort //在首尾和中间元素中找到主元 template<typename T, class compare = std::less<T>> T GeneratePivot(vector<T>& nums, int left, int right, compare cmp = std::less<T>()) {//选择区间首，中，尾元素中的中间值作为主元，并将这三个元素放到合适的位置 int center = left + (right - left) / 2; if (!(cmp(nums[left], nums[center])))swap(&nums[left], &nums[center]); if (!(cmp(nums[left], nums[right])))swap(&nums[left], &nums[right]); if (!(cmp(nums[center], nums[right])))swap(&nums[center], &nums[right]); //以上三次交换，将arr[left],arr[center],arr[right]三个位置变成升序有序的 //即交换完成之后，arr[center]应该设为pivot swap(&nums[right - 1], &nums[center]);//pivot大于等于自己，所以先放到最右侧right-1的位置 return nums[right - 1];//此时right-1存放的是pivot } template<typename T, class compare = std::less<T>> void QuickSort(vector<T>& nums, int left, int right, compare cmp = std::less<T>()) {//快排序实现函数，递归调用自身，实现排序 if (left >= right)return; T pivot = GeneratePivot(nums, left, right); int i = left, j = right - 1;//由于GeneratePivot已经完成了首尾元素相对pivot的有序，因此j从right-1开始 while (true) { while (cmp(nums[++i], pivot)) {} while (j > 0 && !(cmp(nums[--j], pivot))) {} if (i < j) { swap(&nums[i], &nums[j]); } else { break; } } //跳出循环之后，i就是pivot的合适的位置了 if (i < right) { if (nums[i] != nums[right - 1]) { swap(&nums[i], &nums[right - 1]);//将pivot放到合适的地方 } } //然后递归调用自己 QuickSort(nums, left, i - 1); QuickSort(nums, i + 1, right); } template<typename T, class compare = std::less<T>> void quickSort(vector<T>& nums, compare cmp = std::less<T>()) { if (nums.size() <= 1)return; QuickSort(nums, 0, nums.size() - 1); } #pragma endregion #pragma region heapSort inline int Left(int index) { return (index << 1) + 1; } inline int Right(int index) { return (index << 1) + 2; } //下沉（堆顶不是最大值的时候，将其下沉） template<typename T, class compare = std::less<T>> void maxHeapify(vector<T>& nums, int idx, int heapSize, compare cmp = std::less<T>()) {//堆顶节点下沉——重新调整为大顶堆 int tmpMax = 0; int left = Left(idx); int right = Right(idx); //堆顶与其左节点比较 if ((left <= heapSize) && (!(cmp(nums[left], nums[idx])))) tmpMax = left; else tmpMax = idx; //堆顶与其右节点比较 if ((right <= heapSize) && (!(cmp(nums[right], nums[tmpMax])))) tmpMax = right; //此时tmpMax为堆顶左右节点中的最大者 if (tmpMax != idx) { //如果堆顶不是最大值，则交换堆顶和tmpMax，并递归调整堆 T tmp = nums[idx]; nums[idx] = nums[tmpMax]; nums[tmpMax] = tmp; //swap(&nums[idx], &nums[tmpMax]); maxHeapify(nums, tmpMax, heapSize); } } template<typename T, class compare = std::less<T>> void buildMaxHeap(vector<T>& nums, compare cmp = std::less<T>()) {//构造大顶堆函数 int len = nums.size() - 1; if (len <= 0)return; for (int i = (len >> 1); i >= 0; i--) {//从堆的底部开始调整，自底向下 maxHeapify(nums, i, len); } } template<typename T, class compare = std::less<T>> void heapSort(vector<T>& nums, compare cmp = std::less<T>()) {//堆排序主函数 buildMaxHeap(nums);//初始化堆 int len = nums.size(); int heapSize = len - 1; for (int i = len - 1; i >= 1; i--) { //将堆顶元素(最大值)换到堆数组的末尾 T tmp = nums[0]; nums[0] = nums[i]; nums[i] = tmp; //swap(&nums[0], &nums[i]); maxHeapify(nums, 0, --heapSize); } } #pragma endregion #pragma region mergeSort template<typename T, typename compare = std::less<T>> //实现具体归并的函数 void Merge(vector<T>& nums, int start, int mid, int end, vector<T>& tmp, compare cmp = std::less<T>()) { int firstIdx = start; int secondIdx = mid + 1; int numsIdx = start; //先将两个已排序序列复制到tmp中 for (int i = start; i <= mid; ++i)tmp[i] = nums[i]; for (int i = mid + 1; i <= end; ++i)tmp[i] = nums[i]; //然后将tmp中的两段数组合并到nums中 while (numsIdx <= end) { if (secondIdx > end)nums[numsIdx++] = tmp[firstIdx++]; else if (firstIdx > mid)nums[numsIdx++] = tmp[secondIdx++]; else { if (cmp(tmp[firstIdx], tmp[secondIdx]))nums[numsIdx++] = tmp[firstIdx++]; else nums[numsIdx++] = tmp[secondIdx++]; } } } template<typename T, typename compare = std::less<T>> //归并排序的入口 void MSort(vector<T>& nums, int start, int end, vector<T>& tmp, compare cmp = std::less<T>()) { if (nums.empty() || start >= end)return; int mid = start + (end - start) / 2; //将待排序区间从中间分割开 MSort(nums, start, mid, tmp, cmp); MSort(nums, mid + 1, end, tmp, cmp); //将分割开的元素进行合并 Merge(nums, start, mid, end, tmp, cmp); } template<typename T, typename compare = std::less<T>> //通用接口 void mergeSort(vector<T>& nums, compare cmp = std::less<T>()) { vector<T> tmp(nums.size()); MSort(nums, 0, nums.size() - 1, tmp, cmp); } #pragma endregion }

然后自定义了数据类型，使用了：1）重载比较运算符；2）自定义函数对象；3）匿名表达式，这三种方式，对程序进行了测试。代码如下：

#include <iostream> #include <ctime> #include "sort.h" using namespace std; using namespace zzs_sort; template<typename T> void printVector(vector<T>& nums);//辅助函数：打印容器中元素 void generateIntVector(vector<int>& nums, int n);//辅助函数：生成n个随机数填入int类型的vector //该类用来测试insertSort函数对自定义数据类型排序的正确性 //对自定义数据类型，需要1）重载小于或者大于运算符；2）自定义用于比较的函数对象 class Base { int x; public: Base() :x(-1) {} explicit Base(int m_x) :x(m_x) {} friend bool operator< (const Base& b1, const Base& b2); friend class cmp1; friend ostream& operator<<(ostream& os, const Base& b); friend bool operator !=(const Base& b1, const Base& b2); int getX() { return x; } }; //重载小于"<"运算符 bool operator<(const Base & b1, const Base & b2) { return b1.x < b2.x; } bool operator !=(const Base& b1, const Base& b2) { return b1.x != b2.x; } //重载<<，用于打印输出 ostream& operator<<(ostream& os, const Base& b) { os << b.x; return os; } //定义函数对象，用于自定义类型的比较 struct cmp1 { bool operator()(Base& b1, Base& b2) { return b1.x < b2.x; } }; int main() { srand((int)time(0)); //测试基本数据类型的排序 vector<int> nums1; generateIntVector(nums1, 10); cout << "Initial value of nums1: "; printVector<int>(nums1); //insertSort<int>(nums1,NULL); quickSort<int>(nums1); cout << "Sorted value of nums1: "; printVector<int>(nums1); //以下测试自定义数据类型的排序 vector<Base> baseArr; for (int i = 0; i < 15; i++) { int tmpVal = rand() % 100; Base tmpBase(tmpVal); baseArr.push_back(tmpBase); } cout << "Initial value of baseArr: "; printVector<Base>(baseArr); //insertSort<Base>(baseArr);//重载<运算符之后，使用默认的less //insertSort<Base>(baseArr, cmp1());//使用自定义的函数对象进行比较 mergeSort<Base>(baseArr, [](Base& b1, Base& b2)mutable -> bool {return b1.getX() < b2.getX(); });//使用匿名函数进行比较 cout << "Sorted value of baseArr: "; printVector<Base>(baseArr); return 0; } /** * @brief 向标准输出流输出vecotr中的元素，元素之间以空格分割 * @param[in] nums 要打印的vector * @return */ template<typename T> void printVector(vector<T>& nums) { if (nums.empty()) { cout << "The vector is empty!" << endl; return; } cout << nums[0]; for (int i = 1; i < nums.size(); i++)cout << " " << nums[i]; cout << endl; } /** * @brief 生成n个int型随机数，填充到vector容器中 * @param[in] n 要填充的元素的个数 * @param[out] nums 要往里填充元素的容器 * @return */ void generateIntVector(vector<int>& nums, int n) { int tmp = 0; for (int i = 0; i < n; i++) { tmp = rand() % 100; nums.push_back(tmp); } }