免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

冒泡排序

• 冒泡排序 思想

  這個方法就是在每一趟的循環(huán)中依次比較前后兩個元素之間的大小，然后進行一個交換。這樣在多趟循環(huán)中實現(xiàn)無序數(shù)列的有序排列。下面是使用matlab實現(xiàn)的

• eg:冒泡算法的原理是：根據(jù)輕氣泡不能在重氣泡之下的原則，按一定順序掃描數(shù)組：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。到此排序結(jié)束。

  比如對{6,2,3,1,7}進行冒泡排序（從小到大）

  第一次遍歷結(jié)束后，結(jié)果為：1 6 3 2 7

  第二次遍歷結(jié)束后，結(jié)果為：1 2 6 3 7

  第三次遍歷結(jié)束后，結(jié)果為：1 2 3 6 7

  第n此遍歷結(jié)束后，數(shù)組的前n個數(shù)字組成的子序列是有序的。

clcclear close% aa=round(rand(1,100000)*500000000) ;%產(chǎn)生隨機數(shù)組% a=aa;a=[0 6,5,3,1,8,7,2,4];N=size(a,2);for i=1:N     for j=1:N-i        if a(1,j)>a(1,j+1)            temp=a(1,j);            a(1,j)=a(1,j+1);            a(1,j+1)=temp;        end    endend

• 算法時間復(fù)雜度分析

  從上面的代碼可以看出來，外層循環(huán)也就是趟數(shù)最多為N?1$N?1$次，而內(nèi)層循環(huán)比較次數(shù)最多為N$N$次，最少為1次，所以平均

  次數(shù)為N+12$\frac{N+1}{2}$次，所以總的次數(shù)為T(n)=(N?1)×N+12=N2?12$T(n)=(N?1)\times \frac{N+1}{2}=\frac{N^2?1}{2}$次，所以其算法時間復(fù)雜 度為O(n2)$O(n^2)$.

• 冒泡改進
  有時候碰到的序列里面有大部分是有序，只有少數(shù)的無序的，那么有可能就不需要比較那么多趟去實現(xiàn)這個冒泡，因此，可以設(shè)置一個旗幟變量exchangeFlag，發(fā)生元素交換了，則exchangeFlag=1，否則為0.
  那么改進之后的代碼為：

exchangeFlag=true;ticfor i=1:m     exchangeFlag=0    for j=1:m-i        if a(1,j)>a(1,j+1)            temp=a(1,j);            a(1,j)=a(1,j+1);            a(1,j+1)=temp;            exchangeFlag=1        end    end    if ~exchangeFlag        break;    end end

這里就有一個旗幟變量，進行一個統(tǒng)計是否發(fā)生了元素交換。這樣的當一個序列里面大部分有序，只有少數(shù)無序的時候就比較使用，不要去試行N?1$N?1$趟的比較了。

• Python 實現(xiàn)

for i in range(0,m):    exchangeFlag=0    for j in range(0,m-i-1):        if a[j]>a[j+1]:            a[j],a[j+1]=a[j+1],a[j]            exchangeFlag=1    if ~exchangeFlag:        breakprint(a)

插入排序

• 插入排序的思想

  插入排序是在一個已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。

• matlab代碼

clcclearclose alla=[6 5 3 1 8 7 2 4 -1];m=size(a,2);ticfor i=2:m    if a(1,i)<a(1,i-1)        j=i-1; %記錄這個位置        temp=a(i); %將這個位置的元素值取出來        a(i)=a(i-1); %將大的元素后移        while (j-1)>0 %這里實現(xiàn)待插入的元素和已排好序列進行比較            if temp<a(j-1)                a(j)=a(j-1);            else                break;            end            j=j-1;        end        a(j)=temp;    endendtoc

測試輸出結(jié)果為：

    -1     1     2     3     4     5     6     7     8

• 算法時間復(fù)雜度分析

  對于第i$i$個元素來說，其需要比較的次數(shù)為 i?1$i?1$ 次，那么對于有N$N$個元素的序列來說，最壞的情況下，其需要的次數(shù)為

  T(n)=1+2+3+?+(n?1)=n(n?1)2$T(n)=1+2+3+?+(n?1)=\frac{n(n?1)}{2}$,也就是說其算法時間復(fù)雜度為 O(n2)$O(n^2)$ 。

• python實現(xiàn)

a=[6,5,3,1,8,7,2,4]m=a.__len__()for i in range(1,m):    if a[i]<a[i-1]:        j=i-1        temp=a[i]        a[i]=a[i-1]        while (j-1)>=0:            if temp<a[j-1]:                a[j]=a[j-1]            else:                break            j=j-1        a[j]=tempprint(a)

簡單選擇排序

• 簡單選擇排序思想

  在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。

• matlab代碼實現(xiàn)

a=[6 5 3 1 8 7 2 4];m=size(a,2);for i=1:m    minValue=min(a(1,i:end)); %找到剩余序列的最大值    minValueIndex=find(a(1,i:end)==min(a(1,i:end)))+i-1; %找到剩余序列最大值所在原序列中的索引值    a(1,minValueIndex)=a(i); %交換    a(i)=minValue;end

• 算法時間復(fù)雜度分析

  第一趟，需要比較 N?1$N?1$ 次，第二趟需要比較 N?2$N?2$ 次，?$?$，第 N?1$N?1$ 次需要比較1次就可以了。因此總的比較次數(shù)

  為：T(n)=1+2+3+?+(n?1)=n(n?1)2$T(n)=1+2+3+?+(n?1)=\frac{n(n?1)}{2}$,也就是說其算法時間復(fù)雜度為 O(n2)$O(n^2)$ 。

今天就先學(xué)些到這，后續(xù)繼續(xù)學(xué)習(xí)補充，希望大神路過指點。