>>>時間複雜度
計算時間複雜度
主要是看語句執行的次數
舉例
例一 O(N)
核心就是找到當循環結束時，循環體執行了多少次
看循環的條件 i<n的時候終止 是以n與i有關，我們需要找出i與n的關系，我們先找出執行次數與i的值的關系 即
i = 2x+1
循環次數 1 2 3 4 。。。 x
i的值 3 5 7 9 。。。 2x+1
是以得到當
2x+1 >= n
時 即循環到第x時，循環終止 能得到循環中的語句執行了x次 将x用n表示
x= (n-1)/2
即循環了 （n-1)/2次 是以執行了 (n-1)/2次 即T(n) = (n-1)/2 省去常數和n的系數，是以
時間複雜度為O(n)
void fun1(int n)
{
int i=1,k=100;
while(i<n)
{
k=k+1;
i+=2;
}
}
例二
int i = 1;
while(i<n){
i = i * 2;
}
可以得出，終止條件與i的值有關。我們列舉出循環次數x與i的關系 得出
i = 2^x
循環次數x 1 2 3 4 ... x
i的值 2 4 8 16 ... 2^x
因為當i<n時循環結束，即 2^x < n ，此時語句執行了x次， x用n表示
x = log2N (以2為底)
, 即當執行log2N次時，循環結束，即一共執行了log2N次，是以時間複雜度就是
O(log2N)
;
例三
平方階O(n²) 就更容易了解了，
如果把 O(n) 的代碼再嵌套循環一遍，它的時間複雜度就是 O(n²)
，這段代碼其實就是嵌套了2層n循環，它的時間複雜度就是 O(n*n)，即 O(n²) 如果将其中一層循環的n改成m，那它的時間複雜度就變成了
O(m*n)
for(int i = 1;i<=n;i++){
for(int j = 1; j<=n;j++){
xxx...
}
}
常見時間複雜度
排序算法的時間複雜度
排序算法的穩定性解釋
簡單地說就是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩定的。反之，就是非穩定的。
選擇排序是不穩定的，舉個例子：
序列5 8 5 2 9，第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，是以選擇排序不是一個穩定的排序算法
排序算法總結
排序算法總結
菜鳥教程
1.冒泡排序 (兩兩比較并交換)
(兩兩比較并交換)
1.1圖示
(從小到大進行排序)
有點類似雙指針，一個指針p1從頭開始，一個指針p2從下一位開始，如果p1指向的元素大于p2指向的元素，那麼交換兩個數，然後p1走到p2的位置，P2繼續後移，這樣做會将最大的元素放到後面，
循環次數分析
外層循環
假設有n個數，根據上面的圖示，我們會将
n-1
個最大數放到數組的最後，是以外層需要循環n-1次，每一次找到一個大數放到後面
内層循環
然後每一趟的話，我們需要使用指針來對元素進行一一的比較，然後找出這一趟的最大值放到最後，理論上說我們每一次需要比較
n-1
次，即循環n-1次，但是我們知道第一次循環會将整個數組的最大數放到最後，需要循環(n-1)次，那麼第二趟就無需比較最後一個數和它前面的數了，那麼需要比較(n-2次),依次類推，每一趟我們需要比較的元素個數(即内層循環次數)就是
n-1-(趟數(從0開始))
即第一趟需要比較
n-1-0
個元素
第二趟需要比較
n-1-1個
元素
。。。。
1.2代碼分析(+優化)
public void bubbleSort(int[] nums) {
//外層循環 控制趟數
for (int i = 0; i < nums.length -1 ; i++) {
//設定優化标志位 當某一次的過程中 沒有發生過資料的交換 說明所有元素都已經有序就不需要在進行了 直接break即可
boolean flag = true;
int temp = 0;
//内層循環 控制元素比較的次數
for (int j = 0; j < nums.length - 1 - i; j++) {
//j相當于前指針 j+1相當于後指針 前面的數比後面的大 就交換
if (nums[j] > nums[j + 1]) {
//将這一趟的flag置為false，說明交換過元素 即數組還不是有序的
flag = false;
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
//flag為true 說明這一趟沒有發生過交換 即資料都是有序的 直接結束
if (flag == true) {
break;
}
}
}
1.3算法分析
根據1.2的代碼實作，可以得到，
- 冒泡排序的時間複雜度是
O(n^n)
平均時間複雜度是
O(n^n)
，最壞的時間複雜度也是
O(n^n)
，
- 空間複雜度是
O(1)
-
穩定的排序 關鍵字相同的記錄不會交換次序
2.快速排序 (遞歸排序)*
(遞歸排序)*
2.1圖示
2.2思路分析
快速排序的核心就是分區間處理
- 第一步：确定一個
分界點值mark
- 第二步：調整區間，使得整個區間一分為二時，左區間的數
[]
(]
- 第三步：遞歸處理左右兩個區間
如何調整區間
- 最簡單的方法就是新開兩個數組a和b，周遊兩次原數組，比mark大的放a數組，比mark小的放b數組，然後依次重新為原數組填充資料 但是這種需要使用額外空間，不推薦使用
- 我們可以使用雙指針算法，一個指針l從頭走，一個指針r從尾部走，l指針指向的數如果大于等于mark時停下，r指針如果小于等于mark時停下，交換兩個數，如果r指針和l指針相遇或者r指針<l指針時結束，
此時r指針左邊的數(包括r指針指向的數)都是小于等于mark的，r指針右邊的數(不包括r指針指向的數)都是大于等于mark的
l指針左邊的數(不包括l指針指向的數)都是小于等于mark的，l指針右邊的數(包括l指針指向的數)都是大于等于mark的
舉例：
比如有下面一組數 我們以array[0]即5為mark 劃分兩個區間 然後雙指針
5 6 7 2 3 8 9
l指針第一次指向5等于mark 停下，然後r指針指向9大于mark繼續向前走，指向8大于mark繼續向前，然後走到3的位置小于mark停下，此時交換l指針和r指針指向的數，數組變為
3 6 7 2 5 8 9
l繼續向後走，指向6大于mark停下，r指針向前走，指向2停下，交換 數組變為
3 2 7 6 5 8 9
此時l繼續向後走 指向了7大于mark 停下，r繼續往前走也指向7大于mark繼續向前走，指向2停下，但是現在r指針的索引已經小于了l指針的索引 無需交換并且結束循環 最終數組變為
3 2 7 6 5 8 9 r最終指向2 l最終指向7
是以可以得出上面的結論,
`此時r指針左邊的數(包括r指針指向的數)[3,2]都是小于等于mark(5)的，r指針右邊的數(不包括r指針指向的數)[7,6,5,8,9]都是大于等于mark(5)的 ` `l指針左邊的數(不包括l指針指向的數)[3,2]都是小于等于mark(5)的，l指針右邊的數(包括l指針指向的數)[7,6,5,8,9]都是大于等于mark的`
是以說我們可以按照
[left,r] [r+1,rigth]
或者是
[left,l-1] [l,rigth]
劃分兩個區間，這樣第一個區間的數都是小于等于mark的，第二個區間的數都是大于等于mark的
2.3代碼
模闆
public void quickSort(int[] nums, int left, int right) {
//終止條件 當區間隻有一個數時無需排序
if (left >= right) return;
//找mark值，并聲明兩個指針 l和r取邊界的前(後)一位 這裡為了友善下面在指針移動時停下交換數字後還得移動指針，我們使用的是do-while循環，即上來先做一次移動，代碼看起來簡潔一點
int mark = nums[left], l = left - 1, r = right + 1;
//當兩個指針相遇或者r指針走到l前面時結束
while (l < r) {
//do-while比while的好處就是，這裡如果兩個指針同時停下時并且l<r交換完畢，我們還得再次的移動一次指針，否則會一直的死循環，do-while的話即使是倆指針交換完數依然會走，不用多加指針移動的代碼
do l++; while (nums[l] < mark); //大于等于mark時停下
do r--; while (nums[r] > mark); //小于等于mark時停下
//l<r交換
if (l < r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
}
//遞歸處理左區間
quickSort(nums, left, r);
//遞歸處理右區間
quickSort(nums, r + 1, right);
//這裡的區間也可以寫 (left,l-1) (l,rigth) 上面分析過
}
注意：
上面的代碼，如果我們選
nums[left]
為mark值時，我們在遞歸處理時不能使用以
l
表示的左右區間，如果我們選
nums[right]
為mark值時，在遞歸處理時不能使用以
r
表示的左右區間 否則會出現死循環問題
例：
現在有一個數組 元素為
[1,2]
如果我們選的mark是
nums[left]即1
我們遞歸時用的是以l表示的兩個區間 就會出現死循環的問題
此時l指針指向1等于mark，停下，r指針指向2大于mark向前走，此時l和r相遇，結束循環，此時l的索引為0 r的索引為0
- 此時以l指針表示的兩個區間是 [0,-1] [0,1] 我們發現，我們一開始的區間就是[0,1]這裡又回到了[0,1]程式就陷入了死循環
- 此時r指針表示的兩個區間就是 [0,0] [1,1]就不會發生死循環
2.3算法分析
-
平均時間複雜度
O(nlogn) （區間長度基本一緻）
O(n^n)每次找的mark都是最大(最小)
- 是一個
不穩定
- 需要額外的空間
O(nlogn)
2.4應用
快速選擇_第k個數
3.簡單選擇排序 (周遊交換)
(周遊交換)
3.1圖示
從小到大排序
跟冒泡排序的思路差不多，也是每一次循環确定一個
最小(最大值)
，不同的是，選擇排序不需要像冒泡排序那樣每一趟都兩兩的比較并交換元素，選擇排序是每一趟使用一個變量在周遊的時候确定最小值的索引位置，然後周遊完成之後将這個元素與前面的元素進行交換，保證每一趟都确定一個元素
如下圖所示，每一趟都确定一個最小的元素放到前面，下一次周遊的時候從已确定位置元素的下一個進行周遊
循環次數分析
外層循環
n個元素，需要确定n-1個元素的位置，是以外層循環需要
n-1
次
内層循環
因為我們每一趟都将最小元素放到最前面，是以下一次周遊的時候先将未确定位置元素記錄下來，然後從這個元素的下一個位置開始周遊，最後将這個未确定位置元素給确定下來
3.2代碼分析
public void selectSort(int[] nums) {
//控制趟數 需要n-1趟
for (int i = 0; i < nums.length-1; i++) {
//minIndex指向的是未确定位置元素的首個
int minIndex = i;
//從i+1開始周遊 一直到最後 找到比minIndex索引位置元素還小的 更新minIndex
for (int j = i + 1; j < nums.length ; j++) {
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
//這裡判斷最小元素的位置是否就是起始位置，如果是的話就無需交換，不是的話交換
if (minIndex != i) {
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
}
3.3算法分析
- 冒泡排序的時間複雜度是
O(n^n)
平均時間複雜度是
O(n^n)
，最壞的時間複雜度也是
O(n^n)
，
- 空間複雜度是
O(1)
- 速度比冒泡排序快，因為冒泡排序交換元素的次數比較多，而選擇排序交換元素的次數叫冒泡排序少
-
不穩定的排序
4.堆排序
5.插入排序 (插入有序數組)
(插入有序數組)
3.1圖示
就是将第一個元素看成有序表，然後将後面的元素按照大小插入到有序表中
3.2代碼
3.2.1初始版
将一個元素比如A插入到他前面的一個有序的數組中，無非就三種情況
- 要麼A比第一個數都小，那麼先将這個有序數組中的所有值後移，然後将A插到第一個位置
- A在數組的兩個值之間
(比如...<B<=A<C<....)
- A比這個有序數組的最大元素都大，那麼A就不需要移動
public void insertSort(int[] nums) {
//外層循環控制插入元素的次數 一共n個元素 需要插入n-1次
for (int i = 1; i < nums.length; i++) {
//這個for循環是這個待插入元素前面的有序數組看成是一個區間 讓待插入元素在這個區間中判斷然後找位置
for (int j = 0; j <= i - 1; j++) {
//待插入元素比最後一個元素大 啥也不用幹
if (nums[i] > nums[i - 1]) {
} else
//在待插入數組之間 先講這個待插入元素存起來 然後将比待插入元素大的數全 部後移 最後将這個數插入
if (nums[i] >= nums[j] && nums[i] < nums[j + 1]) {
int t = nums[i];
for (int k = i; k > j + 1; k--) {
nums[k] = nums[k - 1];
}
nums[j + 1] = t;
//待插入元素比有序數組第一個元素都小 将有序數組全部後移 将待插入元素插入
} else if (nums[i] < nums[0]) {
int t = nums[i];
for (int k = i; k > 0; k--) {
nums[k] = nums[k - 1];
}
nums[0] = t;
}
}
}
}
3.2.2普通版
上面的代碼雖然可以實作插入排序，但是嵌套了三層for循環，且後兩個判斷基本做的都是相同的事，都是先将數組後移，然後插入資料，是以我們可以使用一個while循環，将這三種情況三合一
(這種做法跟圖示相同，都是判斷着并移動着元素)
public void insertSort(int[] nums) {
//元素從索引為1開始到最後都得插入
for (int i = 1; i < nums.length; i++) {
//待插入元素 用一個變量存起來
int insertValue = nums[i];
//使用一個指針 指向有序數組的末尾 最後記錄的是待插入元素的前一個位置
int index = i - 1;
/*
1、當待插入元素大于末尾元素時，進不來
2、當待插入元素小于末尾元素且index>0時 将元素後移 并且index後移 直到某一個元素小于待插入元素時結束循環 這時待插入元素剛好在一個正确的區間内 這時index指向的是待插入位置的前一位
3、當循環到index=-1時結束，說明待插入元素比第一個元素還小，
*/
//當index=-1 或者找到一個元素比待插入元素小結束循環
while (index > 0 && insertValue < nums[index]) {
//将待插入元素大的數後移
nums[index + 1] = nums[index];
//指針後移 繼續指向
index--;
}
//index+1就是待插入位置
nums[index + 1] = insertValue;
}
}
3.3算法分析
- 選擇排序的時間複雜度是
O(n^n)
平均時間複雜度是
O(n^n)
，最壞的時間複雜度也是
O(n^n)
，
- 空間複雜度是
O(1)
-
穩定的排序
6.希爾排序 (優化插入排序)
(優化插入排序)
6.1優化插入排序
插入排序的核心就是将一個元素A插入到一段有序的數組中，我們A與前面的數組中的最後一個元素(最大元素)開始比較，然後依次将元素後移，最終找到A的待插入位置，
我們可以發現，當後面的元素都的位置大部分都在有序數組中間時，我們會花費大量的時間在移動數組和比較中，是以我們在插入排序的基礎上優化一下，
(圖示見6.2)
優化的思路就是我們每次按照下标對元素進行分組，對于每組進行插入排序，這樣在最後進行整體插入排序時，大部分的小元素都在數組的前半部分，大的元素都在後半部分，這樣的好處就是元素移動的次數明顯減少。
6.2圖示
現在有7個數字 0 1 2 3 4 5 6
6 7 4 3 8 9 2
一、
我們将7/2 = 3 即第一次索引每+3分一組
下标為 0 3 6 的一組 即 6 3 2
下标為 1 4 的一組 即 7 8
下标為 2 5 的一組 即 4 9
對每一組的數進行插入排序後變為
0 1 2 3 4 5 6
2 7 4 3 8 9 6
二、我們将3/2 =1 這一次索引每+1分一組 即所有元素一組 我們整體進行插入排序
0 1 2 3 4 5 6
2 3 4 5 6 8 9
6.3代碼
public void shellSort(int[] nums) {
int len = nums.length;
while (len >= 1) {
//記錄一下每一次的元素的下一個元素的索引增量
int p = len / 2;
for (int i = 0; i < nums.length; i++) {
//找到有序數組的最後一個位置
int index = i - p;
//存一下待插入元素
int insertValue = nums[i];
//循環判斷 找到待插入元素的位置
while (index >= 0 && insertValue < nums[index]) {
//待插入元素小于有序數組的最後一個元素時 移動有序數組的元素
nums[index + p] = nums[index];
//index指針繼續向前走 找到有序數組的前一個元素在進行比較
index -= p;
}
//最後index會指向待插入索引位置的前一個 是以+p才是待插入元素的位置
nums[index + p] = insertValue;
}
//每次len都必須/2
len /= 2;
}
}
6.4算法分析
- 選擇排序的平均時間複雜度是
O(nlogn)
O(n^s) 1<s<2
- 空間複雜度是
O(1)
-
不穩定的排序
7.歸并排序 (遞歸合并)*
(遞歸合并)*
7.1思路
歸并排序的核心思想是将兩個有序的數列合并成一個大的有序的序列。通過遞歸，層層合并，即為歸并
分治
歸并的總體示意圖
是外部排序，需要借助額外的空間
- 1.從中間劃分兩個區間
- 2.分别遞歸兩個區間
- 3.合并
遞歸區間示意圖
每次劃分n*2個區間，當區間中隻有一個數時，終止遞歸，然後向上合并，這裡最開始合并的就是80和30，因為80和30區間隻有一個數，然後合并60和20，然後時30 80 與20 60進行合并，然後右半部分也是同理，最後異一步合并第二層的兩個數組，最終變成一個有序數組
核心的部分就是合并，其實就是給你兩個有序的數組，将這兩個數組合并，要求合并之後還是有序的，
這裡使用雙指針算法，分别從兩個數組的頭部開始走，判斷哪個數小，小的數放到新數組中并且指針後移繼續比較，最後那個指針走到頭了，就将另外一個數組的後部分都接上
歸并排序部落格
7.2代碼
public void merge_sort(int[] arr, int l, int r) {
// 遞歸結束條件 區間隻有一個數無序劃分區間直接傳回
if (l >= r) return;
// 邏輯部分 找中心點，然後分别向左右兩邊遞歸
int mid = l + ((r - l) >> 1);
//左區間是[l,mid]
merge_sort(arr, l, mid);
//右區間是[mid+1,r];
merge_sort(arr, mid + 1, r);
//雙指針算法合并兩個有序數組
int[] tmp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j])
tmp[k++] = arr[i++];
else
tmp[k++] = arr[j++];
}
//那個指針沒走完将後面的數全部接上
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
// 給原數組指派
for (i = l, j = 0; i <= r; i++, j++)
arr[i] = tmp[j];
}
7.3算法分析
時間複雜度是
O(nlogn)
假設有n個數，一共要分logn層，每層都是O(n)，是以是nlogn
需要額外的空間
7.4應用
逆序對的數量