首页 > 其他分享 >cpp generate random array then sort by quick sort

cpp generate random array then sort by quick sort

时间:2023-04-05 21:36:52浏览次数:38  
标签:sort std arr int random len high low quick

#include <chrono>
#include <ctime>
#include <iomainp> #include <iostream> #include <random> #include <sstream>

std::string get_time_now() { std::chrono::time_point<std::chrono::high_resolution_clock> now = std::chrono::high_resolution_clock::now(); time_t raw_time = std::chrono::high_resolution_clock::to_time_t(now); struct tm tm_info = *localtime(&raw_time); std::stringstream ss; std::chrono::seconds seconds = std::chrono::duration_cast<std::chrono::seconds>(now.time_since_epoch()); std::chrono::milliseconds mills = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch()); std::chrono::microseconds micros = std::chrono::duration_cast<std::chrono::microseconds>(now.time_since_epoch()); std::chrono::nanoseconds nanos = std::chrono::duration_cast<std::chrono::nanoseconds>(now.time_since_epoch()); ss << std::put_time(&tm_info, "%Y%m%d%H%M%S") << std::setw(3) << std::setfill('0') << std::to_string(mills.count() - seconds.count() * 1000) << std::setw(3) << std::setfill('0') << std::to_string(micros.count() - mills.count() * 1000) << std::setw(3) << std::setfill('0') << std::to_string(nanos.count() - micros.count() * 1000); return ss.str(); }
template <typename T>
T gen_random(T min, T max)
{
    std::random_device rd;
    std::mt19937_64 mt(rd());
    std::uniform_int_distribution<T> uid(min, max);
    return uid(mt);
}

template <typename T>
void print_t_array(T *arr, const int &len)
{
    for (int i = 0; i < len; i++)
    {
        std::cout << i << "," << arr[i] << "\t";
    }
    std::cout << std::endl;
}
template <typename T>
void swap(T *left, T *right)
{
    T temp = *left;
    *left = *right;
    *right = temp;
}

template<typename T>
void gen_T_array_len(T *arr,T min,T max,const int&len)
{
    for(int i=0;i<len;i++)
    {
        arr[i]=gen_random<std::uint32_t>(0,UINT32_MAX);
    }
}


template<typename T>
int get_partition(T *arr,int low,int high)
{
    int pivot=arr[high];
    int i=low-1;
    for(int j=low;j<high;j++)
    {
        if(arr[j]<pivot)
        {
            i=i+1;
            swap(&arr[i],&arr[j]);
        }
    } 
    swap(&arr[i+1],&arr[high]);
    return i+1;
}

template<typename T>
void quick_sort_T(T *arr,int low,int high)
{
    if(low<high)
    {
        int pivot=get_partition(arr,low,high);
        quick_sort_T(arr,low,pivot-1);
        quick_sort_T(arr,pivot+1,high);
    }
}


template<typename T>
int get_partition(T *arr,int low,int high)
{
    int pivot=arr[high];
    int i=low-1;
    for(int j=low;j<high;j++)
    {
        if(arr[j]<pivot)
        {
            i=i+1;
            swap(&arr[i],&arr[j]);
        }
    } 
    swap(&arr[i+1],&arr[high]);
    return i+1;
}

template<typename T>
void quick_sort_T(T *arr,int low,int high)
{
    if(low<high)
    {
        int pivot=get_partition(arr,low,high);
        quick_sort_T(arr,low,pivot-1);
        quick_sort_T(arr,pivot+1,high);
    }
}

void quick_sort_len(const int &len) { uint32_t *arr = new uint32_t[len]; gen_T_array_len<std::uint32_t>(arr, 0, UINT32_MAX, std::cref(len)); std::cout << "Before quick sort:" << std::endl; print_t_array<std::uint32_t>(arr, std::cref(len)); std::cout << "\n\nAfter quick sort:" << std::endl; quick_sort_T<std::uint32_t>(arr, 0, len - 1); print_t_array<std::uint32_t>(arr, std::cref(len)); delete[] arr; std::cout << get_time_now() << ",finish in " << __FUNCTION__ << std::endl; }
int main(int args, char **argv) { quick_sort_len(atoi(argv[1])); }
 

 

