算法入门(1)——快速排序
程序员文章站
2022-07-04 09:26:13
下面是用C++写的``快速排序`的函数代码读出和写入文件的函数常规快速排序的函数引入随机基准快速排序的函数快速排序很简单,但是还要记录一下#include#include#include#include#includeusing namespace std;//函数区vector readFile(string fil...
下面是用C++
写的``快速排序`的函数代码
读出和写入文件
的函数
常规
快速排序的函数
引入随机基准
快速排序的函数
快速排序很简单,但是还要记录一下
#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<time.h>
using namespace std;
//函数区
vector<int> readFile(string filePath);//读出文件
void writeFile(string filePath, vector<int> data);//写入文件
int findIndex(vector<int>& data, int left, int right);//寻找基准的下标
void quickSort(vector<int>& data, int left, int right);//快速排序
//改进的快速排序算法
int RandfindIndex(vector<int>& data, int left, int right);
void RandquickSort(vector<int>& data, int left, int right);
int randNUmber(int left, int right);//生成随机数
int main()
{
int data_length;
vector<int> data;
string readPath = "D:\\C++\\Datas\\quickSort.txt";
string writePath = "D:\\C++\\Datas\\result_quickSort.txt";
data = readFile(readPath);//读入带排序数组
data_length = data.size();//整个数组的长度
int left = 0;
int right = data_length - 1;
//quickSort(data, left, right);//第一种排序
RandquickSort(data, left, right);//第二种排序
writeFile(writePath, data);//将排好序的数组写入设置的文件中
return 0;
}
/*
*首先写一个快速排序的算法
* vector<int> data是一个待排序数组
*/
void quickSort(vector<int> &data,int left,int right)
{
if (left < right)
{
int tmp = findIndex(data, left, right);
quickSort(data, left, tmp - 1);
quickSort(data, tmp + 1, right);
}
}
//寻找每次基准应该对应的下标
int findIndex(vector<int>& data, int left, int right)
{
if (left < right)
{
int low = left;//左指针
int high = right;//右指针
int tmp = data[left];//将左边的第一个元素作为基准
while (low < high)
{
while (data[high] > tmp&& low < high)//首先从后往前,如果high对应的元素都大于tmp,就一直往前走
high -= 1;
if (low < high)
data[low++] = data[high];
while (data[low] < tmp&& low < high)//其次从前往后,如果low对应的元素都小于tmp,就一直往后走
low += 1;
if (low < high)
data[high--] = data[low];
}
data[low] = tmp;
return low;
}
}
/*
* 读入和写出文件
* Read:将读出的文件写入 并返回vector<int>
* Write:将vector<int> 数据写入文件当中
*/
vector<int> readFile(string filePath)
{
ifstream infile;
int tmp;
vector<int> data;
infile.open(filePath, ios::in);
if (!infile.is_open())
{
cout << "Read: 文件打开失败!" << endl;
exit(0);
}
while (!infile.eof())
{
infile >> tmp;
data.push_back(tmp);
}
cout << "Read: 成功读出文件" << endl;
return data;
}
void writeFile(string filePath, vector<int> data)
{
ofstream outfile;
outfile.open(filePath, ios::app);//在文件末尾开始写
if (!outfile.is_open())
{
cout << "Write: 打开文件失败" << endl;
exit(1);
}
for (int item : data)
outfile << item << endl;
cout << "Write: 成功写入文件" << endl;
}
/*
* 对常规快速排序算法的改进
* 引入随机基准
*/
void RandquickSort(vector<int>& data, int left, int right)
{
if (left < right)
{
int tmp = RandfindIndex(data, left, right);
quickSort(data, left, tmp - 1);
quickSort(data, tmp + 1, right);
}
}
int RandfindIndex(vector<int>& data, int left, int right)
{
if (left < right)
{
int low = left;//左指针
int high = right;//右指针
int index = randNUmber(left, right);//生成一个随机整数[left,right]
int tmp = data[index];//将左边的第一个元素作为基准
data[index] = data[left];
while (low < high)
{
while (data[high] > tmp && low < high)//首先从后往前,如果high对应的元素都大于tmp,就一直往前走
high -= 1;
if (low < high)
data[low++] = data[high];
while (data[low] < tmp && low < high)//其次从前往后,如果low对应的元素都小于tmp,就一直往后走
low += 1;
if (low < high)
data[high--] = data[low];
}
data[low] = tmp;
return low;
}
}
//生成[left,right]范围内的随机数
int randNUmber(int left, int right)
{
srand(time(0));//设置随机种子,避免前后生成的随机数一致
int index = (rand() % (right - left + 1)) + left;
return index;
}
var foo = 'bar';
本文地址:https://blog.csdn.net/Ai_Math/article/details/108974652