[C/C++ 演算法]- 選擇、插入、氣泡排序

[C/C++ 演算法]- 選擇、插入、氣泡排序

[C/C++ 演算法]- 選擇、插入、氣泡排序

剛才找資料時發現一個C/C++的教學網站,趕快發揮(C/P)的長才將它備份來,有需要的同好,歡迎來(C/P)一下^^。

拷貝來源:
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/SelectionInsertionBubble.htm

#include <stdio.h>
#include <stdlib.h>
#define LEN 8
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

void selectionSort(int*, int, int(*)(int, int));
void insertionSort(int*, int, int(*)(int, int));
void bubbleSort(int*, int, int(*)(int, int));
void print(int*, int len);
int ascending(int, int);
int descending(int, int);
int main(void) {
int number[LEN] = {10, 9, 1, 2, 5, 3, 8, 7};
selectionSort(number, LEN, ascending);
print(number, LEN);
insertionSort(number, LEN, descending);
print(number, LEN);
bubbleSort(number, LEN, ascending);
print(number, LEN);
return 0;
}
int selectedIdx(int* arr, int from, int to, int(*compar)(int, int)) {
int selected = from;
int i;
for(i = from + 1; i < to; i++) if(compar(arr[i], arr[selected]) < 0) {
selected = i;
}
return selected;
}
void selectionSort(int* arr, int len, int(*compar)(int, int)) {
int i;
for(i = 0; i < len; i++) {
int selected = selectedIdx(arr, i, len, compar);
if(selected != i) { SWAP(arr[i], arr[selected]) }
}
}
int insertedIdx(int* arr, int eleIdx, int(*compar)(int, int)) {
int i;
for(i = 0; i < eleIdx; i++) if(compar(arr[i], arr[eleIdx]) > 0) {
break;
}
return i;
}
void insert(int* arr, int eleIdx, int inserted) {
int ele = arr[eleIdx];
int i;
for(i = eleIdx; i > inserted; i--) { arr[i] = arr[i - 1]; }
arr[inserted] = ele;
}
void insertionSort(int* arr, int len, int(*compar)(int, int)) {
int i;
for(i = 0; i < len; i++) {
int inserted = insertedIdx(arr, i, compar);
if(inserted != i) { insert(arr, i, inserted); }
}
}
void bubbleTo(int* arr, int to, int(*compar)(int, int)) {
int i;
for(i = 0; i < to - 1; i++) if(compar(arr[i + 1], arr[i]) < 0) {
SWAP(arr[i + 1], arr[i]);
}
}
void bubbleSort(int* arr, int len, int(*compar)(int, int)) {
int i;
for(i = 0; i < len; i++) { bubbleTo(arr, len - i, compar); }
}
void print(int* arr, int len) {
int i;
for(i = 0; i < len; i++) { printf("%d ", arr[i]); }
printf("\n");
}
int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }

 

One thought on “[C/C++ 演算法]- 選擇、插入、氣泡排序

  1. 排序法的性能評估指標:

    穩定:如果a原本在b前面,而a=b,排序之後a仍然在b的前面。

    不穩定:如果a原本在b的前面,而a=b,排序之後a可能會出現在b的後面。

    時間複雜度:對排序數據的總的操作次數。反映當n變化時,操作次數呈現什麼規律。

    空間複雜度:是指算法在計算機內執行時所需存儲空間的度量,它也是數據規模n的函數。

    PS. 個人認為目前最為推薦 [ 效率(速度)&額外記憶體使用量&穩定度 ] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort)

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *