前提：
void X_Sort(ElementType A[], int N) 从小到大排序
N是正整数 只讨论基于比较的排序（> = < 有定义） 只讨论内部排序
稳定性：任意两个相等的数据，排序前后的位置不发生改变
没有一种排序是任何情况下都表现最好的
选择排序：
无论什么情况都需要N*(N-1)/2次比较，不稳定
时间复杂度：T = O(N^2)
冒泡排序：
对于链表的排序也适用
最好情况：顺序 T = O(N)
最坏情况：逆序 T = O(N^2)
稳定
插入排序：
稳定
最好情况：顺序 T = O(N)
最坏情况：逆序 T = O(N^2)
时间复杂度下界：
对于下标 i < j, 如果A[i] > A[j], 则称(i, j)是一对逆序对(inversion)
交换2个相邻元素正好消去1个逆序对（冒泡， 插入）
插入排序：T(N, i) = O(N+I) 如果序列基本有序，则插入排序简单且高效
定理：任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对
定理：任何仅以交换相邻元素来排序的算法的算法，平均时间复杂度为Ω（N^2)
要提高效率，每次交换不止消去1个逆序对，每次交换相隔较远的2个元素
代码：
#includeusing namespace std;typedef long long ElementType;void Swap(ElementType *a, ElementType *b){ ElementType temp; temp = *a; *a = *b; *b = temp;}void Bubble_sort(ElementType A[], int N){ int P, flag, i; for (P=N-1; P >= 0; P--) { flag = 0; for (i = 0; i < P; i++) { if (A[i] > A[i+1]) { Swap(&A[i], &A[i+1]); flag = 1; } } if (flag == 0) break; }}void Insertion_Sort(ElementType A[], int N){ int P, i; ElementType Tmp; for (P = 1; P < N; P++) { Tmp = A[P]; for (i = P; i > 0 && A[i-1] > Tmp; i--) A[i] = A[i-1]; A[i] = Tmp; }}void SimpleSelectionSort(ElementType A[], int N){ int i, j, temp, Min; for (i = 0; i < N-1; i++) { Min = i; for (j = i+1; j < N; j++) if (A[j] < A[Min]) Min = j; if (Min != i) //第i个元素与最小元素交换 Swap(&A[Min], &A[i]); }}int main(){ int N; ElementType A[110000]; cin >> N; for (int i = 0; i < N; i++) cin >> A[i]; //Bubble_sort(A, N); //Insertion_Sort(A, N); SimpleSelectionSort(A, N); for (int i = 0; i < N-1; i++) cout << A[i] << " "; cout << A[N-1]; return 0;}
PTA运行结果：
- 数据1：只有1个元素；
- 数据2：11个不相同的整数，测试基本正确性；
- 数据3：103个随机整数；
- 数据4：104个随机整数；
- 数据5：105个随机整数；
- 数据6：105个顺序整数；
- 数据7：105个逆序整数；
- 数据8：105个基本有序的整数；
- 数据9：105个随机正整数，每个数字不超过1000。
选择排序：
冒泡排序：
插入排序：
