经典排序算法之——选择法排序

选择法排序

       选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
        简单选择排序的基本思想：
        第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
        第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
        以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

以下为简单选择排序的存储状态，其中大括号内为无序区，大括号外为有序序列：

初始序列：{ 48 25 65 97 76 12 37 }

第1趟：12与48交换：12 { 25 65 97 76 48 37 }

第2趟：25不动　：12 25 { 65 97 76 48 37 }

第3趟：65与38交换：12 25 37 { 97 76 48 65 }

第4趟：97与48交换：12 25 37 48 { 76 97 65 }

第5趟：76与65交换：12 25 37 48 65 { 97 76 }

第6趟：97与76交换：12 25 37 48 65 76 97
     
      完成。

/**********************************************************************************
选择排序：
       每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
***********************************************************************************/
void Dir_Choose(int A[],int n) //直接选择排序
{
        int min,temp;
        for(int i=0;i<n-1;i++)
        {
            min=i;
            for(int j=i+1;j<n;j++)
            {
                 if(A[j]<A[min])
                min=j;
            }
            if(min!=i)
            {
                    temp=A[i];
                    A[i]=A[min];
                    A[min]=temp;
            }
       }
}

总结：选择排序是不稳定的。算法复杂度是O(n ^2 )