【数据结构和算法那些事】--【2】--选择排序

川长思鸟来 2022-08-25 08:26 97阅读 0赞

个人学习整理，如有不足之处，请不吝指教。转载请注明：[@CSU-Max][CSU-Max]

**原理描述：**

选择排序总的来说就是每一趟从n-i+1 (i=1,2,...,n)个元素中选取一个关键字最小的元素作为有序序列中的第i个元素。

（以从小到大的顺序为例）第一趟，从n 个元素中找出关键字最小的元素与第1 个元素进行交换；第二趟，再从第2 个元素开始的后面的n-1 个元素中再选出关键字最小的元素与第2 个元素交换；依次类推，即第 K 趟，则从第k 个元素开始的后面的 n-k+1 个元素中选出关键字最小的元素与第k 个元素交换，直到整个序列有序。

**图解说明：**

待排序序列       14    45    56     10    11    24    45    23

k                    min

第1趟                10     45    56    14     11    24    45    23

k                    min

第2趟                 10    11     56     14    45    24    45    23

k    min

第3趟                 10    11    14     56    45    24    45     23

k                            min

第4趟                 10    11    14    23     45     24    45    56

k     min

第5趟                 10    11    14    23    24     45    45    56

k=min

第6趟                 10    11    14    23    24    45     45    56

k=min

第7趟                 10    11    14    23    24    45    45    56

**实现代码：**

/**
         *  @Description :选择排序
         *  @param  k        带排序的数组
         *  @param  start    数组中待排序区间的起点
         *  @param  end    数组中待排序区间的终点
         */
         public   void  selectSort( int [] k,  int  start,  int  end){
             for ( int  i = start; i < end-1; i++){   
                 //选择出最小的元素
                 int  min = i;
                 for ( int  j = min+1; j <= end; j++){
                     if (k[j] < k[min]){
                        min = j;
                    }
                }
                 //将最小的元素与第i 个元素交换
                 if (i != min){
                    int  temp = k[i];
                    k[i] = k[min];
                    k[min] = temp;
                }
            }    
     }

public   static   void  main(String[] args) {
            MySortMethod method =  new  MySortMethod();
            MyUtil myUtil =  new  MyUtil();
             int [] r = {14, 45, 56, 10, 11, 24, 45, 23};
            
            
            myUtil.printArray(r);
            method.selectSort(r, 0, r. length -1);
            myUtil.printArray(r);
        }

**相关分析：**

空间效率：简单的选择排序只需要一个辅助空间。

时间效率：

在简单选择排序中，所需移动的元素次数较少，若待排序的序列已经有序，则使用简单排序不需要移动元素，在最坏的情况下，若待排序的序列本身就是逆序的，则移动元素的次数为 3（n-1），交换一次要移动３次。

简单选择排序都需要进行n(n-1)/2 次比较操作，因此时间复杂度为 O（ｎ ２）。

[CSU-Max]: http://blog.csdn.net/csu_max