排序算法講義

1、計算機程序設(shè)計八排序?qū)⒁唤M數(shù)據(jù)按由小到大或者由大到小的順序進行排列。選擇排序(Selection Sort)冒泡排序(Bubble Sort)插入排序(Insertion Sort) 希爾排序(Shell Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 歸并排序(Merge Sort) 基數(shù)排序(xxx Sort) 選擇排序 將將 29 18 87 56 3 27 按由小到大排序按由小到大排序29 18 87 5632718 87 56327329 87 56 18 2729 87 56327329 87 56 18 27329 87 56 18 27318 87

2、56 29 27第1趟318 87 56 29 27第2趟318 56 87 29 27318 29 87 56 27318 27 87 56 29318 27 87 56 29第3趟318 27 56 87 29318 27 29 87 56318 27 29 87 56第4趟318 27 29 56 87第5趟選擇排序的基本思想是： 對待排序的n個數(shù)據(jù)進行n-1遍的處理，第1遍處理是將a2.n中最小者與a1交換位置，第2遍處理是將a3.n中最小者與a2交換位置，.，第i遍處理是將ai+1.n中最小者與ai交換位置。這樣，經(jīng)過i遍處理之后，前i個記錄的位置就已經(jīng)按從小到大的順序排列好了。 i

3、nt a1001;int i,j,temp;輸入n個數(shù)字到a中/選擇排序輸出排序結(jié)果選擇排序特點分析時間復(fù)雜度：穩(wěn)定性：時間復(fù)雜度簡單的說就是程序循環(huán)執(zhí)行的總的次數(shù)。排序算法的穩(wěn)定性是指 值相同的數(shù)字在排序前后其相對位置是否要發(fā)生改變，若要改變就是不穩(wěn)定，否則就是穩(wěn)定的?？偣脖容^ n(n-1)/2 次 時間復(fù)雜度為O(n2)不穩(wěn)定不穩(wěn)定練習(xí)：排序（isort.cpp）輸入n（n=80000）個整數(shù)，排序后，按由小到大的順序輸出。輸入格式(輸入文件indata.in)： 第一行一個整數(shù)n 第二行n個由空格間隔的整數(shù)輸出格式(輸出文件outdata.out)： 只有一行：n個由小到大排列的整數(shù)，用

4、空格間隔樣例輸入：816 7 23 8 99 120 35 -2樣例輸出：-2 7 8 16 23 35 99 120 文件輸入輸出打開輸入文件：freopen(d:/indata.txt,r,stdin);作用是：打開d盤已存在的indata.txt文件，從該文件中讀入數(shù)據(jù)。打開輸出文件：freopen(d:/outdata.txt,w,stdout);作用是：在d盤新建立一個名為outdata.txt的文件，將數(shù)據(jù)寫入該文件fclose(stdin); /關(guān)閉輸入文件fclose(stdout); /關(guān)閉輸出文件freopen(輸入文件名,r,stdin);freopen(輸出文件名,w,

5、stdout);#include using namespace std;int main() int a101,n,i,j,temp; scanf(%d,&n); for(i=1;i=n;i+) scanf(%d,&ai); for(i=1;i=n-1;i+) for(j=i+1;jaj) temp=ai; ai=aj; aj=temp; for(i=1;i=n;i+)printf(%d , ai);return 0; 冒泡排序 將將 29 18 87 56 3 27 按由小到大排序按由小到大排序29 18 87 5632729 18 87 5632718 29 87 563

6、2718 29 87 5632718 29 56 8732718 29 56 8732718 29 56387 2718 29 56387 2718 29 56327 8718 29 56327 8718 29 56327 87第1趟18 29356 27 8718 29356 27 8718 29327 56 8718 29327 56 87第2趟18 29327 56 8718329 27 56 8718329 27 56 8718327 29 56 8718327 29 56 87第3趟18327 29 56 87318 27 29 56 87318 27 29 56 87318 27

7、29 56 87第4趟318 27 29 56 87第5趟冒泡排序基本思想是:對待排序的數(shù)字進行兩兩比較,如發(fā)現(xiàn)兩個數(shù)字是反序的,則進行交換,直到無反序的記錄為止。 冒泡排序 將將 29 18 87 56 3 27 按由小到大排序按由小到大排序冒泡排序特點分析時間復(fù)雜度：穩(wěn)定性：總共比較 n(n-1)/2 次 時間復(fù)雜度為O(n2)穩(wěn)定穩(wěn)定(29) (188756327)(1829)(87 56 327)(182987) (56327)(18295687)(327)( 318295687) (27)(31827295687)插入排序 將將 29 18 87 56 3 27 按由小到大排序按由小

8、到大排序算法實現(xiàn)在數(shù)組中增加元素a0作為臨時空間,把待插入的數(shù)放到里面。第i趟排序，即ai的插入過程為： 保存a0=ai j=i-1 如果aj=a0（即待排序的ai），則aj+1=a0 ，完成插入； 否則，將aj后移一個位置：Aj+1= Aj ；繼續(xù)執(zhí)行程序代碼 for(i=2;ia0) aj+1=aj; j-; aj+1=a0;（1）穩(wěn)定性：穩(wěn)定（2）時間復(fù)雜度： O(n2)初始數(shù)據(jù)正序，總比較次數(shù)：n-1初始數(shù)據(jù)逆序，總比較次數(shù)：(n2+n-1)/2= O(n2)初始數(shù)據(jù)無序，第i趟平均比較次數(shù)(i+1)/2，總次數(shù)為：(n2+3n)/4=O(n2)可見，原始數(shù)據(jù)越趨向正序，比較次數(shù)和移動

9、次數(shù)越少。)(22222nOnnini課堂練習(xí)：學(xué)生成績(student.cpp) 某年級有n(n=5000)個學(xué)生，學(xué)號1到n，現(xiàn)給出這n個學(xué)生的語文和數(shù)學(xué)成績，請按數(shù)學(xué)成績的由高到低對這n個學(xué)生進行排序。數(shù)學(xué)成績相同的學(xué)生，按語文成績由高到低排序。輸入格式：第一行，一個整數(shù)n，表示n個學(xué)生第二行，n個空格間隔的整數(shù)，表示學(xué)號1到n的學(xué)生的數(shù)學(xué)成績第三行，n個空格間隔的整數(shù)，表示學(xué)號1到n的學(xué)生的語文成績輸出格式：排序后輸出n行，每行代表一個學(xué)生。每行兩個數(shù)字，分為該生的數(shù)學(xué)和語文成績。樣例輸入：667 88 91 88 99 8880 92 69 70 85 77樣例輸出99 8591 6

10、988 9288 7788 7067 80int main()int yu5001,shu5001,n,i,j,temp; scanf(%d,&n); for(i=1;i=n;i+)scanf(%d,&shui); for(i=1;i=n;i+)scanf(%d,&yui); for(i=1;i=n-1;i+) for(j=1;j=n-i;j+) if(shujshuj+1)|(shuj=shuj+1)&(yujyuj+1) temp=shuj; shuj=shuj+1; shuj+1=temp; temp=yuj; yuj=yuj+1; yuj+1=temp;

11、 for(i=1;i=n;i+)printf(%d %dn,shui,yui); return 0; 程序代碼 for(i=2;i=n;i+) shu0=shui; yu0=yuj; j=i-1; while(shujshu0) |(shuj=shu0)&(yujyu0) shuj+1=shuj; yuj+1=yuj; j-; shuj+1=shu0; yuj+1=yu0;1839329快速排序 將將 29 96 18 56 3 56 39 77 按由小到大排序按由小到大排序思想：每次找一個數(shù)位基準，把小于等于它的放到這個數(shù)的左邊，把大于等于它的放到它的右邊29 96 18 56 37

12、756 39 3939 2996xa12345678下標9656356y18 56773956565612345xy2931839189639 29 563929void qsort(int l,int r) int x,y,mid,temp; x=l; y=r; mid=al; do while(axmid)y- -; if (x=y) temp=ax; ax=ay; ay=temp; x+; y-; while(x=y); if(ly)qsort(l,y); if(xr)qsort(x,r);每排完一趟，小于等于基準值的，在y的左側(cè)。大于等于基準值的在x的右側(cè)。8,12,56,99,18#

13、include #include using namespace std;using namespace std;int int a30a301 1; ;int int i,n;i,n;void qsort(int l,int r)void qsort(int l,int r) int x,y,mid,temp; int x,y,mid,temp; x=l; y=r; mid=al; x=l; y=r; mid=al; do do while(axmid)x+; while(axmid)y-; while(aymid)y-; if (x=y) if (x=y) temp=ax; ax=ay; ay=temp; temp=ax; ax=ay; ay=temp; x+; y-; x+; y-; while(x=y);while(x=y); if(ly)qsort(l,y); if(ly)qsort(l,y); if(xr)qsort(x,r); if(xr)qsort(x,r); int main()int main() scanf(%d,&n);scanf(%d,&n); for for( (i i=1;i=n;i+)scanf(%d,&