下面是用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;
RandquickSort(data, left, right);
writeFile(writePath, data);
return 0;
}
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 -= 1;
if (low < high)
data[low++] = data[high];
while (data[low] < tmp&& low < high)
low += 1;
if (low < high)
data[high--] = data[low];
}
data[low] = tmp;
return low;
}
}
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);
int tmp = data[index];
data[index] = data[left];
while (low < high)
{
while (data[high] > tmp && low < high)
high -= 1;
if (low < high)
data[low++] = data[high];
while (data[low] < tmp && low < high)
low += 1;
if (low < high)
data[high--] = data[low];
}
data[low] = tmp;
return low;
}
}
int randNUmber(int left, int right)
{
srand(time(0));
int index = (rand() % (right - left + 1)) + left;
return index;
}
var foo = 'bar';