算法入门（1）——快速排序_IOS

算法入门（1）——快速排序

下面是用`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';