屌丝的常用排序-----three

    上面文章讲完了插入排序和交换排序，本次我们来讨论选择排序。

          选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。

1、普通(单个)选择排序

    每遍历一次，记录下最值元素所在位置，遍历结束后，将此最值元素调整到合适的位置。这样一次遍历，只需一次交换，便可将最值放置到合适位置

//成功返回0，失败返回-1
int select_sort(int *arr,const int n)
{
    //判断参数是否正确
    if(NULL == arr || 0 >= n)
            return -1;
            
     int i = 0;    //循环使用
     int j = 0;    //循环使用
     int k = -1;    //记录比较的下标
     int temp;        //交换时作中间值
     
      //每次循环只进行一次交换 最多进行n - 1次循环，因此总体上，比冒泡进行交换的次数少
     for(i = 0; i < n - 1; i++)
     {
            //第i次排序时，已经进行了i次大循环，因此已经排好了i个元素  
            //已排好序的元素0，,...,i-2,i-1  
            //待排元素为i,i+1,...,n-1  
            
            k = i;    //拿i的位置值与后面的值相比较
            for(j = i + 1; j < n; i++)
            {
                    if(arr[k] < arr[j])
                        k = j;
            }
            
            //判断k值是否有变化，有变量就交换
            if(k != i)
            {
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
            }
     }
     return 0;
}

2、二分选择排序

int select_sort(int *arr, const int n)
{
    //判断参数是否正确
    if(NULL == arr || 0 >= n)
        return -1;
        
    int i = 0;
    int j = 0;
    int minpos = -1;
    int maxpos = -1;
    int temp;
    //每次循环完进行二次交换 最多进行n/2次循环，因此总体上，比冒普通选择排序的次数少
    for(i = 0; i < n / 2; i++)
    {
        minpos = i;
        maxpos = i;
        for(j = i + 1; j < n; j++)
        {
            if(arr[j] > arr[maxpos])
            {
                maxpos = j;
                continue;
            }      
            
            if(arr[j] < arr[minpos])
            {
                minpos = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minpos];
        arr[minpos] = temp;
        
        if(maxpos == i)
        {
            temp = arr[minpos];
            arr[minpos] = arr[n - 1 - i];
            arr[n - 1 - i] = temp;
        }
        else
        {
            temp = arr[maxpos];
            arr[maxpos] = arr[n - 1 - i];
            arr[n - 1 -i] = temp;
        }
    }
    return 0;
}