C/C++知识点之c++ 6种排序算法 源代码
顾宇峰 2019-04-10 来源 : 阅读 268 评论 0

摘要:本文主要向大家介绍了C/C++知识点之c++ 6种排序算法 源代码,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍了C/C++知识点之c++ 6种排序算法   源代码,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。

C/C++知识点之c++ 6种排序算法   源代码

// sort.cpp : 定义控制台应用程序的入口点。//#include ""stdafx.h""#include <iostream>using namespace std;template <typename T>void print(T* &arr,int len) {    for (int i=0;i<len;i++)
    {        cout<<*(arr+i)<<' ';
    }    cout<<endl;
}//简单选择排序/*
1.i=[0,len-1),j=[i+1,len-1]数组第i元素值与j元素值比较,大于交换i与j的元素值
2.j+=1 重复第一步直到 j == len
3.i+=1 重复第一步 直到 i == len - 1
*/template <typename T>void select_sort(T* &array,int len){    if (NULL == array)
    {        cout<<""#ERROR  ""<<__FILE__<<""  Line:""<<__LINE__<<"" null point error""<<endl;        return;
    }    for (int i=0; i<len-1; i++)        for (int j=i+1;j<len;j++)            if (array[i] > array[j])
                swap(array[i],array[j]);
}//冒泡排序/*
1.BUBBLE相邻2个元素比较,大则交换
  每一次使得最大的值到最上面
*/template <typename T>void bubble_sort(T* &array,int len){    if (NULL == array)
    {        cout<<""#ERROR  ""<<__FILE__<<""  Line:""<<__LINE__<<"" null point error""<<endl;        return;
    }    bool flag;    for (int i=0; i<len-1; i++)
    {
        flag = true;        for (int j=0;j<len-i-1;j++)            if (array[j] > array[j+1])
            {
                flag = false;
                swap(array[j],array[j+1]);
            }        if (flag) break;
    }
}//插入排序/*
1.i属于[1,len)从i位置往前判断j属于[0,i)
 则后一个元素与前一个相比小于则替换,大于等于退出第一个循环
