1. Toy模板网首页
  2. > Toy博客

C++ OJ题测试—排序算法效率

10月前 作者：Han同学 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了C++ OJ题测试—排序算法效率。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

 目录

OJ链接

一、直接插入排序

二、希尔排序

三、直接选择排序

常规： 

第二种：

四、 堆排序

五、冒泡排序

六、快速排序

使用C++ sort函数

C语言思路：

三路划分优化效率

七、归并排序

八、计数排序

OJ链接

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​ 

一、直接插入排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i=0;i<nums.size()-1;i++)
        {
            int end=i;
            int tmp=nums[i+1];
            while(end>=0)
            {
                if(nums[end]>tmp)
                {
                    nums[end+1]=nums[end];
                    --end;
                }
                else
                    break;
            }
            nums[end+1]=tmp;
        }
        return nums;
    }
};

 

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

二、希尔排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int gap=nums.size();
        while(gap>1){
            gap=gap/3+1;
            for(int i=0;i<nums.size()-gap;i++){
                int end=i;
                int tmp=nums[end+gap];
                while(end>=0){
                    if(nums[end]>tmp){
                        nums[end+gap]=nums[end];
                        end-=gap;
                    }
                    else
                        break;
                }
                nums[end+gap]=tmp;
            }
        }
        return nums;
    }
};

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

三、直接选择排序

常规： 

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int i,j,minIndex,temp;
        for(i=0;i<nums.size()-1;i++){
            minIndex=i;
            for(j=i+1;j<nums.size();j++){
                if(nums[j]<nums[minIndex])
                    minIndex=j;
            }
            temp=nums[i];
            nums[i]=nums[minIndex];
            nums[minIndex]=temp;
        }
        return nums;
    }
};

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​ 

 第二种：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int begin=0,end=nums.size()-1;
        while(begin<end){
            int maxi=begin,mini=begin;
            for(int i=begin;i<=end;i++){
                if(nums[i]>nums[maxi])
                    maxi=i;
                if(nums[i]<nums[mini])
                    mini=i;
            }
            swap(nums[begin],nums[mini]);
            if(begin==maxi)
                maxi=mini;
            swap(nums[maxi],nums[end]);
            ++begin;
            --end;
        }
        return nums;
    }
};

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

四、 堆排序

class Solution {
public:
    void AdjustDown(vector<int>& a,int n,int parent)
    {
        int child=parent*2+1;
        while(child<n){
            if(child+1<n&&a[child+1]>a[child])
                ++child;
            if(a[child]>a[parent]){
                swap(a[child],a[parent]);
                parent=child;
                child=parent*2+1;
            }
            else{
                break;
            }
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        for(int i=(nums.size()-1-1);i>=0;i--){
            AdjustDown(nums,nums.size(),i);
        }
        int end=nums.size()-1;
        while(end>0){
            swap(nums[0],nums[end]);
            AdjustDown(nums,end,0);
            --end;
        }
        return nums;
    }
};

 C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

五、冒泡排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int j = 0; j < nums.size(); ++j){
            bool exchange = false;
            for (int i = 1; i < nums.size() - j; i++)
            {
                if (nums[i - 1] > nums[i])
                {
                    int tmp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = tmp;
    
                    exchange = true;
                }
            }
    
            if (exchange == false)
            {
                break;
            }
        }
        return nums;
    }
};

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

六、快速排序

使用C++ sort函数

sort函数是C++标准库中提供的通用排序函数，用于对容器中的元素进行排序。它可以对各种容器（如数组、向量、列表等）中的元素进行排序，包括内置类型和自定义类型。

sort函数的声明如下：

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
  • first：表示排序范围的起始迭代器，指向要排序的第一个元素。
  • last：表示排序范围的结束迭代器，指向要排序的最后一个元素的下一个位置。

sort函数使用的是一种快速排序或归并排序的变体算法，具体取决于实现。它会根据元素的比较运算符（<）来确定元素的顺序。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums;
    }
};

 C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++

 

C语言思路：

class Solution {
public:
    int GetMidIndex(vector<int>& a, int left, int right)
    {
        int mid = (left + right) >> 1;
        if (a[left] < a[mid])
        {
            if (a[mid] < a[right])
            {
                return mid;
            }
            else if (a[left] < a[right])
            {
                return right;
            }
            else
            {
                return left;
            }
        }
        else // a[left] > a[mid]
        {
            if (a[mid] > a[right])
            {
                return mid;
            }
            else if (a[left] > a[right])
            {
                return right;
            }
            else
            {
                return left;
            }
        }
    }
    void QuickSort(vector<int>& a, int begin, int end)
    {
        if (begin >= end)
            return;
    
        int keyi = PartSort3(a, begin, end);
        QuickSort(a, begin, keyi - 1);
        QuickSort(a, keyi + 1, end);
    }
    
