排序上
為何插入比冒泡更受歡迎，兩者時(shí)間復(fù)雜度都是o(n^2)匙奴，
答:那得從評(píng)價(jià)算法標(biāo)準(zhǔn)說起叙赚，時(shí)間空間穩(wěn)定性time&space&stable
一怨咪，排序評(píng)價(jià)標(biāo)準(zhǔn)
1.排序算法執(zhí)行效率3個(gè)緯度
i乏矾，時(shí)間復(fù)雜度最好平均最壞
數(shù)據(jù)原始排序情況孟抗，有序無序
ii，時(shí)間復(fù)雜度系數(shù)常數(shù)低階
數(shù)據(jù)原始規(guī)模大小钻心，具體數(shù)據(jù)
iii凄硼，比較移動(dòng)和交換次數(shù)
基于比較算法，涉及兩個(gè)操作捷沸，一是比較摊沉，二是移動(dòng)或者交換
2.空間復(fù)雜度
原地排序，特指空間復(fù)雜度是o(1)的排序算法痒给，冒泡插入選擇都是原地排序算法
3.穩(wěn)定性
同值元素说墨，排序后前后順序不變骏全，稱為穩(wěn)定排序算法，特別注意這個(gè)特定在局部有同值婉刀，再次排序整體數(shù)據(jù)時(shí)同值間順序不變
比如:實(shí)際開發(fā)中，常排序的是一組對(duì)象序仙，不簡(jiǎn)單是一個(gè)數(shù)突颊，如給電商訂單排序，按金額排序潘悼，金額相同則按時(shí)間排序
解:解決辦法先全部排序金額律秃，再排局部相等按照時(shí)間排序
注:按照金額時(shí)間依次排序思路不難，實(shí)現(xiàn)復(fù)雜
解:先全部按照時(shí)間排序治唤，再通過穩(wěn)定排序算法按照金額排序
注:按照時(shí)間金額逆次排序思路不難棒动，實(shí)現(xiàn)簡(jiǎn)單
二，3種選擇排序
1.冒泡排序
一趟排序出一個(gè)泡宾添，只操作相鄰兩個(gè)數(shù)據(jù)船惨，看相鄰是否符合順序，不符合換序缕陕，其實(shí)可以優(yōu)化粱锐，在某趟冒泡操作一次都沒有交換的時(shí)候，說明已經(jīng)達(dá)到完全有序扛邑，利用一個(gè)flag可實(shí)現(xiàn)優(yōu)化
// 冒泡排序怜浅，a 表示數(shù)組，n 表示數(shù)組大小
public void bubbleSort(int[] a, int n) {
? if (n <= 1) return;
for (int i = 0; i < n; ++i) {
? ? // 提前退出冒泡循環(huán)的標(biāo)志位
? ? boolean flag = false;
? ? for (int j = 0; j < n - i - 1; ++j) {
? ? ? if (a[j] > a[j+1]) { // 交換
? ? ? ? int tmp = a[j];
? ? ? ? a[j] = a[j+1];
? ? ? ? a[j+1] = tmp;
? ? ? ? flag = true;? // 表示有數(shù)據(jù)交換? ? ?
? ? ? }
? ? }
? ? if (!flag) break;? // 沒有數(shù)據(jù)交換蔬崩，提前退出
? }
}
2.冒泡性能評(píng)價(jià)
i.時(shí)間復(fù)雜度恶座，最好o(n)，最壞o(n^2)沥阳，平均o(n^2)
ii.原地排序算法
iii.穩(wěn)定排序算法
補(bǔ):平均時(shí)間復(fù)雜度就是加權(quán)平均期望時(shí)間復(fù)雜度跨琳，計(jì)算比較復(fù)雜，平時(shí)可用“有序度”“逆序度”代替計(jì)算桐罕，有序度是序列中全部有序的元素對(duì)湾宙，逆序度是序列中全部逆序的元素對(duì)
如:4，5冈绊，6侠鳄，3，2死宣，1
有序?qū)Γ?/5伟恶，4/6，5/6
滿序?qū)Γ?毅该，2博秫，3潦牛，4，5挡育，6為n*(n-1)/2=15
逆序?qū)Γ?5-3=12
冒泡排序過程就是將逆序?qū)ψ冇行驅(qū)Π屯耄杞粨Q12次
3.插入排序
將序列分為有序區(qū)間和無序區(qū)間(遍歷區(qū)間i=1，j=)即寒，將無序序列中元素一一插入到有序排列中合適的位置
// 插入排序橡淆，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ù)整體往后移動(dòng)一個(gè)
? ? ? } else {
? ? ? ? break;
? ? ? }
? ? }
? ? a[j+1] = value; // 插入數(shù)據(jù)母赵，j可以為-1
? }
}
注:為何逆序遍歷區(qū)間找到位置逸爵，是因?yàn)檎业轿恢镁托枰w移動(dòng)后面的區(qū)間，所以直接逆序遍歷時(shí)邊找位置凹嘲，邊往后移動(dòng)
4.插入性能評(píng)價(jià)
i.最好o(n)师倔，最壞o(n^2)，平均o(n^2)
ii.原地排序算法
iii.穩(wěn)定排序算法
5.選擇排序
類似插入排序周蹭，分成有序區(qū)間趋艘，無序區(qū)間但每次都是從無序區(qū)間選擇最小值放到有序區(qū)間末尾
6.選擇性能評(píng)價(jià)
i.最好最壞平均o(n^2)
ii.原地排序算法
iii.不穩(wěn)定排序算法
7.開篇問題解答
冒泡排序中數(shù)據(jù)的交換操作：
if (a[j] > a[j+1]) { // 交換
? int tmp = a[j];
? a[j] = a[j+1];
? a[j+1] = tmp;
? flag = true;
}
插入排序中數(shù)據(jù)的移動(dòng)操作：
if (a[j] > value) {
? a[j+1] = a[j];? // 數(shù)據(jù)移動(dòng)
} else {
? break;
}
注:冒泡插入頻次最高最深的的操作，冒泡有3個(gè)操作一起凶朗，插入僅1個(gè)操作致稀，為了把性能做到極致，選插入俱尼，插入還可以繼續(xù)優(yōu)化成希爾排序抖单，平時(shí)工作中三個(gè)算法就插入用的最多
