简单选择排序C++实现

超、凢脫俗 2022-05-23 23:47 195阅读 0赞

选择排序

思想：

存在一乱序数组A\[0~n\]

第一步：以A\[0\]作为参考点，比较A\[1~n\], 遍历完数组后，寻找到最小值A\[k\]（或最大值）的下标k值，然后swap(A\[0\],A\[k\]);

第二步：以A\[1\]作为参考点，比较A\[2~n\], 遍历完数组后，寻找到最小值A\[k\]（或最大值）的下标k值，然后swap(A\[1\],A\[k\]);

第i步：以A\[i\]作为参考点，比较A\[(i+1)~n\], 遍历完数组后，寻找到最小值A\[k\]（或最大值）的下标k值，然后swap(A\[i\],A\[k\]);

时间复杂度：

N = 1 + 2 + 3 + … + n-1 = n\*(1+(n-1))/2  去掉常数为O(n^2);

算法实现:

#include<iostream>
    
    #include<malloc.h>
    
     
    
    using namespace std;
    
     
    
    /*选择排序 */
    
    void select_sort(int a[],int n)
    
    {
    
        int k = 0;
    
        int i = 0;
    
        int j = 0;
    
       
    
        for(i=0;i<n-1;i++)
    
        {
    
            k = i;
    
            for(j=i+1;j<n;j++)
    
            {
    
                if(a[k] > a [j])
    
                {
    
                    k = j;
    
                }
    
            }      
    
            swap(a[k],a[i]);
    
        }  
    
    }
    
    int main(void)
    
    {
    
        int n;
    
        int *p;
    
        int i=0;
    
       
    
        cin>>n; // 排序个数
    
        if(n < 0)
    
            return 0;
    
           
    
        p = (int *)malloc(sizeof(int)*n);
    
        for(i=0;i<n;i++)
    
        {
    
            cin>>p[i];
    
        }
    
       
    
        //选择排序
    
        select_sort( p, n);
    
        //输出排序结果
    
        for(i=0;i<n;i++)
    
        {
    
            cout<<p[i]<<""<<endl;
    
        }
         free(p);

return 0;
    
    }