冒泡排序(交換排序）

基本思想

基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

特性總結

1. 冒泡排序是一種非常容易理解的排序
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：穩定

代碼實現

void bubbleSort(int* a, int n)//冒泡排序(時間復雜度為O(N^2),空間復雜度為O(1))
{for (int i = 0; i < n; i++){bool exchange = false;for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){int tmp = a[j];a[j] = a[j - 1];a[j - 1] = tmp;exchange = true;}}if (exchange == false)break;}
}

直接選擇排序

基本思想

每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完 。

• 在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數據元素
• 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
• 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

特性總結

1. 直接選擇排序思想非常好理解，但是效率不是很好。實際中很少使用
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：不穩定

代碼實現（優化，每次循環同時選擇最小和最大的數）

void Swap(int& a, int& b)
{int tmp = a;a = b;b = tmp;
}void printArr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void selectSort(int* a, int n)//選擇排序，時間復雜度為O(N^2),空間復雜度為O(1)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin, mini = begin;for (int i = begin; i <= end; i++){if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(a[begin], a[mini]);if (maxi == begin)//如果maxi和begin重疊，修正一下即可{maxi = mini;}Swap(a[end], a[maxi]);begin++;end--;}
}