排序算法復雜度（排序法）

大家好，我是小夏，我來為大家解答以上問題。排序算法復雜度，排序法很多人還不知道，現在讓我們一起來看看吧！

1、選擇排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基于此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。

2、簡單選擇排序的基本思想：第1趟，在待排序記錄r[1]~r[n]中選出最小的記錄，將它與r[1]交換；第2趟，在待排序記錄r[2]~r[n]中選出最小的記錄，將它與r[2]交換；以此類推，第i趟在待排序記錄r[i]~r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。

3、以下為簡單選擇排序的存儲狀態，其中大括號內為無序區，大括號外為有序序列：

4、初始序列：{ 49 27 65 97 76 12 38 }

5、第1趟：12與49交換：12 { 27 65 97 76 49 38 }

6、第2趟：27不動　：12 27 { 65 97 76 49 38 }

7、第3趟：65與38交換：12 27 38 { 97 76 65 49}

8、第4趟：97與49交換：12 27 38 49 { 97 76 65 }

9、第5趟：76與65交換：12 27 38 49 65 { 97 76 }

10、第6趟：97與76交換：12 27 38 49 65 76 97 完成

11、簡單選擇排序的算法具體描述如下：

12、void SelectSort(RecordType r[], int length)　/*對記錄數組r做簡單選擇排序，length為待排序記錄的個數*/

13、{

14、int temp;

15、for ( i=0 ; i< length-1 ; i++) //n-1趟排序

16、{

17、int index=i；　//假設index處對應的數組元素是最小的

18、for ( j=i+1 ; j < length ; j++) 　//查找最小記錄的位置

19、if (r[j].key < r[index].key )

20、index=j；

21、if ( index!=i) 　//若無序區第一個元素不是無序區中最小元素，則進行交換

22、{ temp= r[i]； r[i]= r[index]； r[index]=temp; }　//利用temp作為臨時空間，兩個值交換的橋梁

23、}

24、}

本文到此講解完畢了，希望對大家有幫助。