＜基礎算法＞十大排序算法總結

1. 冒泡排序

基本思想

冒泡排序的基本思想：從無序序列頭部開始，進行兩兩比較，根據大小交換位置，直到最後将最大（小）的資料元素交換到了無序隊列的隊尾，進而成為有序序列的一部分；下一次繼續這個過程，直到所有資料元素都排好序。

算法的核心在于每次通過兩兩比較交換位置，選出剩餘無序序列裡最大（小）的資料元素放到隊尾。

代碼

void bubble_sort(int arr[], int len) {
	int i, j;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}
           

算法改進

（1）設定标志位change

标志變量用于記錄每趟冒泡排序是否發生資料元素位置交換。如果沒有發生交換，說明序列已經有序了，不必繼續進行下去了。

void bubble_sort(int arr[], int len) 
{
	int i, j, change=1;   
	for (i = 0; i < len - 1 && change!=0; i++)
    {
        change=0;
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
             {
		     	 swap(arr[j], arr[j + 1]);
             	 change = 1;
             }
      }
}
           

（2）雞尾酒排序

雞尾酒排序又叫定向冒泡排序，攪拌排序、來回排序等，是冒泡排序的一種變形。此算法與冒泡排序的不同處在于排序時是以雙向在序列中進行排序。

雞尾酒排序在于排序過程是先從低到高，然後從高到低；而冒泡排序則僅從低到高去比較序列裡的每個元素。它可以得到比冒泡排序稍微好一點的效能，原因是冒泡排序隻從一個方向進行比對（由低到高），每次循環隻移動一個項目。

以序列(2,3,4,5,1)為例，雞尾酒排序隻需要從低到高，然後從高到低就可以完成排序，但如果使用冒泡排序則需要四次。

但是在亂數序列的狀态下，雞尾酒排序與冒泡排序的效率都很差勁。

void cocktail_sort(int arr[], int len) {
	int j, left = 0, right = len - 1;
	while (left < right) {
		for (j = left; j < right; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
		right--;
		for (j = right; j > left; j--)
			if (arr[j - 1] > arr[j])
				swap(arr[j - 1], arr[j]);
		left++;
	}
}
           

（1）時間複雜度

在設定标志變量之後：

當原始序列“正序”排列時，冒泡排序總的比較次數為n-1，移動次數為0，也就是說冒泡排序在最好情況下的時間複雜度為O(n)；

當原始序列“逆序”排序時，冒泡排序總的比較次數為n(n-1)/2，移動次數為3n(n-1)/2次，是以冒泡排序在最壞情況下的時間複雜度為O(n^2)；

當原始序列雜亂無序時，冒泡排序的平均時間複雜度為O(n^2)。

（2）空間複雜度

冒泡排序排序過程中需要一個臨時變量進行兩兩交換，所需要的額外空間為1，是以空間複雜度為O(1)

2. 快速排序

3. 選擇排序

4. 直接插入排序

5. 算法改進：二分插入排序

6. 希爾排序

7. 堆排序

8. 歸并排序

9. 桶排序/計數排序

10.基數排序