簡單排序

內(nèi)部排序 和外部排序 內(nèi)部排序 就是 假如 你有2GB的內(nèi)存 剛好 有 2GB以下的 數(shù)據(jù)需要排序 這樣剛好就 將全部的數(shù)據(jù) 儲(chǔ)存到 內(nèi)存當(dāng)中 進(jìn)行了排序 ?這就是內(nèi)部排序 ?與之相反的 外部排序就是 ? 你有1TB的 數(shù)據(jù)需要排序但是 你有 2GB的內(nèi)存 這時(shí)候 ?內(nèi)存 不能盛下 ?數(shù)據(jù) 就需要 開始外部排序了. ? ?

穩(wěn)定排序 ?和不穩(wěn)定排序 ?任意兩個(gè)相等的數(shù)據(jù) 在 ?排序前后的相對(duì)位置不發(fā)生變化. ? (這個(gè) ?比較容易實(shí)現(xiàn))

　　　　沒有任何一種 ?排序在任何情況下 ?都是 最優(yōu)的.

所以說 ?存在 ?就必定有它存在的必然性 ? 在課本里面的東西 ? 只要有 ?就應(yīng)該 好好的學(xué)習(xí) ?.

冒泡排序 .這個(gè)就很簡單了 ?大家應(yīng)該都會(huì) . ?直接附上代碼

冒泡雖然很垃圾,但是冒泡有兩個(gè)有點(diǎn)

1: ?可以對(duì) 鏈表進(jìn)行排序(快速排序 ?好像也可以).

2: ?可以手動(dòng)控制穩(wěn)定性 (快速排序 ?好像也可以).

(小問題 如果有7個(gè)數(shù)字 ?則最多 需要比較幾次? ) -------------21 ?why? ?如何計(jì)算?

//核心思想就是 每一次 都找一個(gè)最大的 然后以此交換 知道將最大的放到最后面 第二次將第二大的 放到 倒數(shù)第二的位置 一次進(jìn)行 n次 這樣的操作.
//穩(wěn)定性的話 就是看你 需要交換的 條件 如果 不是 大于或等于 或者是 小于或等于 就是穩(wěn)定的 只要 相等也交換 就是 不穩(wěn)定的排序.
void Bubble_Sort( ElementType A[], int N ) { for ( P=N-1; P>=0; P-- ) {flag = 0;for( i=0; i<P; i++ ){ /* 泡 一趟冒泡 */if ( A[i] > A[i+1] ){Swap(A[i], A[i+1]);flag = 1; /* 換 標(biāo)識(shí)發(fā)生了交換 */}}if ( flag==0 ) break; /* 換 全程無交換 */ } }　//最好情況：順序 T = O( N )//最壞情況：逆序 T = O( N 2 )

?插入排序: ?就是咱們 打牌的時(shí)候 ?插牌的思想.

1:程序短 ?但是插入排序最重要的存在原因就是啥呢? ? ?后面補(bǔ)充

2:插入排序穩(wěn)定.

?

#include <stdio.h> #include<algorithm> #include <string.h> using namespace std; int main() {int p,i,j,a[10]={2,5,8,9,6,3,1,4,7,0},temp;for(p=1;p<10;p++) // 從原先的 數(shù)組里面 一次選出來一個(gè)數(shù)字 {temp=a[p]; //賦值給 temp for(i=p;i>0&&a[i-1]>temp;i--) //開始 倒著檢查 并且將 大于該牌的牌一次后移一位 直到 剛才選出來的牌 小于 那一張撲克 .( 手里面撲克總量 是 P) {a[i]=a[i-1];}a[i]=temp; //小于了 那么就插入吧 ,剛好剛才還騰出來了 一個(gè) 空位. }for(i=0;i<10;i++)printf("%d",a[i]); }

?

----------------------排序的 思想是什么?-----------------

?

時(shí)間復(fù)雜度下界

?對(duì)于下標(biāo) i<j ,如果A[i]>A[j] , 則稱(i,j)是一對(duì)逆序?qū)?inversion)

?逆序?qū)Φ挠?jì)算

?

問題：序列{34, 8, 64, 51, 32, 21} 中有多少逆序?qū)?#xff1f; 9對(duì) (34, 8) (34, 32) (34, 21) (64, 51) (64, 32) (64, 21) (51, 32) (51, 21) (32, 21)

?所以 ? 排序的 的si

?

?

交換2 個(gè)相鄰元素正好消去1 個(gè)逆序?qū)?#xff01; ?所以 ?冒泡 和插入 在這一個(gè) 數(shù)組里面 ?都需要交換9次.

?

插入排序：T(N, I) = O( N+I )
— 如果序列 基本有序

?

思考!!!!!!!!!!

?

定理:任意N個(gè)不同的元素組成的序列平均具有N(N-1)/4 個(gè) 逆序?qū)? (平均哦)
定理:任何僅以交換相鄰兩元素來排序的算法,其平均時(shí)間復(fù)雜度為 N^2

---------------------有沒有 靈光乍現(xiàn)?------------------------

?意思就是 我們想提高算法的效率 我們可以從 ?每次交換 消去盡可能多的 逆序?qū)?

?

-----------------------怎么實(shí)現(xiàn)呢?---------------------------------

我們可以 交換 相鄰較遠(yuǎn)的 逆序?qū)?注意觀察 上面的 ?9個(gè) 逆序?qū)? ?這樣一次交換就可以消去 ?多個(gè) 逆序?qū)?

?

?

?

--------簡單排序到此為止 ?下面 就去 實(shí)現(xiàn) 一次交換 消去 ?N個(gè) 逆序?qū)?-----------

?

轉(zhuǎn)載于:https://www.cnblogs.com/A-FM/p/5158047.html

總結(jié)

以上是生活随笔為你收集整理的-----------简单排序-------------的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。