    int PartSort3(vector<int>& a, int left, int right)
    {
        int midi = GetMidIndex(a, left, right);
        swap(a[left], a[midi]);
    
        int prev = left;
        int cur = left + 1;
        int keyi = left;
        while (cur <= right){
            if (a[cur] < a[keyi] && ++prev != cur){
                swap(a[prev], a[cur]);
            }
            ++cur;
        }
       swap(a[prev], a[keyi]);
        keyi = prev;
        return keyi;
    }
    vector<int> sortArray(vector<int>& nums) {
        QuickSort(nums,0,nums.size()-1);
        return nums;
    }
};

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​ 

三路划分优化效率

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​ 

class Solution {
public:
    int GetMidIndex(vector<int>& a, int left, int right)
    {
        int mid = left + (rand()%(right-left));
        if (a[left] < a[mid])
        {
            if (a[mid] < a[right])
            {
                return mid;
            }
            else if (a[left] < a[right])
            {
                return right;
            }
            else
            {
                return left;
            }
        }
        else // a[left] > a[mid]
        {
            if (a[mid] > a[right])
            {
                return mid;
            }
            else if (a[left] > a[right])
            {
                return right;
            }
            else
            {
                return left;
            }
        }
    }

    void QuickSort(vector<int>& a, int begin, int end)
    {
        if (begin >= end)
            return;

        int left = begin;
        int right = end;
        int cur = left + 1;

        int midi = GetMidIndex(a, left, right);
        swap(a[left], a[midi]);
        int key = a[left];

        while (cur <= right)
        {
            if (a[cur] < key)
            {
                swap(a[left], a[cur]);
                ++left;
                ++cur;
            }
            else if (a[cur] > key)
            {
                swap(a[right], a[cur]);
                --right;
            }
            else
            {
                ++cur;
            }
        }

        QuickSort(a, begin, left - 1);
        QuickSort(a, right + 1, end);
    }

    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(0));

        QuickSort(nums, 0, nums.size() - 1);

        return nums;
    }
};
  1.  GetMidIndex：这个方法用于在快速排序的过程中选择一个"基准"元素。它首先随机选择一个索引mid，然后比较数组a在left、mid和right这三个位置的元素，返回这三个元素中的中位数的索引。这种方式可以有效地避免在处理近乎有序的数组时，快速排序退化为O(n^2)的情况。

  2. QuickSort：这是快速排序的主要方法。它首先调用GetMidIndex方法获取基准元素的索引，然后将基准元素与数组的第一个元素交换位置，接着遍历数组，将小于基准的元素放到左边，大于基准的元素放到右边，等于基准的元素不动。最后，递归地对基准元素左边和右边的子数组进行同样的操作。 

  3. sortArray：这是对外的接口方法，它首先初始化随机数种子，然后调用QuickSort方法对输入的数组nums进行排序，最后返回排序后的数组。

这段代码的主要优点是它使用了随机化的快速排序算法，可以在平均情况下达到O(n log n)的时间复杂度，而且它的空间复杂度为O(log n)，因为它只需要递归调用栈的空间。

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

七、归并排序

class Solution {
public:
    void InsertSort(vector<int>& a, int begin, int end)
    {
        for(int i=begin+1; i<=end; i++)
        {
            int tmp=a[i];
            int j=i;
            while(j>begin && a[j-1]>tmp){
                a[j]=a[j-1];
                j--;
            }
            a[j]=tmp;
        }
    }
    void _MergeSort(vector<int>& a,int begin,int end,vector<int>& tmp)
    {
        if (begin >= end) {
            return;
        }
        if (end - begin + 1 < 10){
	    	InsertSort(a, begin, end);
	    	return;
	    }
        int mid=(begin+end)/2;
        _MergeSort(a,begin,mid,tmp);
        _MergeSort(a,mid+1,end,tmp);
        int begin1=begin,end1=mid;
        int begin2=mid+1,end2=end;
        int i=begin;
        while(begin1<=end1&&begin2<=end2)
        {
            if(a[begin1]<a[begin2])
                tmp[i++]=a[begin1++];
            else
                tmp[i++]=a[begin2++];
        }
        while(begin1<=end1)
            tmp[i++]=a[begin1++];
        while(begin2<=end2)
            tmp[i++]=a[begin2++];
        for (i = begin; i <= end; i++)
        {
            a[i] = tmp[i];
        }
    }
    vector<int> sortArray(vector<int>& nums)
    {
         vector<int> tmp(nums.size());
        _MergeSort(nums,0,nums.size()-1,tmp);
        return nums;
    }
};

C++ OJ题测试—排序算法效率,C++,排序算法,算法,c++​

八、计数排序

class Solution {
public:
    
