資訊專欄INFORMATION COLUMN
摘要：選擇排序，簡單粗暴直觀的排序算法。我們跑一趟無序序列，把最小值和最大值都找出來。
選擇排序，簡單粗暴直觀的排序算法。
一個長度為N的序列num[N]，分為有序部分和無序部分
第一次，num[0]~num[N-1]是無序部分，從這N個數中選出最小的數，放在序列的第一個位置，
此時，num[0]是有序部分，num[1]~num[N]是無序部分
第二次，num[0]是有序部分，num[1]~num[N]是無序部分，從N-1個數中選出最小的數，放在序列的第二個位置，
此時，num[0]~num[1]是有序部分，num[2]~num[N]是無序部分
如此進行下去，整個序列最終為有序（順序）序列
代碼：
#include#define N 10void selectsort(int *num , int length ){ int i ; int j; int temp;//中間變量，供交換值的時候使用 for(i = 0;i < length ; i ++)//假設無序序列的第一個元素num[i]為最小值 { for(j = i+1 ; j < length ;j++)//遍歷最小值后面的所有元素(num[i+1]~num[length-1]) { if(num[i] > num[j])//若找到比最小值num[i]還要小的元素，則與原來的最小值元素交換值 { temp = num[i]; num[i] = num[j]; num[j] = temp; } } }}int main(){ int num[N] = {9,8,7,6,5,4,3,2,1,0}; selectsort(num , N); for(int i=0; i < N;i++) { printf("%d ",num[i]); } printf("/n"); return 0;} 運行結果
看一下程序細節
時間復雜度
第一次需要遍歷N-1個元素，第二次需要遍歷N-2個元素······
所以時間復雜度是）O（N^2）
然而，細想一下，選擇排序，每一趟遍歷無序部分，卻只為了找到那個最小的數，效率太低（老子辛辛苦苦在無序序列兜了一圈，只找一個最小值，這哪行，哪像計算機人搜搜扣扣的精神（又扣時間又扣空間））
于是，趕一只羊也是趕，趕兩只羊也是趕。我們跑一趟無序序列，把最小值和最大值都找出來。
代碼：
#include#define N 10#includevoid swap(int *a,int *b)//函數作用，交換a和b的值{ int temp ; temp = *a; *a = *b; *b = temp;}void selectsort(int *num ,int n){ int start = 0;//無序部分的第一個元素 int end = N-1;//無序部分的最后一個元素 while(start < end) { int min_index = start;//最小值元素的下標 int max_index = end;//最大值元素的下標 int i = 0; for(i = start;i<=end;i++)//遍歷無序序列 { if(num[i] < num[min_index]) min_index = i;//記錄無序序列最小值元素的下標 if(num[i] > num[max_index]) max_index = i; //記錄無序序列最大值元素的下標 } swap(&num[start],&num[min_index]);//將找到的最小值放在序列開頭 //錯誤語句實例 swap(&num[end],&num[max_index]); //將找到的最大值放在序列末尾，看似合情合理，但在極端情況下與上一句語句是矛盾的 //本例就屬于極端情況，此處挖一個坑 if(start == max_index)//極端情況，當最大值位于序列開頭，要被最小值替換 { max_index = min_index; } start++;//縮小無序序列長度，因為有序序列變長了 end--; //細節演示 // for(int i = 0;i 運行結果：
?
程序細節：
?對比單向選擇排序算法，雙向選擇排序雖然時間復雜都仍然是O(N^2),但是效率優化了50%左右
?填坑：
我們需要排序的序列是num[10] = {9，8，7，6，5，4，3，2，1，0}
先來看一下錯誤代碼
?錯誤細節，每一次遍歷序列的變化
可以看到?，第一次遍歷，最小值下標是9，最大值下標是0，處理過程是將num[min_index]放在序列開頭,num[max_index]放在序列末尾，即num[0] <——>num[9],即num[0]和num[9]只需要一次換值；
但是因為執行兩次swap()（換值函數），相當于原來序列并沒有發生變化
在以后的遍歷中，也是這種情況，所以最終結果是序列沒有任何變化，也就不難理解為何代碼要做如下處理
正確代碼
?正確細節，每一次遍歷序列的變化
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/124094.html
摘要：當到達時等同于直接插入排序，此時序列已基本有序，所有記錄在統一組內排好成有序序列。當面對大量數據時，希爾排序將比直接插入排序更具優勢圖示講解第一趟取增量，所有間隔為的元素分在一組，在各個組中分別進行直接插入排序。 ...
摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為。快速排序和合并排序的算法速度分別表示為和，是算法所需的固定時間量被稱為常量。 分而治之 分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...
摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...
摘要：題目語言實現現插入排序算法把數字由小到大進行排序插入排序是把一個記錄插入到已排序的有序序列中，使整個序列在插入該記錄后仍然有序。 ?1、題目 ???????C語言實現現插入排序算法把數字由小到大進行排序 插入排序是把一個記錄插入到已排序的有序序列中，使整個序列在插入該記錄后仍然有序。插入排序...
閱讀 877·2021-11-22 09:34
閱讀 1013·2021-10-08 10:16
閱讀 1826·2021-07-25 21:42
閱讀 1795·2019-08-30 15:53
閱讀 3527·2019-08-30 13:08
閱讀 2186·2019-08-29 17:30
閱讀 3349·2019-08-29 17:22
閱讀 2182·2019-08-29 15:35
