首页 > 编程语言 >C++ generate and quick sort in template

C++ generate and quick sort in template

时间:2022-10-14 11:12:56浏览次数:45  
标签:sort arr int high low template quick pivot generate

#pragma once 
 
#include <iostream>
#include <random> 
#include <algorithm>

using namespace std;
 
random_device rd;
mt19937_64 mt(rd());

template<typename T>
T getRandom(T min, T max)
{
    uniform_int_distribution<T> uid(min, max);
    return uid(mt);
}


template<typename T>
void swap(T* left, T* right)
{
    if (*left == *right)
    {
        return;
    }

    T temp = *left;
    *left = *right;
    *right = temp;
}

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

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

void arrayDemo(int len)
{
    uint32_t * arr = new uint32_t[len];
    for (int i = 0; i < len; i++)
    {
        arr[i] = getRandom<uint32_t>(0, UINT32_MAX);
    }

    cout << "Before quick sort:" << endl;
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl << endl;
    cout << "After quick sort:" << endl;
    quickSort<uint32_t>(arr, 0, len - 1);
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl << endl;
    delete[]arr;
}
 
int main()
{
    arrayDemo(1000);
}

 

标签:sort,arr,int,high,low,template,quick,pivot,generate
From: https://www.cnblogs.com/Fred1987/p/16790957.html

相关文章

  • 学习日记--(复习qsort、学习枚举、指针)
    1、两数之和方法一:暴力枚举思路:枚举数组中每一个数,寻找之后的数字是否存在target-x。int*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){for......
  • PySide6:您的第一个QtQuick/QML应用程序
    QML是一种声明性语言,它允许您比使用传统语言更快地开发应用程序。它是设计应用程序UI的理想工具,因为它具有声明性质。在QML中,用户界面被指定为具有属性的对象树。在本教程中......
  • leet Code [34. Find First and Last Position of Element in Sorted Array]
    [34.FindFirstandLastPositionofElementinSortedArray](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)二分法......
  • sorted与sort区别
    使用sorted()排序值开始使用Python排序,首先要了解如何对数字数据和字符串数据进行排序。1.排序数字型数据可以使用Python通过sorted()对列表进行排序。比如定义了一个......
  • python 排序函数--sort()--sorted()
    python中有两种排序方法,list内置sort()方法或者python内置的全局sorted()方法区别为:sort()方法对list排序会修改list本身,不会返回新list。sort()只能对list进行排序。......
  • Java8集合通过流排序,Stream<T> sorted(Comparator<? super T> comparator)
    Java8中,可以通过流的sorted操作对流中的元素排序,sorted操作的参数是Comparator接口,通过传入一个比较函数来实现排序操作,最直接的,就是通过形如(a,b)->{in......
  • 学习日记(qsort)
    1、C语言标准库函数qsort(快速排序)声明在stdlib.h文件中,时间复杂度为n*log(n)voidqsort(void*base(需要排序的目标数组名),size_tnum(参与排序的目标数组元素个数),si......
  • LeetCode148. Sort List
    题意链表排序方法递归代码classSolution{public:ListNode*sortList(ListNode*head){returnsortList(head,nullptr);}ListNode*......
  • 16、Java——QuickHit游戏
    目录​​项目需求​​​​项目环境准备​​​​案例覆盖的技能点​​​​难点分析​​​​项目实现思路​​​​代码展示​​项目需求  (1)QuickHit游戏考验学员键盘输入......
  • shell 知识点补充(2)-重定向/ ; , &&, ||/管线命令/grep/sort/ uniq/wc/tee/tr/col/jo
    1、重定向1.标准输入(stdin):代码为0,使用<或<<;(重写或追加)2.标准输出(stdout):代码为1,使用>或>>;3.标准错误输出(stderr):代码为2,使用2>或2>>;eg:yee@Loon......