一、幾種常見(jiàn)算法的介紹及復(fù)雜度分析
1.基本概念
1.1穩(wěn)定排序(stable sort)和非穩(wěn)定排序
穩(wěn)定排序是所有相等的數(shù)經(jīng)過(guò)某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，。反之，就是非穩(wěn)定的排序。
比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過(guò)某種排序后為a1,a2,a4,a3,a5，
則我們說(shuō)這種排序是穩(wěn)定的，因?yàn)閍2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。
1.2內(nèi)排序( internal sorting )和外排序( external sorting)
在排序過(guò)程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱(chēng)為內(nèi)排序； 在排序過(guò)程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱(chēng)為外排序。
1.3算法的時(shí)間復(fù)雜度和空間復(fù)雜度
所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。 一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。
2.幾種常見(jiàn)算法
2.1冒泡排序 （Bubble Sort）
冒泡排序方法是最簡(jiǎn)單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個(gè)序列，并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì)，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時(shí)，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時(shí)，不必檢查第i高位置以上的元素，因?yàn)榻?jīng)過(guò)前面i-1遍的處理，它們已正確地排好序。
冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n ^2)。
2.2選擇排序 （Selection Sort）
選擇排序的基本思想是對(duì)待排序的記錄序列進(jìn)行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經(jīng)過(guò)i遍處理之后，前i個(gè)記錄的位置已經(jīng)是正確的了。
選擇排序是不穩(wěn)定的。算法復(fù)雜度是O(n ^2 )。
2.3插入排序 （Insertion Sort）
插入排序的基本思想是，經(jīng)過(guò)i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i]又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤L[i]，則L[1..i]已排好序，第i遍處理就結(jié)束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個(gè)位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時(shí)為止。圖1演示了對(duì)4個(gè)元素進(jìn)行插入排序的過(guò)程，共需要(a),(b),(c)三次插入。
直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n ^2)
2.4堆排序
堆排序是一種樹(shù)形選擇排序，在排序過(guò)程中，將A[n]看成是完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。
堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog n)。
2.5歸并排序
設(shè)有兩個(gè)有序（升序）序列存儲(chǔ)在同一數(shù)組中相鄰的位置上，不妨設(shè)為A[l..m]，A[m+1..h]，將它們歸并為一個(gè)有序數(shù)列，并存儲(chǔ)在A[l..h]。
其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是O(nlog2n)。
2.6快速排序
快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過(guò)一趟掃描后，使得排序序列的長(zhǎng)度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少1?？焖倥判蛲ㄟ^(guò)一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。
快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n ^2)。
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶(hù)發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