    vector<int> sortArray(vector<int>& nums)
    {
        // 找到数组中的最大值和最小值
        int minVal = INT_MAX, maxVal = INT_MIN;
        for (int num : nums) {
            minVal = min(minVal, num);
            maxVal = max(maxVal, num);
        }
        
        // 统计每个元素出现的次数
        vector<int> count(maxVal - minVal + 1, 0);
        for (int num : nums) {
            count[num - minVal]++;
        }
        
        // 根据统计结果重新构造排序后的数组
        vector<int> sortedArray;
        for (int i = 0; i < count.size(); i++) {
            for (int j = 0; j < count[i]; j++) {
                sortedArray.push_back(i + minVal);
            }
        }
        
        return sortedArray;
    }
};
  • 当我们使用计数排序算法时，我们首先需要找到待排序数组中的最大值和最小值。这是为了确定计数数组的大小，以及后续构造排序后的数组时的索引范围。
  • 接下来，我们创建一个计数数组 count，其大小为 maxVal - minVal + 1，其中 maxVal 是数组中的最大值，minVal 是数组中的最小值。计数数组用于统计每个元素出现的次数。
  • 然后，我们遍历待排序数组 nums，对于每个元素 num，我们将其在计数数组中对应的位置的值加1，表示该元素出现了一次。
  • 接着，我们根据统计结果重新构造排序后的数组 sortedArray。我们从计数数组的第一个位置开始遍历，对于每个计数数组的索引 i，我们将其对应的值 count[i] 表示的元素值（即 i + minVal）按照出现次数依次添加到 sortedArray 中。
  • 最后，我们返回排序后的数组 sortedArray。

计数排序算法的时间复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是待排序元素的范围。由于计数排序是一种稳定的排序算法，它可以在线性时间内完成排序。文章来源地址https://www.toymoban.com/news/detail-767568.html

到了这里，关于C++ OJ题测试—排序算法效率的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C++排序算法：归并排序详解

    C++排序算法：归并排序详解

    一、归并排序 二、基本算法         1、分离         2、合并         3、图片讲解 三、代码实现         1、分离函数         2、合并函数          3、完整代码          4、样例 四、总结          归并排序 (Merge Sort)是建立在归并操作上的一种既有效又稳

    2024年02月12日
    浏览(40)
  • 【算法篇C++实现】常见排序算法

    【算法篇C++实现】常见排序算法

    算法精炼 每趟从待排序的记录中选出最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。 简单排序处理流程 从待排序序列中，找到最小的元素； 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换； 从余下的 N - 1 个元素中

    2024年02月13日
    浏览(45)

  • 稳定的排序算法：直接插入排序和冒泡排序 （c++实现）

    1.直接插入排序： 插入排序：就是把数组分为左右两个序列，保持左边序列中所有元素是有序的，（当左边序列只有第一个元素时，本身就是有序的，）每次往后移一个，将这个元素保存起来，跟左边的元素进行比较，直到找到第一个小于它的元素后停下，此时的位置是这个

    2024年02月10日
    浏览(45)
  • 【C++】常用排序算法

    【C++】常用排序算法

    2024年02月09日
    浏览(34)
  • C++ 排序算法

    C++ 排序算法

    📖1. sort   对容器内元素进行排序   📖2. random_shuffle     洗牌  指定范围内的元素随机调整次序   📖3. merge   容器元素合并，并整合到另一个容器中   📖4 . reverse     反转指定容器元素 📖在C++语言中，sort（排序）函数是STL（标准库）中的一个函数，它用于将一个数组或

    2024年02月07日
    浏览(24)
  • 排序算法（九大）- C++实现

    排序算法（九大）- C++实现

    目录 基数排序 快速排序  Hoare版本（单趟） 快速排序优化 三数取中  小区间优化 挖坑法（单趟） 前后指针法（单趟） 非递归实现（快排） 归并排序 非递归实现（归并） 计数排序 冒泡排序 插入排序 希尔排序（缩小增量排序） 选择排序（优化版本） 堆排序 实现原理：

    2024年02月13日
    浏览(42)
  • C++算法之冒泡排序

    C++算法之冒泡排序

    试想一下，如果在上体育课的时候，通常学生都会随意站成一列，但是体育老师会帮忙调整学生的站位使得最终顺序是按照身高排序的。那么，回忆一下体育老师是如何调整顺序的呢？ 假设体育老师想将学生从左到右按照身高从矮到高排序。通常情况下，他会从左到右扫视学

    2024年02月14日
    浏览(41)
  • C++算法之快速排序

    C++算法之快速排序

    我们知道，给一个长度为n的序列排序，有三种很简单的算法：选择排序、冒泡排序、插入排序。这三种算法的复杂度均为 O(n^2) 。 如果按照计算机 1 秒钟可以进行 10^8 次计算作为参照，那么它1秒之内可以排序的序列长度大概为 10^4 这个数量级。 然而，在实际生活中， 10^4 级

    2024年02月10日
    浏览(32)

  • 快速排序算法（C++版）

    快速排序（Quick Sort） 是一种常用的高效排序算法，属于分治法的典型代表。它的基本思想是选择一个基准元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有元素小于基准，另一部分的所有元素大于基准，然后对这两部分分别递归地进行排序。因为

    2024年02月05日
    浏览(75)
  • 【C++】数据结构与算法：常用排序算法

    【C++】数据结构与算法：常用排序算法

    😏 ★,° :.☆(￣▽￣)/$: .°★ 😏 这篇文章主要介绍常用排序算法。 学其所用，用其所学。——梁启超 欢迎来到我的博客，一起学习，共同进步。 喜欢的朋友可以关注一下，下次更新不迷路🥞 排序算法是计算机科学中常见的一类算法，用于将一组数据按照特定的顺序进行排

    2024年02月14日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包