插入排序

基本思想

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。

打撲克牌整理手牌用的就是插入排序的思想

代碼實現

void InsertSort(int* a, int n)
{
?? ?assert(a);
?? ?for (int i = 0; i < n - 1; i++)//將一個數組中所有元素升序
?? ?{ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//,這里必須是n-1,不然后面數組會越界
?? ??? ?int end=i;
?? ??? ?int x=a[end+1];//x始終指向end下一個位置的值
?? ??? ?while (end >= 0)//每趟插入最多挪動end-1個數據
?? ??? ?{
?? ??? ??? ?if (a[end] > x)//x前一個數大于x,就將數據往后移一格
?? ??? ??? ?{
?? ??? ??? ??? ?a[end + 1] = a[end];//這里數組的值會往后覆蓋
?? ??? ??? ??? ? ? ? ? ? ? ? ? ? ? ?//但是沒關系,我們已經將a[end+1]的值保存在x當中了
?? ??? ??? ??? ?end--;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?break;//跳出里面的while循環
?? ??? ??? ?}
?? ??? ?}
?? ??? ?a[end + 1] = x;
?? ?}
}
?

特性總結

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩定的排序算法
4. 穩定性：穩定

選擇排序

基本思想

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

就像小學生排隊一樣，讓最矮的那個站到第一排，然后讓第二矮的占到第二排，以此類推

代碼實現

void SelectSort(int* a, int n)
{
?? ?int begain = 0;
?? ?int end = n - 1;
?? ?while (begain < end)
?? ?{
?? ??? ?int maxi = begain;//初始化最值
?? ??? ?int mini = begain;
?? ??? ?for (int i = begain; i <= end; i++)
?? ??? ?{
?? ??? ??? ?if (a[i] < a[mini])
?? ??? ??? ?{
?? ??? ??? ??? ?mini = i;//記錄下標,否則會有數據被覆蓋的問題
?? ??? ??? ?}
?? ??? ??? ?if (a[i] > a[maxi])
?? ??? ??? ?{
?? ??? ??? ??? ?maxi = i;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?swap(&a[begain], &a[mini]);//將最大最小值交換
?? ??? ?swap(&a[end], &a[maxi]);
?? ??? ?begain++;//數組范圍往中間縮小
?? ??? ?end--;
?? ?}
}
?

代碼優化

上述思想是單向的，我們可以讓最高的和最矮的同時排序，就可以優化一下，實現雙向排序

void SelectSort(int* a, int n)
{
?? ?int begain = 0;
?? ?int end = n - 1;
?? ?while (begain < end)
?? ?{
?? ??? ?int maxi = begain;
?? ??? ?int mini = begain;
?? ??? ?for (int i = begain; i <=end; i++)
?? ??? ?{
?? ??? ??? ?if (a[i] < a[mini])
?? ??? ??? ?{
?? ??? ??? ??? ?mini = i;//記錄下標,否則會有數據被覆蓋的問題
?? ??? ??? ?}
?? ??? ??? ?if (a[i] > a[maxi])
?? ??? ??? ?{
?? ??? ??? ??? ?maxi = i;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?swap(&a[begain], &a[mini]);
?? ??? ?if (maxi == begain)//當最大值為begain時,交換最小值和開頭元素后,maxi指向的值不再是最大值了.
?? ??? ?{
?? ??? ??? ?maxi = mini;
?? ??? ?}
?? ??? ?swap(&a[end], &a[maxi]);
?? ??? ?begain++;
?? ??? ?end--;
?? ?}
}
?

特性總結

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