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

简介: 七大基本排序算法已通过VS2015环境测试可能不是最优算法,但是比基本版更好完整项目GitHub 地址:https://github.com/cugwyman/7-SortsBubbleSort冒泡排序//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);
}
目录
相关文章
|
20小时前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。
|
1天前
|
传感器 算法 数据安全/隐私保护
基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
```markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合,模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略,优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例,旨在最小化未覆盖区域。 ```
|
2天前
|
机器学习/深度学习 算法 计算机视觉
通过MATLAB分别对比二进制编码遗传优化算法和实数编码遗传优化算法
摘要: 使用MATLAB2022a对比了二进制编码与实数编码的遗传优化算法,关注最优适应度、平均适应度及运算效率。二进制编码适用于离散问题,解表示为二进制串;实数编码适用于连续问题,直接搜索连续空间。两种编码在初始化、适应度评估、选择、交叉和变异步骤类似,但实数编码可能需更复杂策略避免局部最优。选择编码方式取决于问题特性。
|
4天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
16 7
|
4天前
|
算法 Python
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
12 0
|
4天前
|
存储 传感器 算法
基于ACO蚁群优化算法的WSN网络路由优化matlab仿真
摘要(Markdown格式): - 📈 ACO算法应用于WSN路由优化,MATLAB2022a中实现,动态显示迭代过程,输出最短路径。 - 🐜 算法模拟蚂蚁寻找食物,信息素更新与蚂蚁选择策略确定路径。信息素增量Δτ += α*τ*η,节点吸引力P ∝ τ / d^α。 - 🔁 算法流程:初始化→蚂蚁路径选择→信息素更新→判断结束条件→输出最优路由。优化WSN能量消耗,降低传输成本。
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战

热门文章

最新文章