#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