源代码github：无堆排序版本 更新版本
比较排序和非比较排序 根据是否进行比较（<,>）分为：比较排序和非比较排序 常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。
比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。
内部排序和外部排序 根据排序工作在内存还是在磁盘中完成。在内存中完成的排序称为内部排序，在磁盘中完成的排序称为外部排序。
算法：遍历数组arr[]，遍历到i时，arr[0],arr[1]...arr[i-1]是已经排好序的，比如升序，取出a[i]，从a[i-1]开始向前和每个数值比较大小，如果a[i]<a[i-1]，则将a[i]与a[i-1]交换位置，继续与前面比较，直到a[i]>a[j]或与arr[0]比较完成。可见相等元素比较是，原来靠后的还是在后边，所以插入排序是稳定的。当输入数据有序时，只是遍历数组而不会执行交换操作，因此时间复杂度O(N)，最坏的情况是数组是逆序的（如降序排序，而输入是增序），因此每个数据arr[i]都要执行i-1次交换，时间复杂度O(N*N)；记输入数据中的逆序（i<j,a[i]>a[j]的所有i，j对）数为I，则插入排序的时间复杂度为O(I+N)。有定理：N个互异元素的数组，平均逆序数I=N(N-1)/4，因此插入排序的平均时间复杂度为o(N*N)，即亚二次。对于所有通过交换数组两元素实现排序的算法，也有这个属性。
原始数组
34 8 64 51 32 21
移动（交换）的次数
p=1
8 34...
1
p=2
8 34 64...
0
p=3
8 34 51 64
1
p=4
8 32 34 51 64
3
p=5
8 21 32 34 51 64
4
void insertionSort(vector<int>& arr) { int size = arr.size(); for (int i = 1; i < size; i++) { int k = i;//使用i的值而不要修改i for (int j = i - 1; j >= 0; j--)//对于所有的j<i,判断大小并执行交换 { if (arr[k] < arr[j]) { int temp = arr[k]; arr[k] = arr[j]; arr[j] = temp; k = j;//交换arr[k]和arr[j]之后，arr[k]位于j处，因此k也要变 } } cout << "arr[0]-arr[" << i << "] sort: "; for (int j = 0; j <= i; j++) cout<< arr[j] << " "; cout << endl; } }同上述分析，第k轮排序，前k-1个数据有序。
堆的定义：堆中元素以完全二叉树的形式储存，又因为完全二叉树可以按层序表示为一维数组，因此可以使用一维数组来储存。堆中每个节点仅与父节点有关系，若是小顶堆，则当前节点大于等于父节点（大顶堆，当前节点小于等于父节点）。对于一维数组形式的堆，可以根据索引判断父子关系，起始索引为0，则位置i处的节点，其左儿子节点为2i+1，右儿子为2i+2，父节点为(i-1)/2。
堆的基本操作：插入和删除堆顶。插入是向已有堆中插入一个新的节点，删除只能删除堆顶，但是由于堆的父子关系， 需要进行一系列操作保证堆序。
插入：插入通过使用空穴上滤的方法完成。首先在可用位置（完全二叉树的当前层下个位置或下一层第一个位置，数组的末尾）建立一个空穴，并插入待插入节点的值。根据堆序，执行上滤操作，即若大顶堆，而插入的节点值大于其父节点，则一直上滤，直到满足堆序或到达堆顶。
void heapInsert(vector<int>& nums, int val) { nums.push_back(val);//数组末尾放入新节点 int n = nums.size(); int idx = n - 1;//空穴初始位置 for (int i = (idx-1)/2; i >= 0; i=(i-1)/2)//从其父节点开始 直到根节点 { if (nums[idx] < nums[i])//不满足堆序 上滤 { nums[idx] = nums[i]; nums[i] = val; idx = i; } else break;//满足堆序 退出 } }
删除堆顶：删除通过使用空穴下滤的方法完成。由于使用数组保存完全二叉树，而删除节点的时间复杂度太大，所以将被删除的节点移动到数组末尾，通过一个变量记录当前堆中的节点个数，来防止被删除节点的访问，实现删除。如上所述，堆顶元素需要放到数组末尾，而数组末尾已有其他元素，因此需要移动该元素。将堆顶视为空穴，每次在其两个子节点中根据堆序选择下滤的方向，直到数组末尾的元素放在空穴满足堆序。
void heapDelete(vector<int>& nums, int& n) { int end = nums[n - 1];//数组末尾元素 nums[n - 1] = nums[0];//删除堆顶 nums[0] = end; n--;//数目更新 int idx = 0;//从堆顶开始下滤 while (1) { int left = 2 * idx + 1;//左子节点索引 int right = 2 * idx + 2;//右子节点索引 if (left < n && right < n)//左右子节点均合法 { if (nums[idx] <= nums[left] && nums[idx] <= nums[right]) break;//当前位置符合堆序 退出 else { if (nums[left] < nums[right])//left<cur<right { nums[idx] = nums[left];//当前位置选较小的 nums[left] = end;//下移 idx = left; } else//right<cur<left 当前位置选较小的 { nums[idx] = nums[right];//下移 nums[right] = end; idx = right; } } } else if (left < n)//只有左子节点 { if (nums[idx] <= nums[left]) break;//符合堆序 退出 else { nums[idx] = nums[left];//下滤 nums[left] = end; idx = left; } } else if (right < n)//只有右子节点 { if (nums[idx] <= nums[right]) break;//符合堆序 退出 else { nums[idx] = nums[right];//下滤 nums[right] = end; idx = right; } } else break;//到达叶节点 退出 } }
堆排序：堆（优先队列）的排序可以以时间复杂度O(NlogN)运行。算法首先将输入数组建立堆，花费O(N)时间，每次删除堆顶元素花费logN时间，删除N次堆顶元素，总的时间复杂度为O(N+N*logN)=O(N*logN)，堆顶元素的变化序列即是数组的有序序列，如果是大顶堆，那么得到降序排序，反之小顶堆则得到增序排序。这里注意堆的性质，只要堆顶元素是最大值（大顶堆）或最小值（小顶堆），堆中节点只有父子节点间有大小关系，而兄弟节点间无序。但是因为每次删除节点后，堆顶仍然为剩余元素的最大值（大顶堆）或最小值（小顶堆），所以当删除所有元素后，堆顶元素的变化序列即为有序序列。这里没有用数组交换来实现堆，而是直接用了堆的stl实现，实际上应该使用数组交换来实现堆的建立和删除节点，直接使用优先队列会增加额外的储存空间。
使用n次insert建立一个大小为n的堆，再删除堆顶n次，数组中即为堆排序的结果。若使用小顶堆，则数组内为升序，反之为降序。
使用stl模板的堆排序：
void heapSort(vector<int>& arr,bool method) { if (!method)//升序 { priority_queue<int, vector<int>, greater<> >queMin;//小顶堆 int size = arr.size(); for (int i = 0; i < size; i++) queMin.push(arr[i]); int i = 0; while (!queMin.empty()) { arr[i] = queMin.top(); queMin.pop(); i++; } } else//降序 { priority_queue<int>queMax;//大顶堆 int size = arr.size(); for (int i = 0; i < size; i++) queMax.push(arr[i]); int i = 0; while (!queMax.empty()) { arr[i] = queMax.top(); queMax.pop(); i++; } } }使用自定义堆的堆排序：
void sortHeap(vector<int>& nums) { int n = nums.size(); vector<int> temp; for (auto p : nums) heapInsert(temp, p); while (n > 0) heapDelete(temp, n); nums = temp; }每一次删除堆顶后，堆内的元素顺序，n为剩余元素个数 ：
希尔排序从数组中每隔k项选出一个子序列a[i],a[i+k],a[i+2k]，进行排序，这样子序列中有序。再减小k的值，每个k值对应一趟，只要最终k=1，那么整个数组有序。不同k值组成的序列叫做增量序列h1,h2,...,ht；只要h1=1，数组最终有序，但是不同的增量序列的选取对算法性能的影响很大。每一轮希尔排序可以看作是为数组的子序列进行插入排序，最后一轮hk=1是插入排序。因为插入排序的时间复杂度被输入数组的有序性影响，所以希尔排序相当于先对数组子序列进行排序，使数组部分有序，再执行插入排序。 如输入数组arr{81,94,11,96,12,35,17,95,28,58,41,75,15} size=13; gap1=13/2=6; 取arr[0],arr[6],arr[12]做插入排序 取arr[1],arr[7],做插入排序 ... gap2=6/2=3 取arr[0],arr[3],arr[6],arr[9],arr[12]做插入排序。注意arr[0],arr[6],arr[12]在gap=6时已经排序完成，是有序数组 因此此处的插入排序时间复杂度降低 同理，取arr[1],arr[4],arr[7],arr[10]做插入排序。 ... gapn=1 gap的最后一个值一定要保证为1 否则希尔排序不能保证最后数组有序 当gap=1时，希尔排序退化成插入排序 但是由于前面的gap已经让数组部分有序 因此此处插入排序的时间复杂度也被降低了。 常用的但不是最好的ht=N/2，h[k]=h[k+1]/2
void shellSort(vector<int>& arr, bool method) { int size = arr.size(); if (!method)//升序排序 for (int gap = size / 2; gap >= 1; gap = gap / 2)//取常用ht=size/2，hk=hk+1/2 { for (int i = gap; i < size; i++)//每一轮希尔排序是插入排序的变体 当hk=1时为插入排序 { int k = i; for (int j = i - gap; j >= 0; j -= gap) { if (arr[k] < arr[j]) { int temp = arr[k]; arr[k] = arr[j]; arr[j] = temp; k = j; } } } cout << "gap=" << gap << ": "; for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } else for (int gap = size / 2; gap >= 1; gap = gap / 2) { for (int i = gap; i < size; i++) { int k = i; for (int j = i - gap; j >= 0; j -= gap) { if (arr[k] > arr[j]) { int temp = arr[k]; arr[k] = arr[j]; arr[j] = temp; k = j; } } } cout << "gap=" << gap << ": "; for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } } #include<iostream> #include<vector> #include<queue> //for priority_queue #include<functional> //for greater<> using namespace std; void insertionSort(vector<int>&,bool method=false); void heapSort(vector<int>&,bool method=false); void shellSort(vector<int>&, bool method=false); int main() { vector<int>arr{ 81,94,11,96,12,35,17,95,28,58,41,75,15 }; cout << "Original array:" << endl; for (auto itr = arr.begin(); itr != arr.end(); itr++) cout << *itr << " "; cout << endl; cout << "shellSort increase:" << endl; shellSort(arr);//升序排序 cout << "shellSort increase result:" << endl; for (auto itr = arr.begin(); itr != arr.end(); itr++) cout << *itr << " "; cout << endl; cout << "shellSort decrease:" << endl; shellSort(arr, true);//降序排序 cout << "shellSort decrease result:" << endl; for (auto itr = arr.begin(); itr != arr.end(); itr++) cout << *itr << " "; cout << endl; return 0; }假设有两个已排序数组，将他们合并成一个数组，最终得到是一个有序数组。假如数组只有一个数字，那么它自然是有序的。因此输入数组的有序序列是将输入数组拆分成两个数组，对这两个数组进行排序并合并的结果。而拆分出的两个子数组同样可以执行这样的操作。合并两个有序数组时使用三个指针，如合并增序数组A={1,2,5,9},B={3,6,7,10}，pta遍历A，ptb遍历B，ptc遍历合并后的数组C。如果在pta和ptb都合法时，比较pta和ptb指向的值，小的数值放入C，ptc++，小的指针++，若pta到达A的结尾，则顺序放入ptb直到B的结尾，否则顺序放入pta直到A的结尾。
vector<int> merge(vector<int>&arr1, vector<int>&arr2, bool method) { int size1 = arr1.size(); int size2 = arr2.size(); int size = size1 + size2; vector<int> res(size, 0); if (!method) { int pt1 = 0, pt2 = 0, pt = 0; while (pt < size) { if (pt1 == size1&&pt2 < size2) { res[pt] = arr2[pt2]; pt2++; pt++; } else if (pt1 < size1&&pt2 == size2) { res[pt] = arr1[pt1]; pt1++; pt++; } else { if (arr1[pt1] < arr2[pt2]) { res[pt] = arr1[pt1]; pt1++; } else { res[pt] = arr2[pt2]; pt2++; } } pt++; } } else { int pt1 = 0, pt2 = 0, pt = 0; while (pt < size) { if (pt1 == size1&&pt2 < size2) { res[pt] = arr2[pt2]; pt2++; } else if (pt1 < size1&&pt2 == size2) { res[pt] = arr1[pt1]; pt1++; } else { if (arr1[pt1] > arr2[pt2]) { res[pt] = arr1[pt1]; pt1++; } else { res[pt] = arr2[pt2]; pt2++; } } pt++; } } return res; } #include<iostream> #include<vector> #include<queue> //for priority_queue #include<functional> //for greater<> using namespace std; void insertionSort(vector<int>&,bool method=false); void heapSort(vector<int>&,bool method=false); void shellSort(vector<int>&, bool method=false); vector<int> merge(vector<int>&, vector<int>&,bool method = false); int main() { vector<int> arr1{ 9,4,1 }; vector<int> arr2{ 7,5,3,2 }; vector<int> arr = merge(arr1, arr2,true); int size = arr.size(); for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; arr1={ 1,4,9 }; arr2 = { 2,3,5,7 }; arr = merge(arr1, arr2); for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; return 0; }如有输入数组arr{24,13,26,1,2,27,38,15} 拆分1 arr={24,13,26,1}+{2,27,38,15}=A+B 拆分2 A={24,13}+{26,1}=C+D B={2,27}+{38,15}=E+F 拆分3 C={14}+{13}=C1+C2,D={26}+{1}=D1+D2,E={2}+{27}=E1+E2,F={38}+{15}=F1+F2 合并3 C={13,24},D={1,26},E={2,27},F={15,38} 合并2 A={1,13,24,26} B={2,15,27,38} 合并1 arr={1,2,13,15,24,26,27,38}即为排序结果
桶排序不适用于任意数组输入，必须有附加信息，比如已知输入数组的上界。例如，输入arr[i]是小于M的非负数，此时可以使用桶排序。建立大小为M的数组，称为M个桶，初始时每个桶为0，代表桶是空的。遍历输入数组，令数字对应桶的个数+1，最后顺序打印出非空的桶即可，桶排序通过建立待排序数组中的数字和桶的对应关系，并记录这个数字出现的次数。arr[i]为输入待排序数组,大小为n，范围为0-M-1,bucket[M]为桶，则桶的索引i与arr[i]对应，bucket[k]，k对应数组中的数字arr[i]，bucket[k]的值为该数字出现的次数。最后顺序打印桶中非空的元素，若出现多次则需打印对应次数，即为输入数组的有序序列。桶的索引范围要大于数组中的数字，才能保证有序序列的完整性，即index_min<=arr_min&&index_max>=arr_max。
输入一个字符串，根据ASCII码进行重新排序。
void radixSortChar(string& str,bool method) { int size = str.size(); int bucketSize = 256;//字符最多有256个 vector<char> bucket(bucketSize, 0); for (int i = 0; i<size; i++) bucket[str[i]]++;//记录每个字符出现次数 str.clear();//清空输入字符串 为更新做准备 if(!method) for (int i = 0; i<bucketSize; i++)//顺序遍历桶 字符串升序输出 for (int j = 0; j<bucket[i]; j++) str.push_back(i); else for (int i = bucketSize-1; i>=0; i--)//倒序遍历桶 字符串降序输出 for (int j = 0; j<bucket[i]; j++) str.push_back(i); } #include<iostream> //for cout endl #include<vector> //for vector #include<string> //for string using namespace std; void radixSortChar(string& str, bool method = false);//str待排序字符串 默认false升序 true降序 int main() { string arr{ "bdecdAEGRD" };//测试用例 radixSortChar(arr);//升序 cout << arr << endl; radixSortChar(arr, true);//降序 cout << arr << endl; return 0; }上文中桶排序的缺点是显而易见的，因为桶必须是连续的，当输入数组的数字大范围不连续，如1和22222222，尽管只有两个输入数字，却至少需要22222222（1-22222222）个桶，遍历数组不会花费很多时间，因为数组个数不多，但是在遍历桶时，也会因为桶的数目过多而浪费很多的时间。因此桶排序只适合数值范围小的排序，如字符按照ascii码排序，因此字符最多256个，因此不会浪费太多储存空间，遍历桶也不会浪费太多时间。 基数排序的算法是多趟的桶排序，考虑输入数字为0~b^p-1的任意子集；b^p-1可能会很大，但是合理选取b后，p的值不会很大，因此对输入数字最多进行p趟桶排序即可获得输入数组的排序，p的不同值对应输入数字最高位到最低位的数字。比如取b=10，对应十进制数字，那个p的取值对应十进制数字个位，十位，百位...上的数字，如果数字小则前移对应升序，如果数字大则前移对应降序，从高位到低位遍历还是从低位到高位遍历不影响最终的排序结果。因为桶排序适用于字符排序，那么很自然的相同基数排序可以解决字符串的排序问题（ascii码顺序），当然对于传统的数值排序也适用。
int型数字，最大32位，这里只考虑非负数，则除去最高位的正负标志位，最大32位。按照从最低位到最高位的顺序进行桶排序，即可得到基数排序后的有序序列。按最低位到最高位遍历每个数字（不要使用最高位到最低位，因为不确定最高位的位数），影响排序（升序还是降序）的因素是从桶中取出数字更新arr的顺序，如果与位数遍历的顺序相同（低位到高位）从小桶（0）到大桶（9），那么是升序，反之是降序。
void radixSortInt(vector<int>&arr, int b, bool method) //arr为待排序数组 b为基数 如十进制为10，method默认false升序，true降序。 { int size = arr.size(); vector<vector<int>> bucket(b);//因为某一位相同而其他位可能不同 if(!method)//所以每个桶中不是存储出现次数 而是该位相同的所有数字 for (int i = 1; i < 32; i++)//遍历每一位int型最高32位 { for (int j = 0; j < size; j++)//遍历每个数字 { bucket[arr[j]/int(pow(b,i-1))].push_back(arr[j]);//将当前位的值相同的放入同一个桶中 } arr.clear();//arr清空 储存当前位排序后的顺序 for (int j = 0; j < b; j++)//顺序将桶中元素取出 当前位排序后的升序序列 { for (int k = 0; k < bucket[j].size(); k++) arr.push_back(bucket[j][k]); } cout << i << "th: " << endl; for (int j = 0; j < arr.size(); j++) cout << arr[j] << " "; cout << endl; if (bucket[0].size() == size)//说明所有元素都已经到达最高位 break; for (int j = 0; j < b; j++)//注意当更新arr中的值后，将bucket中每个元素清空 bucket[j].clear(); } else for (int i = 1; i < 32; i++)//该位相同的所有数字 { for (int j = 0; j < size; j++)//将数组所有数字根据当前位放入对应桶中 { bucket[arr[j] / int(pow(b, i - 1)) % 10].push_back(arr[j]); } arr.clear();//arr清零为更新做准备 for (int j = b-1; j >= 0; j--)//降序时，从后向前从桶中取出数字更新arr { int size = bucket[j].size(); for (int k = 0; k < size; k++) arr.push_back(bucket[j][k]); } //显示当前位数排序后的arr cout << i << "th: " << endl; for (int j = 0; j < arr.size(); j++) cout << arr[j] << " "; cout << endl; //循环退出条件 因为未给出数字的最高位 以int型32位为界，且当所有数字最高位为0 //即取最高位都落入bucket[0]桶时，代表排序结束 if (bucket[0].size() == size) break; for (int j = 0; j < b; j++)//注意当更新arr中的值后，将bucket中每个元素清空 bucket[j].clear(); } } #include<iostream> //for cout endl #include<vector> //for vector #include<algorithm> //pow() using namespace std; void radixSortInt(vector<int>&arr, int b, bool method = false); //arr待排序数组 b基数十进制则为10 method默认false升序 true降序 int main() { vector<int>arr{ 64,8,216,512,027,729,0,1,343,125 }; int size = arr.size(); cout << "Original array:" << endl; for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << endl; cout << "radixSort increase:" << endl; radixSortInt(arr, 10); cout << "radixSort increase result:" << endl; for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << endl; arr = { 64,8,216,512,027,729,0,1,343,125 }; cout << "radixSort decrease:" << endl; radixSortInt(arr, 10,true); cout << "radixSort decrease result:" << endl; for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << endl; return 0; }基数排序升序： 第一趟桶排序 根据个位数字升序 第二趟桶排序 在个位数字有序的基础上 根据十位数字升序 第三趟桶排序 在个位十位数字有序的基础上 根据百位数字升序 第四趟桶排序 在个十百位数字有序的基础上 根据千位升序 这时所有数字均进入bucket[0]桶，循环退出 同理对于基数排序降序，只有反向从桶中取出数字更新arr，即可得降序排序。 这里判断循环退出是以所有数字最高位为0，即所有数字都在bucket[0]桶作为循环退出条件。因为有多个数字位数相同(case最高位为百位)，所以会出现多计算一次，在处理完百位后，按顺序遍历桶，得到的结果已经是排序序列，但是未达到循环退出条件，所以还会判断千位。但是如果不对数组进行预处理，如求出最大值从而判断最高位等操作的话，只能这样处理。
同整型数字的基数排序，字符串的基数排序是按字符串每一位的字符ASCII码排序，从最低位到最高位遍历字符串放入对应桶中，若按桶从前往后取出更新字符串排序，则为字符串升序排序（ascii码小在前），若按桶从后往前取出字符串更新字符串排序，则为字符串降序排序（ascii码大的在前）。
void radixSortStr(vector<string>&arr,bool method) { int size = arr.size();//字符串个数 int size2 = arr[0].size();//每个字符串字符个数 int bucketSize = 256;//256是考虑所有字符 实际调整 如只有小写字符 //可设置为26 但是要保证字符按照ascii码顺序进入对应桶中 //如bucket[arr[j]-'a'].push_back(arr[j])这样该位为‘a’的进入第一个桶 为‘z’的进入最后一个桶 vector<vector<string>>bucket(bucketSize); if(!method) for (int i = size2-1; i >= 0; i--)//比较字符串的每一位字符 字符共size2位 { for (int j = 0; j < size; j++)//对每一个字符串操作 字符串共size个 bucket[arr[j][i]].push_back(arr[j]); arr.clear(); for (int j = 0; j < bucketSize; j++)//从前向后遍历每个桶 ascii码升序 { int size = bucket[j].size(); for (int k = 0; k < size; k++)//顺序取出每个桶中字符串 arr.push_back(bucket[j][k]); } //打印每一轮（按字符串每一位）桶排序后的数字排序 cout << size2-i << " round: " << endl; for (int j = 0; j < size; j++) cout << arr[j] << " "; cout << endl; for (int j = 0; j < bucketSize; j++) bucket[j].clear(); } else for (int i = size2 - 1; i >= 0; i--)//比较字符串的每一位字符 字符共size2位 { for (int j = 0; j < size; j++)//对每一个字符串操作 字符串共size个 bucket[arr[j][i]].push_back(arr[j]); arr.clear(); for (int j = bucketSize-1; j >= 0; j--)//从前向后遍历每个桶 ascii码升序 { int size = bucket[j].size(); for (int k = 0; k < size; k++)//顺序取出每个桶中字符串 arr.push_back(bucket[j][k]); } //打印每一轮（按字符串每一位）桶排序后的数字排序 cout << size2-i << " round: " << endl; for (int j = 0; j < size; j++) cout << arr[j] << " "; cout << endl; for (int j = 0; j < bucketSize; j++) bucket[j].clear(); } } #include<iostream> //for cout endl #include<vector> //for vector #include<string> //for string using namespace std; void radixSortStr(vector<string>& arr,bool method=false); //arr待排序数组 method默认false升序 true降序 int main() { vector<string>arr{ "aacbd","aasde","bdegs","bdega","nksdj" }; cout << "Original String Array:" << endl; for (auto pt : arr) cout << pt << " "; cout << endl; cout << "RadixSortStr Increase:" << endl; radixSortStr(arr); cout << "RadixSortStr Increase Result:" << endl; for (auto pt : arr) cout << pt << " "; cout << endl; cout << "RadixSortStr Decrease:" << endl; radixSortStr(arr,true); cout << "RadixSortStr Decrease Result:" << endl; for (auto pt : arr) cout << pt << " "; cout << endl; return 0; }如上图所示，i round代表按照第i位将字符串排序并更新arr数组，因为已知字符串长度相同，所以可以确定最后一位，即确定桶排序的次数。每个字符串共5位，因此第5轮桶排序后，字符串有序。注意位数应从字符串末尾开始，如每个string的长度为5，那么应先比较str[4]，根据str[4]更新字符串的排序顺序，再比较str[3],...,直至比较完str[0]。
