如何分析一個排序算法?

1,排序算法的執(zhí)行效率

執(zhí)行效率包括:
最好情況胀蛮、最壞情況、平均情況時間復(fù)雜度,
時間復(fù)雜度的系數(shù)癌蚁、常數(shù)浙垫、低階,
比較次數(shù)和交換(或移動)次數(shù)

2,排序算法的內(nèi)存消耗

空間復(fù)雜度為O(1)的排序算法為原地排序

3,排序算法的穩(wěn)定性

穩(wěn)定排序算法:就是兩個相同的數(shù)據(jù),經(jīng)過排序之后,前后位置沒有發(fā)生改變.
例:

var dic = [{"key":1,"name":"張1"},{"key":5,"name":"張5"},{"key":3,"name":"張31"},{"key":2,"name":"張2"},{"key":3,"name":"張32"}];

根據(jù)key的值將數(shù)組進(jìn)行排序.
穩(wěn)定排序的結(jié)果:

var dic = [{"key":1,"name":"張1"},{"key":2,"name":"張2"},{"key":3,"name":"張31"},{"key":3,"name":"張32"},{"key":5,"name":"張5"}];

張31和張32的順序未發(fā)生改變

冒泡排序

原理

比較相鄰的兩個數(shù)據(jù),看是否滿足大小要求,如果不滿足就讓他倆互換.重復(fù)n次,就完成了n個數(shù)據(jù)的排序

代碼實(shí)現(xiàn)

- (NSArray *)bubbleSortWithArray:(NSArray *)array
{
    if (array.count <= 1) {
        return array;
    }
    
    NSMutableArray *tmpArray = [NSMutableArray arrayWithArray:array];
    
    for (int i = 0; i < tmpArray.count; i ++) {
        BOOL isNoChange = NO;
        for (int j = 0; j < tmpArray.count - i - 1; j ++) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                isNoChange = YES;
            }
        }
        if (!isNoChange) {
            return tmpArray;
        }
    }
    return tmpArray;
}

是否為原地排序

是,只做相鄰兩個數(shù)的交換,空間復(fù)雜度為O(1)

是否為穩(wěn)定排序

是,當(dāng)相鄰兩個數(shù)據(jù)大小相等的時候我們可以不交換數(shù)據(jù).

時間復(fù)雜度

最好時間復(fù)雜度

要排序的數(shù)據(jù)已經(jīng)是有序的了,我們只需要一次冒泡就可以結(jié)束排序,所以最好情況時間復(fù)雜度是O(n)

最壞時間復(fù)雜度

要排序的數(shù)據(jù)是倒序的,那么我們需要n次冒泡才可以結(jié)束排序,所以最壞情況時間復(fù)雜度是O(n2)

平均情況時間復(fù)雜度

平均情況時間復(fù)雜度我們可以通過有序度和逆序度這兩個概念來進(jìn)行分析.有數(shù)據(jù)1,2,3,4,5,6 這是一個完全有序的數(shù)據(jù),我們稱它為滿有序度 公式為 n(n-1)/2. 這個數(shù)據(jù)的有序度就是6(6-1)/2=15,逆序度就是0. 滿有序度=有序度+逆序度.
計算平均情況時間復(fù)雜度我們可以取這個公式的中間值n*(n-1)/4,所以平均情況時間復(fù)雜度就是O(n2).

插入排序

原理

我們將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間，已排序區(qū)間和未排序區(qū)間恕沫。初始已排序區(qū)間只有一個元素监憎，就是數(shù)組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素婶溯，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序偷霉。重復(fù)這個過程迄委，直到未排序區(qū)間中元素為空，算法結(jié)束类少。

插入排序原理

代碼實(shí)現(xiàn)

// 插入排序叙身，a表示數(shù)組，n表示數(shù)組大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 數(shù)據(jù)移動
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入數(shù)據(jù)
  }
}

是否為原地排序

是,并不需要額外的存儲空間,空間復(fù)雜度為O(1).

是否為穩(wěn)定排序

是,我們可以選擇將后面出現(xiàn)的元素插入到前面出現(xiàn)元素的后面,這樣就保持原有的順序不變.

時間復(fù)雜度

最好時間復(fù)雜度

最好的情況就是數(shù)組是有序的,這個時候的復(fù)雜度為O(n).

最壞時間復(fù)雜度

最壞的情況就是數(shù)組是完全倒序的,這個時候的復(fù)雜度是O(n2).

選擇排序

原理

選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序硫狞，也分已排序區(qū)間和未排序區(qū)間信轿。但是選擇排序每次會從未排序區(qū)間中找到最小的元素晃痴，將其放到已排序區(qū)間的末尾。

選擇排序

是否為原地排序

是,并不需要額外的存儲空間,空間復(fù)雜度為O(1).

是否為穩(wěn)定排序

