資訊專欄INFORMATION COLUMN
摘要：選擇排序，簡單粗暴直觀的排序算法。我們跑一趟無序序列，把最小值和最大值都找出來。
選擇排序，簡單粗暴直觀的排序算法。
一個長度為N的序列num[N]，分為有序部分和無序部分
第一次，num[0]~num[N-1]是無序部分，從這N個數(shù)中選出最小的數(shù)，放在序列的第一個位置，
此時，num[0]是有序部分，num[1]~num[N]是無序部分
第二次，num[0]是有序部分，num[1]~num[N]是無序部分，從N-1個數(shù)中選出最小的數(shù)，放在序列的第二個位置，
此時，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;} 運行結(jié)果
看一下程序細節(jié)
時間復雜度
第一次需要遍歷N-1個元素，第二次需要遍歷N-2個元素······
所以時間復雜度是）O（N^2）
然而，細想一下，選擇排序，每一趟遍歷無序部分，卻只為了找到那個最小的數(shù)，效率太低（老子辛辛苦苦在無序序列兜了一圈，只找一個最小值，這哪行，哪像計算機人搜搜扣扣的精神（又扣時間又扣空間））
于是，趕一只羊也是趕，趕兩只羊也是趕。我們跑一趟無序序列，把最小值和最大值都找出來。
代碼：
#include#define N 10#includevoid swap(int *a,int *b)//函數(shù)作用，交換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--; //細節(jié)演示 // for(int i = 0;i 運行結(jié)果：
?
程序細節(jié)：
?對比單向選擇排序算法，雙向選擇排序雖然時間復雜都仍然是O(N^2),但是效率優(yōu)化了50%左右
?填坑：
我們需要排序的序列是num[10] = {9，8，7，6，5，4，3，2，1，0}
先來看一下錯誤代碼
?錯誤細節(jié)，每一次遍歷序列的變化
可以看到?，第一次遍歷，最小值下標是9，最大值下標是0，處理過程是將num[min_index]放在序列開頭,num[max_index]放在序列末尾，即num[0] <——>num[9],即num[0]和num[9]只需要一次換值；
但是因為執(zhí)行兩次swap()（換值函數(shù)），相當于原來序列并沒有發(fā)生變化
在以后的遍歷中，也是這種情況，所以最終結(jié)果是序列沒有任何變化，也就不難理解為何代碼要做如下處理
正確代碼
?正確細節(jié)，每一次遍歷序列的變化
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/124094.html
摘要：當?shù)竭_時等同于直接插入排序，此時序列已基本有序，所有記錄在統(tǒng)一組內(nèi)排好成有序序列。當面對大量數(shù)據(jù)時，希爾排序?qū)⒈戎苯硬迦肱判蚋邇?yōu)勢圖示講解第一趟取增量，所有間隔為的元素分在一組，在各個組中分別進行直接插入排序。 ...
摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為?？焖倥判蚝秃喜⑴判虻乃惴ㄋ俣确謩e表示為和，是算法所需的固定時間量被稱為常量。 分而治之 分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...
摘要：強烈推薦上值得前端學習的數(shù)據(jù)結(jié)構(gòu)與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數(shù)據(jù)結(jié)構(gòu)，提供進一步閱讀的解釋和鏈接。數(shù)據(jù)結(jié)構(gòu)和算法必知必會的個代碼實現(xiàn)。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學好前端，先練好內(nèi)功，內(nèi)功不行，就算招式練的再花哨，終究成不了高手；只有內(nèi)功深厚者，前端之路才會走得...
摘要：題目語言實現(xiàn)現(xiàn)插入排序算法把數(shù)字由小到大進行排序插入排序是把一個記錄插入到已排序的有序序列中，使整個序列在插入該記錄后仍然有序。 ?1、題目 ???????C語言實現(xiàn)現(xiàn)插入排序算法把數(shù)字由小到大進行排序 插入排序是把一個記錄插入到已排序的有序序列中，使整個序列在插入該記錄后仍然有序。插入排序...
閱讀 972·2021-11-22 09:34
閱讀 1153·2021-10-08 10:16
閱讀 1923·2021-07-25 21:42
閱讀 1871·2019-08-30 15:53
閱讀 3595·2019-08-30 13:08
閱讀 2275·2019-08-29 17:30
閱讀 3426·2019-08-29 17:22
閱讀 2284·2019-08-29 15:35
