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

    上面文章講完了插入排序和交換排序，本次我們來討論選擇排序。

          選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法(比如序列[5， 5， 3]第一次就將第一個[5]與[3]交換，導(dǎo)致第一個5挪動到第二個5后面)。

1、普通(單個)選擇排序

    每遍歷一次，記錄下最值元素所在位置，遍歷結(jié)束后，將此最值元素調(diào)整到合適的位置。這樣一次遍歷，只需一次交換，便可將最值放置到合適位置

//成功返回0，失敗返回-1
int select_sort(int *arr,const int n)
{
    //判斷參數(shù)是否正確
    if(NULL == arr || 0 >= n)
            return -1;
            
     int i = 0;    //循環(huán)使用
     int j = 0;    //循環(huán)使用
     int k = -1;    //記錄比較的下標(biāo)
     int temp;        //交換時作中間值
     
      //每次循環(huán)只進行一次交換 最多進行n - 1次循環(huán)，因此總體上，比冒泡進行交換的次數(shù)少
     for(i = 0; i < n - 1; i++)
     {
            //第i次排序時，已經(jīng)進行了i次大循環(huán)，因此已經(jīng)排好了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)
{
    //判斷參數(shù)是否正確
    if(NULL == arr || 0 >= n)
        return -1;
        
    int i = 0;
    int j = 0;
    int minpos = -1;
    int maxpos = -1;
    int temp;
    //每次循環(huán)完進行二次交換 最多進行n/2次循環(huán)，因此總體上，比冒普通選擇排序的次數(shù)少
    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;
}