排序算法圖解之Java選擇排序

更新時間：2022年11月04日 11:37:52 作者：興趣使然黃小黃

選擇排序的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。本文通過圖片和示例介紹了選擇排序，需要的可以參考一下

1.選擇排序簡介

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

2.圖解選擇排序算法

選擇排序的基本思想如下：

第一次：從arr[0]~arr[n-1]中選取最小值，與arr[0]進行交換；

第二次：從arr[1]~arr[n-1]中選取最小值，與arr[1]進行交換；

第三次：從arr[2]~arr[n-1]中選取最小值，與arr[2]進行交換；

…

第 i 次：從arr[i]~arr[i-1]中選取最小值，與arr[i]進行交換；

總共通過n-1次，可以得到從小到大的有序序列。

以序列：{8, 3, 2, 1, 7, 4, 6, 5} 為例！分步驟圖解如下：

思路說明：

1.在每趟排序時，都假定當(dāng)前位置的元素為最小值，如果在遍歷過程中發(fā)現(xiàn)有比當(dāng)前位置元素還小的值，則替換最小值。（先將最小值記錄，此趟遍歷完成再替換）

2.選擇排序一共有數(shù)組大小-1趟排序。

3.選擇排序代碼實現(xiàn)

import java.util.Arrays;

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 選擇排序
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] array = {8, 3, 2, 1, 7, 4, 6, 5};
        System.out.println("排序前: " + Arrays.toString(array));
        selectSort(array);
        System.out.println("排序后: " + Arrays.toString(array));
    }

    //選擇排序
    public static void selectSort(int[] arr){
        //選擇排序過程
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i; //假定最小索引，最小值為第一個元素
            int min = arr[minIndex];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]){
                    //更新最小值
                    min = arr[j];
                    minIndex = j;
                }
            }
            //將最小值放進arr[i]
            if (i != minIndex){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            //輸出每輪排序后的結(jié)果
            System.out.println("第" + (i+1) + "趟: " + Arrays.toString(arr));
        }
    }
}

運行結(jié)果如下：