轻松掌握编程基本算法（三）

2023-03-01

int max min

编程基本算法（一）编程基本算法（二）编程基本算法（三） 选择排序使用条件：可对比大小的集合。算法思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。举例编程：intb[10]={77,1,65,13,81,93,10,5

编程基本算法（一）

编程基本算法（二）

编程基本算法（三）

选择排序

使用条件：可对比大小的集合。

算法思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//简单选择排序 
void SimpleSelect(int b[10]) 
{ 
    int temp; 
    int i; 
    for(i=0;i<9;i++) 
    { 
        for(int j=i+1;j<9;j++) 
        { 
            if(b[i]>b[j]) 
            { 
                temp=b[i]; 
                b[i]=b[j]; 
                b[j]=temp; 
            } 
        } 
    } 
    cout<<"the sort is:"; 
    for(int i=0;i<10;i++) 
    { 
        cout<<b[i]<<" "; 
    } 
    cout<<endl; 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

性能分析：时间复杂度为O（n^2）

堆排序

使用条件：可对比大小的集合。

算法思想：其实堆排序是简单选择排序的一种进化，它最主要是减少比较的次数。什么是堆？若将序列对应看成一个完全二叉树，完全二叉树中所有非终端节点的值均不大于（或者不小于）其左右孩子节点的值，可以称作为堆。由堆的性质可以知道堆顶是一个最大关键字(或者最小关键字)。在输出堆顶后，使剩下的元素又建成一个堆，然后在输出对顶。如此反复执行，便能得到一个有序序列，这个过程成便是堆排序。

堆排序主要分为两个步骤：

（1）从无序序列建堆。

（2）输出对顶元素，在调成一个新堆。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//堆排序 
void HeapSort(int b[10]) 
{ 
    void HeapAdjuest(int b[10],int min,int max); 
    void Sawp(int *a,int *b); 
    int i; 
    //因为是完成二叉树，所以从最后一个非叶子节点开始堆转换 
    for(i=9/2;i>=0;i--) 
    { 
        HeapAdjuest(b,i,9); 
    } 
    //拿出堆顶数据在从新堆排序 
    for(i=9;i>0;i--) 
    { 
        Sawp(&b[i],&b[0]); 
        HeapAdjuest(b,0,i-1); 
    } 
} 
 
//堆调整(大顶堆) 
//min 数据需要调整在数组中的开始位置 
//max 数据需要调整在数据中的结束位置 
void HeapAdjuest(int b[10],int min,int max) 
{ 
    if(max<=min)return ; 
    int temp; 
    temp=b[min]; 
    int j; 
     
    //延它的孩子节点循环 
    for(j=2*min;j<=max;j*=2) 
    { 
        //选择它的大孩子 
        if(j<max&&b[j]<b[j+1]) 
        { 
            j++; 
        } 
         
        //堆顶大于它的孩子不做处理 
        if(temp>b[j]) 
        { 
            break; 
        } 
         
        //将大的数替换成小的数 
        b[min]=b[j]; 
        min=j;     
    } 
    b[min]=temp; 
} 
 
//交换函数 
void Sawp(int *a,int *b) 
{ 
    int temp; 
    temp=*a; 
    *a=*b; 
    *b=temp; 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.

性能分析：时间复杂度时间复杂度O(nlogn)

归并算法

又称2路归并算法

使用条件：可对比大小的集合。

算法思想：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1，然后两两归并，得到[n/2]个长度为2或者为1（这里长度为1可能这里序列长度是奇数，那么最后一个序列就落单了，所以长度为1）；在两两归并，如此重复，直至得到一个长度为n的有序序列为止。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//归并排序 
void MergeSort(int b[10],int d[10],int min,int max) 
{ 
    //用与存放中间分区域得到的序列 
    int c[10]; 
    void Merge(int c[10],int d[10],int min,int mid,int max); 
    if(min==max)d[min]=b[min]; 
    else 
    { 
        //平分成两个区域 
        int mid=(min+max)/2; 
        //将这个区域进行归并排序 
        MergeSort(b,c,min,mid); 
        //将这个区域进行归并排序 
        MergeSort(b,c,mid+1,max); 
        //两个区域归并 
        Merge(c,d,min,mid,max); 
    } 
} 
 
//将有序序列d[min-mid]与d[mid+1-max]归并成有序序列c[min-max] 
void Merge(int c[10],int d[10],int min,int mid,int max) 
{ 
    int i,j,k; 
    for(i=j=min,k=mid+1;j<=mid&&k<=max;i++) 
    { 
        if(c[j]>c[k]) 
        { 
            d[i]=c[k]; 
            k++; 
        } 
        else 
        { 
            d[i]=c[j]; 
            j++; 
        } 
    } 
    if(j<=mid) 
    { 
        for(;j<=mid;j++,i++) 
        { 
            d[i]=c[j]; 
        } 
    } 
    if(k<=max) 
    { 
         for(;k<=max;k++,i++) 
        { 
            d[i]=c[k]; 
        } 
    } 
} 
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.