使用 Java 的 DSA - 選擇排序

概述

選擇排序是一種簡單的排序演算法。此排序演算法是一種基於就地比較的演算法，其中列表分為兩部分，左側為已排序部分，右側為未排序部分。最初，已排序部分為空，未排序部分為整個列表。

從未排序陣列中選擇最小元素，並與最左元素交換，該元素成為已排序陣列的一部分。此過程透過將未排序陣列邊界向右移動一個元素來繼續。

此演算法不適用於大型資料集，因為其平均和最壞情況下時間複雜度為 O(n²)，其中 n 是元素的數量。

虛擬碼

Selection Sort ( A: array of item)
   procedure selectionSort( A : array of items )
   int indexMin
   for i = 1 to length(A) - 1 inclusive do:
      /* set current element as minimum*/
      indexMin = i    
      /* check the element to be minimum */
      for j = i+1 to length(A) - 1 inclusive do:
         if(intArray[j] < intArray[indexMin]){
             indexMin = j;
         }
      end for
      /* swap the minimum element with the current element*/
      if(indexMin != i) then
         swap(A[indexMin],A[i])
      end if
   end for
end procedure

演示程式

package com.tutorialspoint.simplesort;

import java.util.Arrays;

public class SelectionSortDemo {
     
   public static void main(String[] args){
      int[] sourceArray = {4,6,3,2,1,9,7};
      System.out.println("Input Array: " 
         + Arrays.toString(sourceArray));
      printline(50);
      System.out.println("Output Array: " 
         + Arrays.toString(selectionSort(sourceArray)));
      printline(50);        
   }    

   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
      System.out.println("=");
   }

   public static int[] selectionSort(int[] intArray){

      int indexMin;       
      // loop through all numbers 
      for(int i=0; i < intArray.length-1; i++){ 
         // set current element as minimum 
         indexMin = i;
         // check the element to be minimum 
         for(int j=i+1;j<intArray.length;j++){
            if(intArray[j] < intArray[indexMin]){
               indexMin = j;
            }
         }

         if(indexMin != i){
            System.out.println("     Items swapped: [ " 
               + intArray[i] + ", " + intArray[indexMin] +" ]" ); 
            // swap the numbers 
            int temp=intArray[indexMin];
            intArray[indexMin] = intArray[i];
            intArray[i] = temp;
         }          

         System.out.println("iteration "+(i+1) +"#: " 
		    + Arrays.toString(intArray));
      }
      return intArray;
   }
}

如果我們編譯並執行以上程式，則會產生以下結果 −

Input Array: [4, 6, 3, 2, 1, 9, 7]
==================================================
     Items swapped: [ 4, 1 ]
iteration 1#: [1, 6, 3, 2, 4, 9, 7]
     Items swapped: [ 6, 2 ]
iteration 2#: [1, 2, 3, 6, 4, 9, 7]
iteration 3#: [1, 2, 3, 6, 4, 9, 7]
     Items swapped: [ 6, 4 ]
iteration 4#: [1, 2, 3, 4, 6, 9, 7]
iteration 5#: [1, 2, 3, 4, 6, 9, 7]
     Items swapped: [ 9, 7 ]
iteration 6#: [1, 2, 3, 4, 6, 7, 9]
Output Array: [1, 2, 3, 4, 6, 7, 9]
==================================================