冒泡排序

1. 從第一個數據開始到第n-1個數據，依次和后面一個數據兩兩比較，數值小的在前。最終，最后一個數據（第n個數據）為最大值。
2. 從第一個數據開始到第n-2個數據，依次和后面一個數據兩兩比較，數值小的在前。最終，倒數第二個數據（第n-1個數據）為第二個最大值。
3. 從第一個數據開始到第n-3個數據，依次和后面一個數據兩兩比較，數值小的在前。最終，倒數第三個數據（第n-2個數據）為第三個最大值。
4. 最多重復操作n-1次。

時間復雜度：最好情況 O(n)，最壞情況 O()，平均情況 O()

• 若已是排好的，從開頭到最后，兩兩比對，需要n-1次比對，無需交換，一輪結束，則時間約n，即 O(n)。
• 若是亂序，則需最多n-1次重復操作，雖然每次重復操作的比對次數減1，但總時間約，即O()。

空間復雜度：O(1)

• 在原位置排序，只重復使用了用于交換的臨時空間，不隨數據量的變動而變動，空間使用為常量(1)。

---

C語言實現：（bubblesort.c）

#include <stdio.h>/* function prototype */
void bubble(int *, int);	// bubble sort
void traverse(int *, int);	// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);bubble(arr, n);	printf("[ after bubble sort ] ");traverse(arr, n);return 0;
}/* subfunction */
void bubble(int *array, int length)		// bubble sort
{for(int i = length - 1; i > 0; i--){int ischange = 0;for(int j = 0; j < i; j++){if(array[j] > array[j+1]){int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;ischange = 1;}}if(ischange == 0) return ;}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

編譯鏈接： gcc -o bubblesort bubblesort.c

執行可執行文件： ./bubblesort

---

---

選擇排序

1. 從第一個數據開始到最后，挑選最小值，放入第一個位置。
2. 從第二個數據開始到最后，挑選最小值，放入第二個位置。
3. 從第三個數據開始到最后，挑選最小值，放入第三個位置。
4. 共重復操作n-1次。

時間復雜度：最好情況 O()，最壞情況 O()，平均情況 O()

• 從開頭到最后，挑選最小值，需要n-1次比對。重復n-1次操作，雖然每次重復操作的比對次數減1，但總時間約，即O()。

空間復雜度：O(1)

• 在原位置排序，只重復使用了用于交換的臨時空間，不隨數據量的變動而變動，空間使用為常量(1)。

---

C語言實現：（selectsort.c）

#include <stdio.h>/* function prototype */
void select(int *, int); 	// select sort
void traverse(int *, int);	// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);select(arr, n);printf("[ after select sort ] ");traverse(arr, n);return 0;
}/* subfunction */
int findmin(int *array, int m, int n)		// find the minimum data, return index
{int minindex = m, mindata = array[m];int j;for(j = m + 1; j < n; j++){if(mindata > array[j]){minindex = j;mindata = array[j];}}return minindex;
}void select(int *array, int length)	 	// select sort
{for(int i = 0; i < length - 1; i++){int min = findmin(array, i, length);if(i != min){int tmp = array[i];array[i] = array[min];array[min] = tmp;}}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

編譯鏈接： gcc -o selectsort selectsort.c

執行可執行文件： ./selectsort

---

---

插入排序

1. 第二個數據和第一個數據，兩兩比較，數值小的在前。
2. 從第三個數據開始到第一個數據，依次和前面一個數據兩兩比較，數值小的在前。
3. 從第四個數據開始到第一個數據，依次和前面一個數據兩兩比較，數值小的在前。
4. 最多重復操作n-1次。

時間復雜度：最好情況 O(n)，最壞情況 O()，平均情況 O()

• 若已是排好的，無需交換，從第二個數據到最后，依次只需和前面一個數據兩兩比對，需要n-1次比對，則時間約n，即 O(n)。
• 若是亂序，則除了和前面數據兩兩比對（需n-1次比對），還需重復往前比對，最多比對n-1次，總時間約，即O()。

空間復雜度：O(1)

• 在原位置排序，只重復使用了用于交換的臨時空間，不隨數據量的變動而變動，空間使用為常量(1)。

---

C語言實現：（insertsort.c）

#include <stdio.h>/* function prototype */
void insertsort(int *, int);		// insert sort
void traverse(int *, int);		// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);insertsort(arr, n);printf("[ after insert sort ] ");traverse(arr, n);return 0;
}/* subfunction */
void insertsort(int *array, int length)	// insert sort
{int ischange = 0;for(int i = 1; i < length; i++){for(int j = i; j >= 0; j--){if(array[j-1] > array[j]){int tmp = array[j];array[j] = array[j-1];array[j-1] = tmp;ischange = 1;}if(ischange == 0) return ;}}
}void traverse(int *array, int length)		// show element one by one
{printf("element(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

編譯鏈接： gcc -o?insertsort insertsort.c

執行可執行文件： ./insertsort