基础算法之简单选择排序（selection sort）

1，名 称：简单选择排序

2，复杂度：O(n^2)

3，实现方式：C语言

4，空间复杂度：O(1)

5，稳定性：不稳定

6，算法思想：总共遍历两次，外层循环是算法总共要至执行的此数，那么为什么呢？因为该算法每一次执行外层循环会进行一次交换，默认i所在的位置是最大或者最小（要根据升序还是降序确定），然后里层循环是确定要交换的数字，请具体的思想请大家去代码中体会吧！

7，算法种类：升序（ascending order）、降序（descending order）

8，算法实现代码：

注意：以下实例在 Windows 平台编译通过， Linux 上没有 conio.h 文件，所以无法编译通过。

Linux 上可以使用 #include <curses.h> 来代替 conio.h 文件提供的功能，安装方法：

ubuntu：

sudo apt-get install libncurses5-dev libncursesw5-dev

Centos：

sudo yum install ncurses-devel ncurses

#include "stdio.h"  
#include "conio.h"   
  
void swap(int *a, int *b){  
    int temp ;  
    temp = *a;  
    *a = *b;  
    *b = temp;  
}  
//升序---简单选择排序  
SelectionSortAsc(int *a,int n){  
    int i,j,min;  
    for( i = 0;i < 10; i++){  
        min = i;  
        for(j = i+1;j < 10; j++){  
            if(a[j] < a[min]){  
                min = j;      
            }     
        }  
        if(min != i)          
        swap(&a[i],&a[min]);  
    }  
    printf("\n  ascending order：");                   
}   
//降序---简单选择排序  
SelectionSortDesc(int *a,int n){  
    int i,j,max;  
    for( i = 0;i < 10; i++){  
        max = i;  
        for(j = i+1;j < 10; j++){  
            if(a[j] > a[max]){  
                max = j;      
            }     
        }  
        if(max != i)          
        swap(&a[i],&a[max]);  
    }  
    printf("\n  descending order：");                  
}   
 main(){  
    int i;  
    int  a[20] = {10,8,6,5,3,2,9,7,4,1};  
    SelectionSortAsc(a,10);   
    for(i = 0 ; i < 10; i++)  
        printf("%d ",a[i]);  
    printf("\n");     
    SelectionSortDesc(a,10);  
    for(i = 0 ; i < 10; i++)  
        printf("%d ",a[i]);  
    getche();     
}

参考实例:

#include <stdio.h>

typedef void (*p_func)(int *, int);

void select_sort(int  *arr, int size)   //选择排序
{
    int i = 0, j = 0;
    for(i = 0; i < size; i++)
    {
        for(j = i; j < size; j++)
        {
            if(arr[i] > arr[j] )
            {
                arr[i] ^= arr[j];
                arr[j] ^= arr[i];
                arr[i] ^= arr[j];
            }
        }
    }
}

void bubble_sort(int *arr, int size)    //冒泡排序
{
    int i = 0, j = 0;
    for(i = 1; i < size; i++)
    {
        for(j = 0; j < size - i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                arr[j] ^= arr[j+1];
                arr[j+1] ^= arr[j];
                arr[j] ^= arr[j+1];
            }   
        }   
    } 
}
void quick_sort(int *arr, int size)     //快速排序
{
    if(size <= 1)
        return;
    int base = *arr;
    int head = 0, tail = size - 1;
    while(head < tail)
    {
        if(arr[head] > arr[tail])
        {
            arr[head] ^= arr[tail];
            arr[tail] ^= arr[head];
            arr[head] ^= arr[tail];
        }
        if(arr[head] == base)
            tail--;
        else head++;
    }
    quick_sort(arr, head - 1);
    quick_sort(&arr[head + 1], size - head - 1);
}
int main()
{
    int arr[] = {0, 4, 2, 8, 6, 1, 5, 9, 3, 7};
    int i = 0, j = 0;
    p_func p_sort[] = {select_sort, bubble_sort, quick_sort};
    for(i = 0; i <= 2; i++)
    {
        p_sort[i](arr, sizeof(arr)/sizeof(int));
        i == 0 ? printf("select : ") : i == 1 ? printf("bubble : ") : printf("quick  : ");
        for(j = 0; j < sizeof(arr)/sizeof(int); j++)
            printf("%d  ", arr[j]);
        printf("\n");
    }

    return 0;
}