博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
快速排序,归并排序
阅读量:4356 次
发布时间:2019-06-07

本文共 2393 字,大约阅读时间需要 7 分钟。

参考 剑指offer的方法,比较简单。

#include<iostream>

#include <vector>
#include <set>
#include <functional>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <list>
#include <map>
#include <stack>
#include <algorithm>
#include<iomanip>
using namespace std;

int RandomInRange(int start, int end)

{
return start + rand() % (end - start+1);
}
int partion(vector<int> &vi, int start, int end)
{
if (start < 0 || end >= vi.size() || start > end)
throw new exception("Invalid Patameter ");
int index = RandomInRange(start, end);
std::swap(vi[index], vi[end]);
int small = start - 1;

for (int i = start; i < end; i++)

{
if (vi[i] < vi[end])
{
//++small;
//if (i != small)
// std::swap(vi[i], vi[small]);
std::swap(vi[i], vi[++small]);
}

}

std::swap(vi[end], vi[++small]);

return small;
}
void QuickSort(vector<int>& vi, int start, int end)
{
if (start == end)
return;

int index = partion(vi, start, end);

if (index > start)

QuickSort(vi, start, index - 1);
if (index < end)
QuickSort(vi, index + 1, end);

}

void QuickSort(vector<int>& vi)
{
QuickSort(vi, 0, vi.size() - 1);
}
//***********************************************
void Merge(vector<int>& vi, vector<int>& tmp, int leftPos, int rightPos, int rightEnd)
{
if (leftPos >= rightPos || rightPos>rightEnd)
return;
int leftEnd = rightPos - 1;
int count = rightEnd - leftPos + 1;
int tmpPos = leftPos;
while (leftPos <= leftEnd && rightPos <= rightEnd)
{
if (vi[leftPos] <= vi[rightPos])
tmp[tmpPos++] = vi[leftPos++];
else
tmp[tmpPos++] = vi[rightPos++];
}
while (leftPos <= leftEnd)
tmp[tmpPos++] = vi[leftPos++];
while (rightPos <= rightEnd)
tmp[tmpPos++] = vi[rightPos++];

for (int i = 0; i < count; i++,rightEnd--)

vi[rightEnd] = tmp[rightEnd];
}
void MergeSort(vector<int>& vi, vector<int>& tmp, int start, int end)
{
if (start >= end)
return;

int mid = (start + end) / 2;

MergeSort(vi, tmp, start, mid);
MergeSort(vi, tmp, mid + 1, end);

Merge(vi, tmp, start, mid + 1, end);

}
void MergeSort(vector<int> vi)
{
vector<int> tmp(vi.size());
MergeSort(vi, tmp, 0, vi.size() - 1);
for (auto i : vi)
cout << i << " ";
cout << endl;
}
int main(int argc, char** args)
{

vector<int> vi = { 1, 5, 3, 4, 6, 9, 2, 7, 8 };

for (auto i : vi)
cout << i << " ";
cout << endl;
MergeSort(vi);
QuickSort(vi);
for (auto i : vi)
cout << i << " ";
cout << endl;
system("pause");
return 0;
}

 

转载于:https://www.cnblogs.com/Oscar67/p/9588008.html

你可能感兴趣的文章
一款纯css3实现的机器人看书动画效果
查看>>
加班与效率
查看>>
轻量级Modal模态框插件cta.js
查看>>
MyEclipse下SpringBoot+JSP整合过程及踩坑
查看>>
重定向和管道
查看>>
实验五
查看>>
STL学习笔记(第二章 C++及其标准程序库简介)
查看>>
Operator_countByValue
查看>>
Java 日期往后推迟n天
查看>>
Web应用漏洞评估工具Paros
查看>>
Git 和 Github 使用指南
查看>>
20180925-4 单元测试
查看>>
mysql的数据存储
查看>>
[转载] Activiti Tenant Id 字段释疑
查看>>
[Java 8] (8) Lambda表达式对递归的优化(上) - 使用尾递归 .
查看>>
SQL Server-聚焦移除Bookmark Lookup、RID Lookup、Key Lookup提高SQL查询性能
查看>>
最小权限的挑战
查看>>
jquery 视觉特效(水平滚动图片)
查看>>
SVG笔记
查看>>
linux下使用dd命令写入镜像文件到u盘
查看>>