算法之选择排序

---

• 一：基本概念

  选择排序(Select Sort)，第1趟，在待排序记录r[1]r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

• 二：图文说明

选择排序示意图.png

我们分析一下具体的排序步骤：
1. 我们先找到数列中最小的数字即16，我们需要将最小的排到第一位，所以将第一位上的值21和16进行交换；
2. 除过第一位元素，在后面的数列中找出最小的值放到第二位，即将21与25进行交换；
3. 除过第一、第二位元素，在后面的数列中找出最小的值放到第三位，即将25与49进行交换；
4. 除过第一、第二、第三位元素，在后面的数列中找出最小的值放到第四位，因为32是最小的值，刚好又在第四位上，所以不用交换；
5. 剩下的最后一位肯定就是最大的数，即数组排序完成！

• 三：代码实现

  1. C语言实现

  #include <stdio.h>
  /*
      选择排序 
  */
  void show(int arr[],int len);//打印出数组 
  void swap(int arr[],int i,int j); //交换数组中的两个位置 
  void selectSort(int arr[],int len); //选择排序算法实现 
  
  int main(void)
  {
      int arr[] = {21, 25, 49, 32, 16};
      int len = sizeof(arr)/sizeof(*arr);
      printf("待排序数组为:\n");
      show(arr,len);
      selectSort(arr,len);
      printf("排序之后的数组为:\n");
      show(arr,len);
      return 0;
  }
  
  void show(int arr[],int len)
  {
      int i;
      for(i=0;i<len;i++)
      {
          printf("%d ",arr[i]);
      }
      printf("\n");
  }
  
  void swap(int arr[],int i,int j)
  {
      int temp;
      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
  
  void selectSort(int arr[],int len)
  {
      int i,j;
      int k = -1;
      for(i=0; i<len;i++)
      {
          k = i;//存储将要交换位置的下标
          for(j=i;j<len;j++)//第一趟排序中的所有比较 
          {
              if(arr[j]<arr[k])
              {
                  k = j;
              }
          }
          swap(arr,i,k);
      }
  }
  

  2.JAVA实现

  package com.data;
  import java.util.Arrays;
  public class SelectSort {
      public static void main(String[] args) {  
          int a[] = {21, 25, 49, 32, 16};
          System.out.println("排序前的数组为:"+Arrays.toString(a));
          selectionSort(a);
          System.out.println("排序后的数组为:"+Arrays.toString(a)); 
      }  
      public static void selectionSort(int arr[]){  
          for(int i=0;i<arr.length;i++){ //遍历整个数组  
              int minIndex=i;  //声明最小值坐标  
              for(int j=i+1;j<arr.length;j++){ //遍历为交换的数组  
                  if(arr[minIndex]>arr[j]){ //拿当前最小值跟为交换的数组对比  
                      minIndex=j;  
                  }  
              }  
              int conversion=arr[i]; //换位变量  
              arr[i]=arr[minIndex]; //交换位置  
              arr[minIndex]=conversion;  
          }  
            
      }  
  }
  

• 四：选择排序的时间复杂度和稳定性

  1. 选择排序的时间复杂度
  • 选择排序的时间复杂度是O(N*N)。
  2. 选择排序稳定性
  • 选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择次小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变了。