c/c++排序算法-选择排序

川长思鸟来 2022-01-13 06:23 230阅读 0赞

### 文章目录 ###

*   *  简单的选择排序
     *   *  基本思想
         *  操作方法：
         *  时间复杂度分析
     *  二元选择排序（简单选择排序的改进版）

## 简单的选择排序 ##

### 基本思想 ###

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

#include <stdio.h>
    
    void printfarr(int *buf, unsigned int len,int count)
    {
        
        if (buf == NULL)
        {
        
            return;
        }
        printf("%d:",count);
        unsigned int i = 0;
        for (i = 0;i < len;i++)
        {
        
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    
    unsigned int SelectSmall(int *arr,unsigned int len,unsigned int n)
    {
        
        int min = arr[n];
        unsigned int index = n;
        for(unsigned int i = n;i < len;i++)
        {
        
            if(min > arr[i])
            {
        
                min = arr[i];
                index = i;
            }
        }
        return index;
    }
    
    
    void SimpleSelectSort(int *arr,unsigned int len)
    {
        
        int count = 0;
        for(unsigned int i = 0;i < len;i++)
        {
        
            unsigned int key = SelectSmall(arr,len,i);
            if(arr[i] > arr[key])
            {
        
                //异或法实现两个数交换
                arr[key] = arr[key] ^ arr[i];
                arr[i] = arr[i] ^ arr[key];
                arr[key] = arr[key] ^ arr[i];
                count++;
                printfarr(arr, len,count);
            }
        }
    }
    
    int main()
    {
        
        int arr[] = {
        9,8,2,6,4,0,3,14,1,7,5,11,10,16,13,15,18};
        SimpleSelectSort(arr,sizeof(arr)/sizeof (arr[0]));
        return 0;
    }

运行结果：
    1:0 8 2 6 4 9 3 14 1 7 5 11 10 16 13 15 18
    2:0 1 2 6 4 9 3 14 8 7 5 11 10 16 13 15 18
    3:0 1 2 3 4 9 6 14 8 7 5 11 10 16 13 15 18
    4:0 1 2 3 4 5 6 14 8 7 9 11 10 16 13 15 18
    5:0 1 2 3 4 5 6 7 8 14 9 11 10 16 13 15 18
    6:0 1 2 3 4 5 6 7 8 9 14 11 10 16 13 15 18
    7:0 1 2 3 4 5 6 7 8 9 10 11 14 16 13 15 18
    8:0 1 2 3 4 5 6 7 8 9 10 11 13 16 14 15 18
    9:0 1 2 3 4 5 6 7 8 9 10 11 13 14 16 15 18
    10:0 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 18

### 操作方法： ###

> 第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；  
> 第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；  
> 以此类推…  
> 第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，  
> 直到整个序列按关键码有序。

### 时间复杂度分析 ###

简单选择排序是一个稳定的排序算法，它最大的特点就是交换移动数据次数相当少，无论最好最差的情况，其比较次数都是一样的多，第  i i i 趟排序需要进行  n − i n-i n−i 次关键字的比较，  
 ∑ i = 1 n − 1 ( n − i ) = ( n − 1 ) + ( n − 2 ) + ( n − 3 ) + … … + 1 = n ( n − 1 ) 2 \\sum\_\{i=1\}^\{n-1\} (n - i) = (n-1) + (n-2) + (n-3) + …… + 1 = \\frac\{n(n - 1)\}\{2\} i=1∑n−1(n−i)=(n−1)\+(n−2)\+(n−3)\+……\+1=2n(n−1)  
交换次数最好的时候是  0 0 0 次，最差的时候是  n 2 \\frac\{n\}\{2\} 2n 次，总的时间复杂度是 O ( n 2 ) O(n^2) O(n2)

## 二元选择排序（简单选择排序的改进版） ##

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行\[n/2\]趟循环即可。具体实现如下：

#include <stdio.h>
    
    struct arrIndex{
        
        unsigned int minIndex;
        unsigned int maxIndex;
    };
    
    void printfarr(int *buf, unsigned int len,int count)
    {
        
        if (buf == NULL)
        {
        
            return;
        }
        printf("%d:",count);
        unsigned int i = 0;
        for (i = 0;i < len;i++)
        {
        
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    
    void SelectSmall(int *arr,unsigned int len,unsigned int n,struct arrIndex *index_t)
    {
        
        int min = arr[n];
        int max = arr[n];
        index_t->maxIndex = n;
        index_t->minIndex = n;
        for(unsigned int i = n;i < len;i++)
        {
        
            if(min > arr[i])
            {
        
                min = arr[i];
                index_t->minIndex = i;
                continue;
            }
            if(max < arr[i])
            {
        
                max = arr[i];
                index_t->maxIndex = i;
            }
        }
    }
    
    
    void SelectSort(int *arr,unsigned int len)
    {
        
        int count = 0;
        unsigned key = len;
        struct arrIndex index_t;
        for(unsigned int i = 0;i <= len/2;i++)
        {
        
            SelectSmall(arr,key,i,&index_t);
            key = key - 1;
            printfarr(arr, len,count);
            printf("min = %d,max = %d\n",arr[index_t.minIndex],arr[index_t.maxIndex]);
            if(arr[index_t.minIndex] == arr[index_t.maxIndex])
            {
        
                break;
            }
            if(arr[i] > arr[index_t.minIndex])
            {
        
                //异或法实现两个数交换
                arr[index_t.minIndex] = arr[index_t.minIndex] ^ arr[i];
                arr[i] = arr[i] ^ arr[index_t.minIndex];
                arr[index_t.minIndex] = arr[index_t.minIndex] ^ arr[i];
            }
            if(arr[len - i - 1] < arr[index_t.maxIndex])
            {
        
                //异或法实现两个数交换
                arr[index_t.maxIndex] = arr[index_t.maxIndex] ^ arr[len - i - 1];
                arr[len - i - 1] = arr[len - i - 1] ^ arr[index_t.maxIndex];
                arr[index_t.maxIndex] = arr[index_t.maxIndex] ^ arr[len - i - 1];
            }
            count++;
        }
    }
    
    int main()
    {
        
        int arr[] = {
        9,8,2,6,4,0,3,14,1,7,5,11,10,16,13,15,18};
        SelectSort(arr,sizeof(arr)/sizeof (arr[0]));
        return 0;
    }

运行结果：
    0:9 8 2 6 4 0 3 14 1 7 5 11 10 16 13 15 18
    min = 0,max = 18
    1:0 8 2 6 4 9 3 14 1 7 5 11 10 16 13 15 18
    min = 1,max = 16
    2:0 1 2 6 4 9 3 14 8 7 5 11 10 15 13 16 18
    min = 2,max = 15
    3:0 1 2 6 4 9 3 14 8 7 5 11 10 13 15 16 18
    min = 3,max = 14
    4:0 1 2 3 4 9 6 13 8 7 5 11 10 14 15 16 18
    min = 4,max = 13
    5:0 1 2 3 4 9 6 10 8 7 5 11 13 14 15 16 18
    min = 5,max = 11
    6:0 1 2 3 4 5 6 10 8 7 9 11 13 14 15 16 18
    min = 6,max = 10
    7:0 1 2 3 4 5 6 9 8 7 10 11 13 14 15 16 18
    min = 7,max = 9
    8:0 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 18
    min = 8,max = 8