排序算法实现

• • 实验要求
  • 快排
  • 希尔排序
  • 选择排序

• 编写快排、希尔排序、选择排序，对三维坐标系到原点的距离进行排序

• 文件读写

• 生成多些测试数据，生成一些相同的数据测试算法稳定性(key相同的元素排序后是否保持原来的位置不变)

• 测试三种排序算法速度

从左往右，每次选择当前位置到最后中最小的元素，替换到当前位置

//
//  main.cpp
//  Expriment4_sort_algorithm
//接单子，帮忙写c/c++，java，python代码
//有需要的加qq:783114731
//

#include 
#include
#include
#include
#include
#include 
#include

#define random(a,b) (rand()%(b-a)+double(a))
#define MAX 8000

using namespace std;

const char* in = "/Users/xiaorui/Desktop/in.txt";

typedef struct
{
    int id;
    double key;
    double item[3];
} RecType;

//double AnchorPoint[3];

//计算距离
void distance(vector &a)
{
    for (int i = 0; i &a)
{
    int len = (int) a.size();
    for (int i = 0; i < len - 1; i++)
    {
        int minIndex = i;                     //最小下标
        for (int j = i + 1; j < len; j++) //从未排序的元素找出最小
        {
            if (a[j].key < a[minIndex].key)
                minIndex = j;
        }
        swap(a[i], a[minIndex]);
    }
}


//快排
void quickSort(vector &a, int left, int right)
{
    if (left < right)
    {
        int pivot = a[right].key;
        int i = left - 1;
        for (int j = left; j < right; j++)
        {
            if (a[j].key <= pivot)
            {
                i++;
                swap(a[i], a[j]);
            }
        }
        swap(a[i + 1], a[right]);
        
        int mid = i+1;
        
        quickSort(a, left, mid - 1);
        quickSort(a, mid + 1, right);
    }
}
//希尔排序
void shellSort(vector &a)
{
    int len = (int) a.size();
    for (int g = len / 2; g > 0; g /= 2)
    {
        for (int i = 0; i < g; i++)
        {
            for (int j = i + g; j < len; j = j + g)
            {
                RecType temp = a[j];        //要插入的元素，会被覆盖，先保存
                int index = j - g; //将要对比元素下标
                while (index >= 0 && a[index].key>temp.key)
                    {
                        a[index + g] = a[index]; //后移
                        index -= g;                 //向下走一步
                    }
                a[index + g] = temp; //恢复被替换的值
            }
        }
    }
}

vector signals;

void generateData(int length)
{
    //设置随机数种子
    srand((int)time(0));
    
    FILE* f = fopen(in,"w");
    if(f == nullptr)
    {
        cout<<"打开文件失败"<0)
    {
        RecType r;
        r.id = id;
        r.key = key;
        r.item[0] = item1;r.item[1]=item2;r.item[2] = item3;
        signals.push_back(r);
    }
    fclose(f);
}
void writeData(vector& a,bool nflag,const char* filename)
{
    FILE* f = fopen(filename,"w");
    if(f == nullptr)
    {
        cout<<"打开文件失败"< b(signals);
    //计时
    long t2 = clock();
    //快排
    quickSort(b, 0, (int)b.size()-1);
    //计时结束
    long cost2 = clock() - t2;
    double time2 = (double)cost2/1000000;
    printf("快速排序,耗时=%f秒n", time2);
    //写入文件
    writeData(b, false, "/Users/xiaorui/Desktop/quickSort.txt");
    
    
    //复制一份使用
    vector c(signals);
    //计时
    long t3 = clock();
    //希尔排序
    shellSort(c);
    //计时结束
    long cost3 = clock() - t3;
    double time3 = (double)cost3/1000000;
    printf("希尔排序，耗时=%f秒n", time3);
    //写入文件
    writeData(c, false, "/Users/xiaorui/Desktop/shellSort.txt");
    
    return 0;
}