一种简单直观的排序算法。 05选择排序.mp4

算法思路，第一次找最小的与首位i交换，后面的与i++交换

以由小到大排序为例，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
image.png
第一轮∶找到最小值23，跟第1个位置29交换，得到有序集合{23}。

第二轮∶从无序集合中找到最小值27，跟第2个位置38交换，得到有序集合{23,27].

第三轮∶从无序集合中找到最小值29，跟第3个位置65交换，得到有序集合{23,27,29]。

第四轮:从无序集合中找到最小值29，跟第4个位置87交换，得到有序集合{23,27,29,29]。

第五轮︰从无序集合中找到最小值38，跟第5个位置78交换，得到有序集合{23,27,29,29,38}。

第六轮︰从无序集合中找到最小值65÷不需要交换，得到有序集合{23,27,29,29,38,65}。

第七轮∶从无序集合中找到最小值78，不需要交换，得到有序集合{23,27,29,29,38,65,78]。

代码实现

  1. public class SelectionSort{
  2.     public static void main(String[] args){
  3.         int[ ] arr = {29,38,65,87,78,23,27,29};
  4.         selectionsort( arr);
  5.         System.out.println(Arrays.toString(arr)) ;
  7.     }
  9.     public static void swap(int[] arr,int i,int j)
  10.     {
  11.         int temp = arr[i];
  12.         arr[i]=arr[j];
  13.         arr[j]=temp;
  14.     }
  17.     public static void selectionSort(int[] arr)
  18.     {
  19.         for(int i = 0;i<arr.length-1;i++)
  20.         {
  21.             int min_index = i;
  22.             for(int j = i+1;j<arr.length;j++)
  23.             {
  24.                 if(arr[j]<arr[min_index])
  25.                 {
  26.                     min_index = j;
  27.                 }
  28.             }
  29.             //用最小值替换i的位置
  30.             swap(arr, i, min_index)
  31.         }
  32.     }
  33. }

算法稳定性

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的;选择排序有不稳定性的算法。例如序列“5(1),8,5(2),2,9”，5(1)会和2交换，破坏稳定性。

时间复杂度∶

1：n-1
2：n-2
3：n-3
4：n-4
……
n-1:1
比较次数=(n-1+1)(n-1)/2=(n^2-n)/2
时间复杂度=o(n2)