七大基本排序算法C/C++(已优化及测试)-阿里云开发者社区

开发者社区> cugwyman> 正文

七大基本排序算法C/C++(已优化及测试)

简介: 七大基本排序算法 已通过VS2015环境测试 可能不是最优算法,但是比基本版更好 完整项目GitHub 地址:https://github.com/cugwyman/7-Sorts BubbleSort冒泡排序 //BubbleSort冒泡排序,复杂度O(n^2...
+关注继续查看

七大基本排序算法

BubbleSort冒泡排序

//BubbleSort冒泡排序,复杂度O(n^2)
//@param flag       优化算法
void BubbleSort(int *a) {
    int flag = 1;
    for (int i = 0; i < len && flag; i++) {
        flag = 0;       //若flag经j循环后为0,则序列已有序
        for (int j = 1; j < len - i; j++) {
            if (a[j - 1] > a[j]) {
                Swap(a, j - 1, j);
                flag = 1;
            }
        }
    }
}

QuickSort快速排序

//QuickSort快速排序,复杂度O(nlogn)
//@param        pivot   枢纽元
void QuickSort(int *a)//驱动程序
{
    QSort(a, 0, len - 1);
}

void QSort(int *a, int left, int right)
{
    int pivot;
    if ((right - left) > MINI_ARRAY)
    {
        while (left < right)
        {
            pivot = Partition(a, left, right);

            QSort(a, left, pivot - 1);
            //QSort(a, pivot + 1, right);
            left = pivot + 1;       
            //此处优化了QSort(a, pivot + 1, right);递归,缩减一部分代码
        }
    }
    else
    {
        InsertSort(a);//小数组使用插入排序
    }
}

int Partition(int *a, int left, int right)
{
    int temp;
    PickMiddle(a, left, right);//保证枢纽元a[left]为较中间值
    temp = a[left];         //挖坑
    while (left < right) {
        while (left < right && a[right] >= temp) {
            right--;
        }
        a[left] = a[right];//小的值赋到最左

        while (left < right && a[left] <= temp) {
            left++;
        }
        a[right] = a[left];//大的值赋到最右
    }

    a[left] = temp;         //填坑
    return left;
}

void PickMiddle(int *a, int left, int right)
{
    int middle = (left + right) / 2;

    if (a[left] > a[right])
    {
        Swap(a, left, right);
    }
    if (a[middle] > a[right])
    {
        Swap(a, middle, right);
    }
    if (a[left] > a[middle])
    {
        Swap(a, left, middle);
    }
}

InsertSort插入排序

//插入排序,复杂度O(n^2)
//将a[j]插入到前面a[0…j-1]的有序区间
void InsertSort(int *a)
{
    int i, j;

    for (i = 1; i < len; i++)
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)//a[j]前一个数据a[j-1] > a[j]
            Swap(a, j, j + 1);//交换a[j]和a[j-1],再j--直到a[j-1]<= a[j]
}

ShellSort希尔排序

//希尔排序,复杂度O(n^(3/2))  
//分组直接插入排序,又称缩小增量排序
//@param    gap     分组(步长可改,此处为2)
void ShellSort(int *a)
{
    int i, j, gap;
    for (gap = len / 2; gap > 0; gap /= 2)
        for (i = gap; i < len; i++)
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
                Swap(a, j, j + gap);
}

SelectSort选择排序

//选择排序,复杂度O(n^2)  
//从无序区选一个最小的元素直接放到有序区的最后
//@param    min     最小值
void SelectSort(int *a)
{
    int min;

    for (int i = 0; i<len; i++) {
        min = i;
        for (int j = i + 1; j<len; j++) {
            if (a[j] < a[min])
                min = j;
            Swap(a, i, min);
        }
    }
}

HeapSort堆排序

//堆排序 ,复杂度O(nlogn)  
//建堆
void AdjustDown(int *a, int index, int n)
{
    int parent = index;
    int child = 2 * parent + 1;
    while (child < n)
    {
        if (child < n && a[child] < a[child + 1])
            child++;
        if (child < n && a[child] > a[parent])
        {
            Swap(a, parent, child);
            parent = child;
            child = 2 * parent + 1;
        }
        else
            break;
    }
    child = parent;
}
//堆排序
void HeapSort(int *a)
{
    for (int i = len / 2 - 1; i >= 0; --i)
    {
        AdjustDown(a, i, len);
    }
    for (int j = len - 1; j>0; --j)
    {
        Swap(a, j, 0);
        AdjustDown(a, 0, j);
    }
    if (a[0] > a[1])
        Swap(a, 0, 1);
}

