當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

排序——选择排序

發布時間：2023/12/9 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了排序——选择排序小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

選擇排序

作者：上品物語?

知識點：

1.1?? 原理

首先，找到數組中最小的那個元素，其次，將它和數組的第一個元素交換位置（如果第一個元素就是最小元素，那么它就和自己交換）。再次，在剩下的元素中找到最小的元素，將它與數組的第二個元素交換位置。如此往復，直到將整個數組排序。這種方法叫做選擇排序，因為它在不斷地選擇剩余元素之中的最小者。

1.2?? 示意圖

1.3?? 算法

public class Selection {

????????

???????? private static boolean less(Comparable v, Comparable w){

?????????????????? return v.compareTo(w)<0;

???????? }

????????

???????? private static void exch(Comparable[] a, int i, int j){

?????????????????? Comparable t = a[i];

?????????????????? a[i] = a[j];

?????????????????? a[j] = t;

???????? }

????????

???????? public static void sort(Comparable[] a){

????????? 　　　//將a[]按升序排序

?????????????????? int N = a.length;

?????????????????? for(int i = 0; i < N; i++){

??????????????????????????? int min = i;

??????????????????????????? for(int j = i+1; j < N; j++)

???????????????????????????????????? if(less(a[j],a[min]))

?????????????????????????????????????????????? min = j;

??????????????????????????? exch(a,i,min);

?????????????????? }

???????? }

}

1.4?? 特點

運行時間和輸入無關。為了找出最小的元素而掃描一遍數組并不能為下一遍掃描提供什么信息。這種性質在某些情況下是缺點，因為使用選擇排序的人可能會驚訝地發現，一個已經有序的數組或是主鍵全部相等的數組和一個元素隨機排列的數組所用的排序時間竟然一樣長！我們將會看到，其他算法會更善于利用輸入的初始狀態。

數據移動是最少的。每次交換都會改變兩個數組元素的值，因此選擇排序用了N次交換——交換次數和數組的大小是線性關系。我們將研究的其他任何算法都不具備這個特征（大部分的增長數量級都是線性對數或是平方級別）。

?參考：排序算法之選擇排序講解并java實現

以上是生活随笔為你收集整理的排序——选择排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。