*/template <typename T>void insert_sort(T* &array,int len){    if (NULL == array)
    {        cout<<""#ERROR  ""<<__FILE__<<""  Line:""<<__LINE__<<"" null point error""<<endl;        return;
    }    for (int i=1; i<len; i++)
    {        for (int j=i;j;j--)
        {            if (array[j] >= array[j-1])                break;
            swap(array[j],array[j-1]);
        }
    }
}//归并排序/*
用到二分思想将数据递归成左右2边得到链表A,B
1.链表A,B用链表归并来得到新的有序链表
*/template <typename T>void merge(T* &array,int left,int mid,int right,T* temp){    int i = left;    int j = mid+1;    int k = 0;    while (i<=mid && j<=right)
    {        if (array[i] > array[j])
            temp[k++] = array[j++];        else
            temp[k++] = array[i++];
    }    //追加最后    while (i <= mid)
        temp[k++] = array[i++];    while (j<=right)
        temp[k++] = array[j++];    //临时变量copy到元素组中
    k = 0;    while(left<=right)//没注意写成k<=right 调试了半天。 数据变成大数考虑是否赋值越界        array[left++] = temp[k++];  
}template <typename T>void merger_sort(T* &array,int left,int right,T* temp){    if (left < right)
    {        int mid = (left + right)/2;
        merger_sort<T>(array,left,mid,temp);//排序左边子序列
        merger_sort<T>(array,mid+1,right,temp);//排序右边子序列
        merge<T>(array,left,mid,right,temp);//左右2边归并
    }
}template <typename T>void merger_sort(T* &array,int len){    if (NULL == array)
    {        cout<<""#ERROR  ""<<__FILE__<<""  Line:""<<__LINE__<<"" null point error""<<endl;        return;
    }
    T* temp = new T[len];
    merger_sort<T>(array,0,len-1,temp);    if (NULL != temp)
    {        delete[] temp;
        temp = NULL;
    }
}//快排/*
(一)挖坑填坑
1.以第一个元素为基准X 初始值前缀i = left 后缀j = right
2.后缀从后往前查找j元素值 < X;i处 赋值 j元素值
3.前缀从前往后查找i元素值 > X;j处 赋值 i元素值
重复第2,3步
(二)分治
1.左边[left,i)执行(一)
2.右边(i,right]执行(一)
递归执行1,2
*/template <typename T>int dig_fil(T* &array,int left,int right){
    T X = array[left];    int i = left;    int j = right;    while (i<j)
    {        while(j>i && array[j] >= X)j--; 
        if (j>i)//只有满足后缀大于前缀才能赋值 不然会数组越界
        {            array[i] = array[j];
            i++;
        }        while(i<j && array[i] < X) i++;        if (i<j)
        {            array[j] = array[i];
            j--;
        }
    }    array[i] = X;    return i;
}template <typename T>void quick_sort(T* &array,int left,int right){    if (left < right)
    {        int mid = dig_fil<T>(array,left,right);
        quick_sort(array,left,mid-1);
        quick_sort(array,mid+1,right);
    }

}template <typename T>void quick_sort(T* &array,int len){    if (NULL == array)
    {        cout<<""#ERROR  ""<<__FILE__<<""  Line:""<<__LINE__<<"" null point error""<<endl;        return;
    }
    quick_sort(array,0,len-1);
}//堆排序/*
堆排序采用完全二叉树 
1.从所有非叶节点中构建最大堆 
2.交换堆顶与最后一个元素
3.对所有[0,len-1)执行第 1,2步
*/template <typename T>void adjust(T* &array,int sign,int len){
    T temp = array[sign];    //每一次循环都更新该父节点为根的完全二叉树最大堆    for (int i = sign * 2 + 1; i < len; i = i * 2 + 1){        if (i + 1 < len && array[i + 1] > array[i])
            i++;        //判断子节点 大于父节点         if (array[i] > temp){            array[sign] = array[i];
            sign = i;
        }
    }    array[sign] = temp;
}template<typename T>void heap_sort(T* &array,int len){    //1.从所有非叶子节点 构建初始大顶堆    for (int i = len / 2 - 1; i >= 0; i--){
        adjust(array, i, len);
    }    //    for (int i = len - 1; i; i--){        //2.交换最大堆 和 相对的最后一个元素
        swap(array[i],array[0]);        //3.重新调整堆结构
        adjust(array, 0, i);
    }
}int _tmain(int argc, _TCHAR* argv[])
{    int a[] = {1,5,4,9,0,2,3,6,8,7};    int* pa = a;    //select_sort<int>(pa,10);    //bubble_sort<int>(pa,10);    //insert_sort<int>(pa,10);    //merger_sort<int>(pa,10);    //quick_sort<int>(pa,10);    //heap_sort(pa,10);
    print<int>(pa,10);
    getchar();    return 0;
}

本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!


本文由 @职坐标 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 0
看完这篇文章有何感觉?已经有0人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论
本文作者 联系TA

2年研发与教育经验

  • 10
    文章
  • 538
    人气
  • 0%
    受欢迎度

已有0人表明态度,0%喜欢该老师!

进入TA的空间
名师指导 直通车
  • 索取资料 索取资料 索取资料
  • 答疑解惑 答疑解惑 答疑解惑
  • 技术交流 技术交流 技术交流
  • 职业测评 职业测评 职业测评
  • 面试技巧 面试技巧 面试技巧
  • 高薪秘笈 高薪秘笈 高薪秘笈
TA的其他文章 更多>>
C/C++知识点之哈希表详解
经验技巧 0% 的用户喜欢
C/C++知识点之container_of 和 offsetof宏
经验技巧 0% 的用户喜欢
C/C++知识点之平衡二叉树
经验技巧 0% 的用户喜欢
C/C++知识点之哈希表—位图
经验技巧 0% 的用户喜欢
C/C++知识点之mac 下xcode配置opencv
经验技巧 0% 的用户喜欢
其他海同名师 更多>>
刘新华
刘新华 联系TA
实力型。激情饱满,对专业充满热情
吴翠红
吴翠红 联系TA
独创“教、学、练、测”循环教学模式
吕益平
吕益平 联系TA
熟悉企业软件开发的产品设计及开发
黄泽民
黄泽民 联系TA
擅长javase核心技术
程钢
程钢 联系TA
擅长大型企业商业网站开发和管理
经验技巧30天热搜词 更多>>

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:13167058313
小职老师的微信号:13167058313

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    ICP许可  沪B2-20190160

站长统计