g++ -g -std=c++2a -I. *.cpp -o h1 -luuid

 

 

 

The key located at get the pivot of array iterately

template <typename T>
int get_partition(T *arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i = i + 1;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

 

标签:sort,std,arr,int,random,len,high,low,quick
From: https://www.cnblogs.com/Fred1987/p/17290964.html

相关文章

  • sort,sorted,reverse,reversed的区别
    python中sort,sorted,reverse,reversed的区别简单的说以上四个内置函数都是排序。对于sort和reverse都是list列表的内置函数,一般不传参数,没有返回值,会改变原列表的值。而sorted和reversed是python内置函数,需要传参数,参数可以是字符串,列表,字典,元组,不管传的参数是什么sorted返回的......
  • 国内市场主流BI排名,瓴羊Quick BI多个领域领先
    这些年,随着大数据、互联网等信息技术的持续发展,商业智能BI市场也迎来了大爆发。为了满足企业数字化的需求,国内市场上涌现出了各种BI工具,像是Tableau、微软PowerBI、瓴羊QuickBI、FineBI等。众多选择让一些企业在进行BI采购选型的时候没了方向,不知道该选哪个品牌才好。那么,市场上......
  • 随机生成工具 RandomValueUtil
    packageentity;/*****@Author:www.itheima.com*@Description:itheima*****/publicclassRandomValueUtil{publicstaticStringbase="abcdefghijklmnopqrstuvwxyz0123456789";privatestaticStringfirstName="赵钱孙李周吴郑王冯陈褚卫蒋沈......
  • SearchInRotatedSortedArray
    packageBisectionMethod;/***33.搜索旋转排序数组*在传递给函数之前,nums在预先未知的某个下标k(0<=k<nums.length)上进行了旋转,*使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]](下标从0开始计数)。*例如,[0,1,2,4,5......
  • Hello QuickJS
    #include"quickjs.h"#include"quickjs-libc.h"#include<string.h>JSRuntime*QJSRuntime=nullptr;JSContext*QJSContext=nullptr;JSContext*CreateQJSContext(JSRuntime*InRuntime){JSContext*RetVal=JS_NewContext(QJSR......
  • 解决tabix建索引报错[E::hts_idx_push] Unsorted positions on sequence #
    当我对两个基因型文件位置取交集,并重新生成两个vcf:$bcftoolsview-Roverlap.lstvariant.filter.vcf.gz-Oz-o300.vcf.gz出现如下错误:$tabix300.vcf.gz[E::hts_idx_push]Unsortedpositionsonsequence#4:29013869followedby29013853tbx_index_buildfailed:300.......
  • D. Binary String Sorting
    Problem-D-Codeforces枚举/线性dp枚举做法:枚举每个点,满足条件左边全是0右边全是1取每个点花费中的最小值#include<bits/stdc++.h>usingnamespac......
  • 创建桌面快捷方式 Add items to Ubuntu 12.04 Unity Launcher (quicklaunch)
    AdditemstoUbuntu12.04UnityLauncher(quicklaunch)TherecentupgradetoUbuntu12.04PrecisePangolinleftmesomewhathangingwhenitcomestocreatinglau......
  • Quick install Chinese input method on Ubuntu
    QuickinstallChineseinputmethodonUbuntu7.04A.ToinstallChineseinputfcitxthroughwebupdate1.Clickapplicationprogramtabandthenclickrootterm......
  • 吃巧克力,容器vector、map,容器适配器 priority_queue,算法sort排序
     #include<algorithm>#include<queue>#include<map>#include<vector>#include<iostream>usingnamespacestd;structchocolate{longlonga;//价......