不是财忽，選擇排序每次都要找剩余未排序元素中的最小值倘核，并和前面的元素交換位置，這樣破壞了穩(wěn)定性即彪。

時間復(fù)雜度

選擇排序的最好情況時間復(fù)雜度紧唱、最壞情況和平均情況時間復(fù)雜度都為 O(n2).

總結(jié)

歸并排序

原理

歸并排序的核心思想還是蠻簡單的。如果要排序一個數(shù)組隶校，我們先把數(shù)組從中間分成前后兩部分漏益，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起深胳，這樣整個數(shù)組就都有序了绰疤。
歸并排序使用的是分治思想。分治舞终，顧名思義轻庆，就是分而治之，將一個大問題分解成小的子問題來解決权埠。小的子問題解決了榨了，大問題也就解決了。

歸并原理

歸并排序這種借助分治思想來完成的排序需要使用遞歸技巧來實(shí)現(xiàn),下面的是遞推公式:

遞推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

終止條件：
p >= r 不用再繼續(xù)分解

解釋:
merge_sort(p…r) 表示攘蔽，給下標(biāo)從 p 到 r 之間的數(shù)組排序龙屉。我們將這個排序問題轉(zhuǎn)化為了兩個子問題，merge_sort(p…q) 和 merge_sort(q+1…r)满俗，其中下標(biāo) q 等于 p 和 r 的中間位置转捕，也就是 (p+r)/2。當(dāng)下標(biāo)從 p 到 q 和從 q+1 到 r 這兩個子數(shù)組都排好序之后唆垃，我們再將兩個有序的子數(shù)組合并在一起五芝，這樣下標(biāo)從 p 到 r 之間的數(shù)據(jù)就也排好序了
代碼:

