排序算法

 1     //归并排序 s_id:起始位置  e_id：结束位置    使用闭区间  等会儿再去看看有没有更方便的方法
 2     vectorint> mergesort(vectorint>& nums, int s_id, int e_id){ 3         if(s_id==e_id)
 4             return vectorint>{nums[s_id]};
 5         vectorint> ans_vec;
 6         int mid = (s_id+e_id)/2;
 7         vectorint> vec_si = mergesort(nums, s_id, mid);
 8         vectorint> vec_sii = mergesort(nums, mid+1, e_id);
 9         //下面对返回的vec_si和vec_sii重新排序 从大到小排序
10         int si = 0;
11         int sii = 0;
12         while(sivec_sii.size()){
13             if(vec_si[si]>vec_sii[sii]){
14                 ans_vec.push_back(vec_si[si]);
15                 si++;
16 
17             }else{
18                 ans_vec.push_back(vec_sii[sii]);
19                 sii++;
20             }
21         }
22         while(sivec_si.size()){
23             ans_vec.push_back(vec_si[si]);
24             si++;
25         }
26         while(siivec_sii.size()){
27             ans_vec.push_back(vec_sii[sii]);
28             sii++;
29         }
30         return ans_vec;
31     };

 1     int  partion(vectorint>& nums, int s_id, int e_id){
 2         //下面开始按照参照的节点分成两部分  参考节点选择 s_id
 3         int refnum = nums[s_id];
 4         int left = s_id;
 5         int right = e_id;
 6         while(leftright){
 7             while(left=nums[right]) right--;
 8             nums[left] = nums[right];
 9             while(left;
10             nums[right] = nums[left];
11         }
12         nums[left] = refnum;
13         return left;
14     }
15     //快速排序算法 许嵩的歌声伴随我写代码  消散了寂寞  谢谢嵩哥
16     //s_id e_id 起始和终止点  使用闭区间
17     void qsort(vectorint>& nums, int s_id, int e_id){
18         //现在的任务是将nums 在 [s_id, e_id]中的元素 按照标定值分成左右两半  左边大于等于标定  右边小于标定
19         if(s_ide_id)
20         {
21             int mid = partion(nums, s_id, e_id);
22             qsort(nums, s_id, mid-1);
23             qsort(nums, mid+1, e_id);
24         }
25     }

 1     //功能函数一  调整大堆树  对这课树有一个要求：只有最上面一个不满足其余的都满足
 2     //所谓大堆树就是根节点是最大的，左右节点的大小并无要求
 3     //node：待调整的节点 绝对位置  比数组中的位置大一
 4     void heapify(vectorint>& nums, int node, int len){
 5         //策略 当前头结点如果没法统治他的两个小节点就将其下放
 6         //采用迭代的方法实现
 7         // int len = nums.size();
 8         while(node*2len){
 9             int max_node = node;
10             //定位简单3树的最大节点位置
11             if(node*21]2-1]) max_node = node*2;
12             if(node*2+11]2+1-1]) max_node = node*2+1;
13             if(max_node==node) break;
14             //交换值
15             int temp = nums[max_node-1];
16             nums[max_node-1] = nums[node-1];
17             nums[node-1] = temp;
18             node = max_node;
19         }
20     }
21     //功能函数二：通过调整堆的方法生成一颗大堆树
22     void getheaptree(vectorint>& nums, int len){
23         //生成的方式是从末端开始向上生成
24         int i = len/2;
25         while(i>0){
26             heapify(nums, i, len);
27             i--;
28         }
29     }