[数据结构与算法] 算法设计与分析复习2

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 算法设计与分析复习2 -> 正文阅读

[数据结构与算法]算法设计与分析复习2

n个元素排序

合并排序

分成大小大致相同两组，分别进行排序

void Mergesort(Type a[], int left, int right)
{    if(left < right) {    
    int i = (left + right) /2;
    Mergesort(a, left, i);
    Mergesort(a, i+1, right);
    Merge(a, b, left, i, right);
    Copy(a, b, left, right):
    }
}

Merge和Copy可在O(n)时间内完成。
在这里插入图片描述
合并排序
最坏时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
辅助空间：O(n)

快速排序

两端向中间，关键字较大的交换到后面单元，关键字较小的交换到前面单元。

template<class Type>
void QuickSort(Type a[], int p, int r)
{    if(p < r) [
     int q = Partition(a, p ,r);
     QuickSort(a, p, q-1);
     QuickSort(a, q+1, r);
     }
}

template<class Type>
int Partition(Type a[], int p, int r)
{    int i = p, j = r+1;
     Type x = a[p];
     while(true) {
       while(a[++i] < x);
       while(a[++j] > x);
       if(i >= j) break;
       Swap(a[i], a[j]);
       }
     a[p] = a[j];
     a[j] = x;
     return j;
}

函数Partition的计算时间为O(n)
最坏情况，划分分别包含n-1个元素和1个元素。
在这里插入图片描述

最好情况，划分基准恰好为中值。
在这里插入图片描述

template<class Typa>
int RanddomizedPartition(Type a[], int p, int r)
{    int i = Random(p, r);
     Swap(a[i], a[p]);
     return Partition(a, p, r);
}