// 歸并排序算法, A是數(shù)組，n表示數(shù)組大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 遞歸調(diào)用函數(shù)
merge_sort_c(A, p, r) {
  // 遞歸終止條件
  if p >= r  then return

  // 取p到r之間的中間位置q
  q = (p+r) / 2
  // 分治遞歸
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 將A[p...q]和A[q+1...r]合并為A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

merge(A[p...r], A[p...q], A[q+1...r]) {
  var i := p辕万，j := q+1枢步，k := 0 // 初始化變量i, j, k
  var tmp := new array[0...r-p] // 申請一個大小跟A[p...r]一樣的臨時數(shù)組
  while i<=q AND j<=r do {
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++等于i:=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }
  
  // 判斷哪個子數(shù)組中有剩余的數(shù)據(jù)
  var start := i，end := q
  if j<=r then start := j, end:=r
  
  // 將剩余的數(shù)據(jù)拷貝到臨時數(shù)組tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }
  
  // 將tmp中的數(shù)組拷貝回A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

merge函數(shù)解析:
你可能已經(jīng)發(fā)現(xiàn)了渐尿，merge(A[p...r], A[p...q], A[q+1...r]) 這個函數(shù)的作用就是醉途，將已經(jīng)有序的 A[p...q]和 A[q+1....r]合并成一個有序的數(shù)組，并且放入 A[p....r]砖茸。那這個過程具體該如何做呢隘擎？如圖所示，我們申請一個臨時數(shù)組 tmp凉夯，大小與 A[p...r]相同货葬。我們用兩個游標(biāo) i 和 j采幌，分別指向 A[p...q]和 A[q+1...r]的第一個元素。比較這兩個元素 A[i]和 A[j]震桶，如果 A[i]<=A[j]休傍，我們就把 A[i]放入到臨時數(shù)組 tmp，并且 i 后移一位尼夺，否則將 A[j]放入到數(shù)組 tmp尊残，j 后移一位。繼續(xù)上述比較過程淤堵，直到其中一個子數(shù)組中的所有數(shù)據(jù)都放入臨時數(shù)組中寝衫，再把另一個數(shù)組中的數(shù)據(jù)依次加入到臨時數(shù)組的末尾，這個時候拐邪，臨時數(shù)組中存儲的就是兩個子數(shù)組合并之后的結(jié)果了慰毅。最后再把臨時數(shù)組 tmp 中的數(shù)據(jù)拷貝到原數(shù)組 A[p...r]中。

是否為原地排序

不是,空間復(fù)雜度是 O(n)扎阶。

是否為穩(wěn)定排序

歸并排序穩(wěn)不穩(wěn)定關(guān)鍵要看 merge() 函數(shù)汹胃，也就是兩個有序子數(shù)組合并成一個有序數(shù)組的那部分代碼。在合并的過程中东臀，如果 A[p...q]和 A[q+1...r]之間有值相同的元素着饥，那我們可以像偽代碼中那樣，先把 A[p...q]中的元素放入 tmp 數(shù)組惰赋。這樣就保證了值相同的元素宰掉，在合并前后的先后順序不變。所以赁濒，歸并排序是一個穩(wěn)定的排序算法轨奄。

時間復(fù)雜度

歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無關(guān)，所以其時間復(fù)雜度是非常穩(wěn)定的拒炎，不管是最好情況挪拟、最壞情況，還是平均情況击你，時間復(fù)雜度都是 O(nlogn)玉组。

快速排序

原理

如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到 r 之間的任意一個數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）丁侄。我們遍歷 p 到 r 之間的數(shù)據(jù)球切，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊绒障，將 pivot 放到中間。經(jīng)過這一步驟之后捍歪，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個部分户辱，前面 p 到 q-1 之間都是小于 pivot 的鸵钝，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的庐镐。根據(jù)分治恩商、遞歸的處理思想，我們可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r 之間的數(shù)據(jù)必逆，直到區(qū)間縮小為 1怠堪，就說明所有的數(shù)據(jù)都有序了。
代碼:

func sort(arr:inout Array<Int>,left:Int,right:Int) {
    if left >= right {
        return;
    }
    
    
    let pivot:Int = pivotMethod(arr: &arr, left: left, right: right);

    sort(arr: &arr, left: 0, right: pivot - 1);
    sort(arr: &arr, left: pivot + 1, right: right);
}
//以一個基數(shù)把數(shù)組分區(qū)
func pivotMethod(arr:inout Array<Int>,left:Int,right:Int) -> Int {
    let pivot:Int = arr[right];
    var i = left;
    
    for j in 0..<arr.count {
        if arr[i] < pivot {
            // 交換數(shù)組內(nèi)的元素
            arr.swapAt(i, j);
            i = i + 1;
        }
    }
    arr.swapAt(i, right);
    return i;
}

var arr:[Int] = [4,1,3,6,8,5,9];

sort(arr: &arr, left: 0, right: arr.count - 1);
print(arr);

pivotMethod說明:

pivotMethod說明

是否為原地排序

是,在排序的時候沒有產(chǎn)生額外的空間開銷.

是否為穩(wěn)定排序

不是,在pivotMethod步驟的時候元素位置會發(fā)生交換.

時間復(fù)雜度

在大部分情況下快排的時間復(fù)雜度都可以做到 O(nlogn)腐泻，只有在極端情況下决乎，才會退化到 O(n2)。

優(yōu)化快速排序

如果數(shù)據(jù)原來就是有序的或者接近有序的派桩，每次分區(qū)點(diǎn)都選擇最后一個數(shù)據(jù)构诚，那快速排序算法就會變得非常糟糕，時間復(fù)雜度就會退化為 O(n2)铆惑。實(shí)際上范嘱，這種 O(n2) 時間復(fù)雜度出現(xiàn)的主要原因還是因?yàn)槲覀兎謪^(qū)點(diǎn)選得不夠合理。最理想的分區(qū)點(diǎn)是：被分區(qū)點(diǎn)分開的兩個分區(qū)中员魏，數(shù)據(jù)的數(shù)量差不多丑蛤。如果很粗暴地直接選擇第一個或者最后一個數(shù)據(jù)作為分區(qū)點(diǎn)，不考慮數(shù)據(jù)的特點(diǎn)撕阎，肯定會出現(xiàn)最壞情況O(n2)受裹。為了提高排序算法的性能，我們也要盡可能地讓每次分區(qū)都比較平均。這里介紹兩個比較常用棉饶、比較簡單的分區(qū)算法厦章。

1. 三數(shù)取中法我們從區(qū)間的首、尾照藻、中間袜啃，分別取出一個數(shù)，然后對比大小幸缕，取這 3 個數(shù)的中間值作為分區(qū)點(diǎn)群发。這樣每間隔某個固定的長度，取數(shù)據(jù)出來比較发乔，將中間值作為分區(qū)點(diǎn)的分區(qū)算法熟妓，肯定要比單純?nèi)∧骋粋€數(shù)據(jù)更好。但是列疗，如果要排序的數(shù)組比較大滑蚯，那“三數(shù)取中”可能就不夠了，可能要“五數(shù)取中”或者“十?dāng)?shù)取中”抵栈。
2. 隨機(jī)法隨機(jī)法就是每次從要排序的區(qū)間中告材，隨機(jī)選擇一個元素作為分區(qū)點(diǎn)。這種方法并不能保證每次分區(qū)點(diǎn)都選的比較好古劲，但是從概率的角度來看斥赋，也不大可能會出現(xiàn)每次分區(qū)點(diǎn)都選得很差的情況，所以平均情況下产艾，這樣選的分區(qū)點(diǎn)是比較好的疤剑。時間復(fù)雜度退化為最糟糕的 O(n2) 的情況，出現(xiàn)的可能性不大闷堡。

歸并排序和快速排序的區(qū)別

區(qū)別

ps:內(nèi)容整理自極客時間--數(shù)據(jù)結(jié)構(gòu)與算法之美