算法之選擇排序

• 一：基本概念

  選擇排序(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. 我們先找到數(shù)列中最小的數(shù)字即16，我們需要將最小的排到第一位，所以將第一位上的值21和16進行交換；
2. 除過第一位元素，在后面的數(shù)列中找出最小的值放到第二位，即將21與25進行交換；
3. 除過第一、第二位元素，在后面的數(shù)列中找出最小的值放到第三位，即將25與49進行交換；
4. 除過第一、第二、第三位元素，在后面的數(shù)列中找出最小的值放到第四位，因為32是最小的值，剛好又在第四位上，所以不用交換；
5. 剩下的最后一位肯定就是最大的數(shù)，即數(shù)組排序完成！

• 三：代碼實現(xiàn)

  1. C語言實現(xiàn)

  #include <stdio.h>
  /*
      選擇排序 
  */
  void show(int arr[],int len);//打印出數(shù)組 
  void swap(int arr[],int i,int j); //交換數(shù)組中的兩個位置 
  void selectSort(int arr[],int len); //選擇排序算法實現(xiàn) 
  
  int main(void)
  {
      int arr[] = {21, 25, 49, 32, 16};
      int len = sizeof(arr)/sizeof(*arr);
      printf("待排序數(shù)組為:\n");
      show(arr,len);
      selectSort(arr,len);
      printf("排序之后的數(shù)組為:\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實現(xiàn)

  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("排序前的數(shù)組為:"+Arrays.toString(a));
          selectionSort(a);
          System.out.println("排序后的數(shù)組為:"+Arrays.toString(a)); 
      }  
      public static void selectionSort(int arr[]){  
          for(int i=0;i<arr.length;i++){ //遍歷整個數(shù)組  
              int minIndex=i;  //聲明最小值坐標  
              for(int j=i+1;j<arr.length;j++){ //遍歷為交換的數(shù)組  
                  if(arr[minIndex]>arr[j]){ //拿當前最小值跟為交換的數(shù)組對比  
                      minIndex=j;  
                  }  
              }  
              int conversion=arr[i]; //換位變量  
              arr[i]=arr[minIndex]; //交換位置  
              arr[minIndex]=conversion;  
          }  
            
      }  
  }
  

• 四：選擇排序的時間復(fù)雜度和穩(wěn)定性

  1. 選擇排序的時間復(fù)雜度
  • 選擇排序的時間復(fù)雜度是O(N*N)。
  2. 選擇排序穩(wěn)定性
  • 選擇排序即是給每個位置選擇待排序元素中當前最小的元素。比如給第一個位置選擇最小的，在剩余元素里面給第二個位置選擇次小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇時，如果當前鎖定元素比后面一個元素大，而后面較小的那個元素又出現(xiàn)在一個與當前鎖定元素相等的元素后面，那么交換后位置順序顯然改變了。