首页 > 编程语言 > 详细

选择排序算法

时间:2021-04-30 10:28:44      阅读:14      评论:0      收藏:0      [点我收藏+]
#include <stdio.h>

//最小值 
//选择算法递归实现    
//原理:每次从a[i]~a[n]中选择一个最大值/最小值放到序列首部(得到最值的方法时比较),
//这样当i=n-1时正好求得一个排序序列 
//时间复杂度分析:设原问题时间复杂度位T(n),共分成了1个子问题
//则T(n)=T(n-1)+n    T(n-1):是要选择n-1次,n:是要比较的次数    (因为1,2,3...都被舍去了)
//递推公式自己去算,数学就可以退出来,=O(n^2) 
void Select(int a[],int i,int n)
{
    if(i<n)
    {
        int small,j,temp;
        small=i;    //用每个递归序列的开头元素去比较 
        for(j=i+1;j<n;j++)
            if(a[j]<a[small])
                small=j;       //获得最小值的下标 
        //交换    使每一次递归 得到一个最小值,放在i-n的行首 
        temp=a[small];
        a[small]=a[i];
        a[i]=temp;  
        Select(a,i+1,n);   //进行下一次递归  
    }
}
//选择算法的非递归实现 1   算法原理:相邻元素两两比较 
void Select1(int a[],int n)
{
    int temp;
    for(int i=0;i<n-1;i++)   
        for(int j=i;j<n;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
 } 
//遍历算法 
void Print(int a[],int n)
{
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
}
int main()
{
    int a[10]={100,32,12,1000,43,56,43,89,0,1};
    int b[10]={100,32,12,1000,43,56,43,89,0,1};
    printf("递归遍历序列: ");
    Select(b,0,10);
    Print(b,10);
    printf("\n左右交换法的序列: ");
    Select1(a,10);
    Print(a,10);
    return 0;
}

技术分享图片

 

选择排序算法

原文:https://www.cnblogs.com/nanfengnan/p/14720227.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!