MergeSort归并排序

//归并排序(递归式),复杂度O(nlogn),  
//采用分治法( Divide and Conquer),先递归地分解数列,再合并数列

//单趟排序
void Merge(int *a, int *tmp, int first, int mid, int last)
{
    int i = first;
    int j = mid + 1;
    int k = first;
    while (i != mid + 1 && j != last + 1)
    {
        if (a[i] > a[j])
            tmp[k++] = a[j++];
        else
            tmp[k++] = a[i++];
    }
    while (i != mid + 1)
    {
        tmp[k++] = a[i++];
    }
    while (j != last + 1)
    {
        tmp[k++] = a[j++];
    }
    for (i = first; i <= last; i++)
        a[i] = tmp[i];
}

//三数求中法,避免用最后一位比较时最后一位是最大值或用第一位比较时第一位是最小值,降低了时间复杂度。 
int ThreeMid(int *a, int left, int right)//找首位,末尾和中点中中间的数
{
    int mid = left + ((right - left) >> 1);
    while (left < right)
    {
        if (a[left] < a[right])
        {
            if (a[mid] < a[left])
                return left;
            else if (a[right] < a[mid])
                return right;
            else
                return mid;
        }
        if (a[left] > a[right])
        {
            if (a[mid] < a[right])
                return right;
            else if (a[mid] > a[left])
                return left;
            else
                return mid;
        }
    }
    return mid;
}

//归并函数
void MSort(int *a, int *tmp, int first, int last)
{
    int mid;
    if (first < last)
    {
        mid = ThreeMid(a, first, last);
        MSort(a, tmp, first, mid);
        MSort(a, tmp, mid + 1, last);
        Merge(a, tmp, first, mid, last);
    }
}

//驱动函数
void MergeSort(int *a)
{
    int tmp[len];

    MSort(a, tmp, 0, len - 1);
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Renascence架构原理——最优化算法
最优化算法 背景 通过公式生成ADF之后,根据下层函数库的配置,在结构不变的情形下,ADF是可以通过一系列值在0-1之间的参数进行调节的。也即ADF可表示为固定维数n的实数集,因此需要解决的问题就是在给定的目标下,求一组使目标值最大的参数。 max(f(x0,x1,x2,x3,...,xn)),xi∈[0,1] max(f(x_0, x_1, x_2, x_3, .
1125 0
图像算法的工程优化技术
图像算法的工程优化技术 当一个很酷的图像算法实现之后,我们希望集成到软件中去,这时将会遇到最大的拦路虎:性能。 可以想像一下,如果美图秀秀做一个美颜效果要转圈圈转个30秒,还会有多少人用呢。 学术界喜欢推出复杂度更低的算法,去解决性能问题,而在实际工程应用中,对代码的优化和硬件的良好运用效果来得更快更显著,这里就对不改动算法,纯工程方面做性能优化的技术作一个简介。
1319 0
hbase 学习(十四)Facebook针对hbase的优化方案分析
使用hbase的目的是为了海量数据的随机读写,但是在实际使用中却发现针对随机读的优化和gc是一个很大的问题,而且hbase的数据是存储在Hdfs,而Hdfs是面向流失数据访问进行设计的,就难免带来效率的下降。
2263 0
JavaScript ~ 排序算法(选择排序)
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <link type="text/css" rel="stylesheet" href="style/flex.
943 0
神经架构优化(NAO):新的神经架构搜索(NAS)算法
如果你是一名深度学习实践者,你可能发现自己经常会遇到同一个关键问题:我应该为现在的任务选择哪种神经网络架构?
551 0
粒子群优化算法(PSO)之基于离散化的特征选择(FS)(一)
欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习、深度学习的知识! 作者:Geppetto 在机器学习中,离散化(Discretization)和特征选择(Feature Selection,FS)是预处理数据的重要技术,提高了算法在高维数据上的性能。
1195 0
带有通配符的字符串匹配算法-C/C++
日前某君给我出了这样一道题目:两个字符串,一个是普通字符串,另一个含有*和?通配符,*代表零个到多个任意字符,?代表一个任意字符,通配符可能多次出现。写一个算法,比较两个字符串是否相等。
685 0
基于投票的热门计数算法策略
类似基于投票的热门计数算法普遍应用在热门文章,热门评论等场景中, 典型的比如网易和今日头条的评论区,国外比如Hacker News和Reddit的主题排序。
3363 0
+关注
cugwyman
CUG EE本科生,意向机器学习、计算机视觉。github.com/cugwyman
35
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载