數(shù)據(jù)結(jié)構(gòu)與算法系列(三)—選擇排序

點(diǎn)擊藍(lán)字關(guān)注我們

前言

大家好，牧碼心今天給大家推薦一篇數(shù)據(jù)結(jié)構(gòu)與算法系列（三）—選擇排序的文章，希望對(duì)你有所幫助。大綱如下:

• 選擇排序基本介紹

• 選擇排序圖文說明

• 選擇排序時(shí)空復(fù)雜度和穩(wěn)定性

• 選擇排序具體實(shí)現(xiàn)

選擇排序基本介紹

選擇排序 是一種較簡(jiǎn)單的排序算法，排序過程類似于隊(duì)伍排隊(duì)，每次選出相對(duì)最高或最小的同學(xué)排列。相比于冒泡排序省去了每輪交換多次的開銷。其基本思想是：首先在未排序的數(shù)列中找到最小(最大)元素，然后將其存放到數(shù)列的起始位置；接著，再?gòu)氖Ｓ辔磁判虻脑刂欣^續(xù)尋找最小(最大)元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序圖文說明

• 下面以數(shù)列{20,40,30,10,60,50}為例，演示選擇排序過程
  

  選擇排序過程

  
  排序流程說明：

  • 第1趟：i=0.找出a[1…5]中的最小值a[3]=10，然后將a[0]和a[3]互換。數(shù)列變化:

    • 20,40,30,10,60,50->10,40,30,20,60,50

  • 第2趟：i=1.找出a[2…5]中的最小值a[3]=20，然后將a[1]和a[3]互換。數(shù)列變化:

    • 10,40,30,20,60,50->10,20,30,40,60,50

  • 第3趟：i=2.找出a[3…5]中的最小值,由于該最小值大于a[2]，該趟不做任何處理。

  • 第4趟：i=3.找出a[4…5]中的最小值,由于該最小值大于a[3]，該趟不做任何處理。

  • 第5趟：i=4.交換a[4]和a[5]的數(shù)據(jù),數(shù)列變化:

    • 10,20,30,40,60,50->10,20,30,40,50,60

選擇排序時(shí)空復(fù)雜度和穩(wěn)定性

• 說明

  • 時(shí)間復(fù)雜度：選擇排序每一輪需要選出最小值min，在交互到最左邊的時(shí)間復(fù)雜度為O(n)，共需要進(jìn)行n-1輪。所以總的時(shí)間復(fù)雜度為O(n^2) ；

  • 空間復(fù)雜度 ：選擇排序是原地排序，沒有產(chǎn)生額外的空間，則為O(1) ；

  • 穩(wěn)定性 ：選擇排序是不穩(wěn)定的，比如被排序的序列存在多個(gè)相同的的元素時(shí)，該排序會(huì)打亂各元素原有的相對(duì)順序。

選擇排序?qū)崿F(xiàn)

• 選擇排序（java版）

 1/*
 2?????*?@Author:greekw
 3?????*?@Desc:?選擇排序，類比站隊(duì)
 4?????*?@Date?0:04?2020/7/22
 5?????*?@Param?[array]
 6?????*?@return?void
 7????**/
 8????public?static?void?selectSort(int[]?array){
 9????????for?(int?i?=?0;?i?<?array.length?;?i++)?{
10????????????//?設(shè)置初始的最小位置
11????????????int?minIndex?=?i;
12
13????????????//?找出最小元素的位置
14????????????for?(int?j?=?i;?j?<?array.length;?j++)?{
15
16????????????????minIndex?=?(array[j]?<?array[minIndex])???j?:?minIndex;
17????????????}
18
19????????????//?交換元素，排序
20????????????int?temp?=?array[i];
21????????????array[i]?=?array[minIndex];
22????????????array[minIndex]?=?temp;
23????????}
24????}
25?????//?測(cè)試用例
26????public?static?void?main(String[]?args)?{
27????????int[]?selectArray=?new?int[]{20,40,30,10,60,50};
28????????selectSort(selectArray);
29????????System.out.println(Arrays.toString(selectArray));
30????}

往期回顧

• 數(shù)據(jù)結(jié)構(gòu)與算法系列（二）—冒泡排序

• 數(shù)據(jù)結(jié)構(gòu)與算法系列（一）—鏈表
  

THE

END

長(zhǎng)按二維碼關(guān)注，一起學(xué)習(xí)、思考、成長(zhǎng)

掃碼關(guān)注我們

微信號(hào) : lx_three