桶排序注释

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;
struct ListNode{
        explicit ListNode(int i=0):mData(i),mNext(NULL){}//加关键字explicit防止隐式转换
        ListNode* mNext;
        int mData;
};
ListNode* insert(ListNode* head,int val){
        ListNode dummyNode;//作为暂时的无数据的头节点
        ListNode *newNode = new ListNode(val);//新节点
        ListNode *pre,*curr;
        dummyNode.mNext = head;
        pre = &dummyNode;//当前节点的前一个结点
        curr = head;//当前节点
        while(NULL!=curr && curr->mData<=val){//从头结点开始找到第一个大于新值的节点
                pre = curr;
                curr = curr->mNext;
        }
        newNode->mNext = curr;//curr是第一个大于新值的节点
        pre->mNext = newNode;//pre是当前节点的前一节点,现在将pre的指向改为新节点
        return dummyNode.mNext;//返回无数据头结点的下一节点即head
}
ListNode* Merge(ListNode *head1,ListNode *head2){
        ListNode dummyNode;//创建临时节点,不直接用指针创建好处是,可以省去释放空间的操作避免遗忘
        ListNode *dummy = &dummyNode;
        while(NULL!=head1 && NULL!=head2){//归并排序的链表操作
                if(head1->mData <= head2->mData){
                        dummy->mNext = head1;
                        head1 = head1->mNext;
                }else{
                        dummy->mNext = head2;
                        head2 = head2->mNext;
                }
                dummy = dummy->mNext;
        }
        if(NULL!=head1) dummy->mNext = head1;
        if(NULL!=head2) dummy->mNext = head2;
        return dummyNode.mNext;
}
void BucketSort(int n,int arr[]){
        vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));//分成十个桶
        //向量内最后一个参数意思是将其内初始化为空指针可用NULL或nullptr代替
        for(int i=0;i<n;++i){
                int index = arr[i]/BUCKET_NUM;//分桶
                ListNode *head = buckets.at(index);
                buckets.at(index) = insert(head,arr[i]);//将新值的节点插入
        }
        ListNode *head = buckets.at(0);
        for(int i=1;i<BUCKET_NUM;++i){//归并
                head = Merge(head,buckets.at(i));
        }
        for(int i=0;i<n;++i){//将链表内的有序数值重新赋给数组
                arr[i] = head->mData;
                head = head->mNext;
        }
}