寫在前面

• 樓主整理經(jīng)典的排序算法
• 記錄學(xué)習(xí)

1. 選擇排序(Selection Sort)

1.1 概念

選擇排序 是表現(xiàn)最穩(wěn)定的排序算法之一 ，因?yàn)闊o(wú)論什么數(shù)據(jù)進(jìn)去都是O(n²)的時(shí)間復(fù)雜度 ，所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。

選擇排序(Selection-sort) 是一種簡(jiǎn)單直觀的排序算法。

1.2 算法描述

它的工作原理：

• 首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置

• 然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。

• 以此類推，直到所有元素均排序完畢。

示意圖

image

1.3 代碼演示

package com.zhuang.algorithm;

/**
 * @Classname SelectionSort
 * @Description 選擇排序
 * @Date 2021/6/13 14:44
 * @Created by dell
 */

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr =new int[]{0,5,6,1,8,2};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));//[0, 1, 2, 5, 6, 8]
    }
    public static void selectionSort(int[] arr){
        int temp,min=0;
        for (int i = 0; i < arr.length-1; i++) {
            min=i;
            //循環(huán)查找最小值
            for (int j = i+1; j < arr.length; j++) {
                if (arr[min]>arr[j]) {
                    min = j;
                }
            }
            if (min!=i){
                temp=arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
}

1.4 算法分析

• 最佳情況：T(n) = O(n²)
• 最差情況：T(n) = O(n²)
• 平均情況：T(n) = O(n²)

1.5 穩(wěn)定性

用數(shù)組實(shí)現(xiàn)的選擇排序是不穩(wěn)定的，用鏈表實(shí)現(xiàn)的選擇排序是穩(wěn)定的。不過(guò)，一般提到排序算法時(shí)，大家往往會(huì)默認(rèn)是數(shù)組實(shí)現(xiàn)，所以選擇排序是不穩(wěn)定的。

1.6 適用場(chǎng)景

由于在各種情況下復(fù)雜度波動(dòng)小，因此一般是優(yōu)于冒泡排序的。在所有的完全交換排序中，選擇排序也是比較不錯(cuò)的一種算法。但是，由于固有的O(n²)復(fù)雜度，選擇排序在海量數(shù)據(jù)面前顯得力不從心。因此，它適用于簡(jiǎn)單數(shù)據(jù)排序。

寫在最后

• 學(xué)習(xí)階段，描述不當(dāng)?shù)胤?，還請(qǐng)大家在評(píng)論區(qū)指出
• 繼續(xù)加油！