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