先說結(jié)論：
- 插入排序和冒泡排序比較，就時(shí)間復(fù)雜度而言：最好土居、最壞以及平均時(shí)間復(fù)雜度一樣枣购，但是插入排序的數(shù)據(jù)移動(dòng)相對(duì)于冒泡排序的數(shù)據(jù)交換，賦值語句更少擦耀，所以優(yōu)先選擇插入排序棉圈；
- 選擇排序最壞的時(shí)間復(fù)雜度是O(n^2)，相對(duì)于插入排序或冒泡排序的O(n)已經(jīng)低人一等眷蜓；而且選擇排序是非穩(wěn)定排序分瘾，效果不理想；
三種算法代碼實(shí)現(xiàn)
插入排序算法代碼：(1-i模式)
//實(shí)現(xiàn)一
void insert_sort(int arr[], int size) {
int i, j, tmp;
for(i=1; i<size; i++) {
tmp = arr[i];
for(j=i; j>0 && arr[j-1]>tmp; j--) {
arr[j] = arr[j-1]; //數(shù)據(jù)移動(dòng)吁系，一行代碼
}
arr[j] = tmp; //找到j(luò)的位置德召，插入進(jìn)去
}
}
//實(shí)現(xiàn)二
void insert_sort(int arr[], int size) {
int i, j, tmp;
for(i=1; i<size; i++) {
tmp = arr[i];
for(j=i; j>0; j--) {
if(arr[j-1]>tmp) {
arr[j] = arr[j-1]; //數(shù)據(jù)移動(dòng)，一行代碼
} else {
break;
}
}
arr[j] = tmp; //找到j(luò)的位置汽纤，插入進(jìn)去
}
}
冒泡排序算法代碼：(0-0模式)
//實(shí)現(xiàn)一
void bubble_sort(int arr[], int size) {
int i, j, tmp;
for(i=0; i<size-1; i++) {
for(j=0; j<size-1-i; j++) { //數(shù)據(jù)交換三行代碼比較多上岗，耗時(shí)長
if(arr[j] > arr[j+1]) {
tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
//實(shí)現(xiàn)二：加flag 優(yōu)化
void bubble_sort(int arr[], int size) {
int i, j, tmp;
for(i=0; i<size-1; i++) {
int exchangeFlag = 0;
for(j=0; j<size-1-i; j++) {
if(arr[j] > arr[j+1]) { // 數(shù)據(jù)交換三行代碼比較多，耗時(shí)長
tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
exchangeFlag = 1; // 表示有數(shù)據(jù)交換
}
}
if (0 == exchangeFlag) break; // 沒有數(shù)據(jù)交換蕴坪，已經(jīng)排好序了肴掷，提前退出
}
}
選擇排序代碼：(0-i+1模式)
void select_sort(int arr[], int size) {
int i, j, min;
for(i=0; i<size-1; i++) {
min = arr[i];
for(j=i+1; j<size; j++) {
if(arr[j] < min) {
min = arr[j];
arr[j] = arr[i];
arr[i] = min;
}
}
}
}
其他補(bǔ)充
算法評(píng)價(jià)標(biāo)準(zhǔn)
- 排序算法的執(zhí)行效率
時(shí)間復(fù)雜度：最好情況、最壞情況背传、平均情況時(shí)間復(fù)雜度呆瞻；
時(shí)間復(fù)雜度的系數(shù)、常數(shù) 径玖、低階：實(shí)際情況小規(guī)模數(shù)據(jù)痴脾，不涉及到無窮大情況；
比較次數(shù)和交換（或移動(dòng)）次數(shù)梳星；
- 排序算法的內(nèi)存消耗
空間復(fù)雜度赞赖；
原地排序（Sorted in place）。原地排序算法丰泊，就是特指空間復(fù)雜度是 O(1) 的排序算法薯定； 是否是原地排序
- 排序算法的穩(wěn)定性
如果待排序的序列中存在值相等的元素，經(jīng)過排序之后瞳购，相等元素之間原有的先后順序不變。
