核心算法 SortString.h
#pragma once #include <memory> #include <string> class SortString { private: const int R = 256; std::string *row; int size; private: int toIndex(const std::string& s,const int& pos) { if (pos <= s.length()) return s[pos]; else return -1; } public: SortString(std::string s[], const int& n) :row(s),size(n) { } void sort() { sort(0, size - 1, 0); } void sort(const int& lo,const int& hi,int d) { if (lo >= hi) return; //可通过一定阈值进行插入排序 std::unique_ptr<int[]> count(new int[R + 2]); std::unique_ptr<std::string[]> aux(new std::string[(hi - lo) + 1]); for (int i = 0; i < R + 2; ++i) count[i] = 0; for (int i = lo; i <= hi; ++i) count[toIndex(row[i],d) + 2]++; // ASCII 0 -- 255 起始位置对应 count[1] -- count[256] // count[0]用于存放超出索引值的起始位置 for (int i = 0; i < R + 1; ++i) count[i + 1] += count[i]; //将row[lo] -- row[hi] 映射为排序后的 aux[0] -- aux[hi - lo] for (int i = lo; i <= hi; ++i) aux[count[toIndex(row[i], d) + 1]++] = row[i]; // 回写 for (int i = lo; i <= hi; ++i) row[i] = aux[i - lo]; for (int i = 0; i < R; ++i) sort(lo + count[i], lo + count[i + 1] - 1, d + 1); } };测试 main.cpp
#include <iostream> #include "SortString.h" using namespace std; int main() { string s[13] = { "black", "clock", "all", "angle", "demo", "girl", "fork", "emplace", "abcde", "acdbe", "aaba", "calo", "daole" }; SortString ss(s, 13); for (int i = 0; i < 13; ++i) cout << s[i] << endl; cout << "--------------------" << endl; ss.sort(); for (int i = 0; i < 13; ++i) cout << s[i] << endl; system("pause"); return 0; }