一.排序

1.1.排序的概念及其運用

1.1.1排序的概念

排序： 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩定性： 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
內部排序： 數據元素全部放在內存中的排序。
外部排序： 數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

1.1.2排序運用

1.1.3 常見的排序算法

二.插入排序

2.1.直接插入排序

2.1.1.算法講解

直接插入排序是一種簡單的插入排序法，其基本思想是：
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
實際中我們玩撲克牌時，就用了插入排序的思想

當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移

直接插入排序的特性總結：

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

2.1.2.代碼實現

2.1.2.1.函數定義

Sort.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>//打印
void PrintArray(int* a, int n);
//插入排序
void InsertSort(int* a, int n);

2.1.2.2.算法接口實現

Sort.c

#include"Sort.h"//打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
//直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

2.1.2.3.測試代碼實現

test.c

#include"Sort.h"void TestInsertSort()
{int a[] = { 2,4,5,7,8,0,9,6,3,1 };printf("排序前：");PrintArray(a, sizeof(a) / sizeof(int));printf("\n");printf("直接插入排序：");InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;
}

2.1.2.4.測試展示

2.2.希爾排序

2.2.1.算法講解

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序。

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。
2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定:
   《數據結構(C語言版)》— 嚴蔚敏
   
   《數據結構-用面相對象方法與C++描述》— 殷人昆
   
   
4. 穩定性：不穩定

2.2.2.代碼實現

2.2.2.1.函數定義

Sort.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>//打印
void PrintArray(int* a, int n);
//希爾排序
void ShellSort(int* a, int n);

2.2.2.2.算法接口實現

Sort.c

#include"Sort.h"//打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
//希爾排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

2.2.2.3.測試代碼實現

test.c

#include"Sort.h"void TestShellSort()
{int a[] = { 2,4,5,7,8,0,9,6,3,1 };printf("排序前：");PrintArray(a, sizeof(a) / sizeof(int));printf("\n");printf("希爾排序：");ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestShellSort();return 0;
}

2.2.2.4.測試展示