一.前提

二.冒泡排序

三.插入排序

#include<iostream>
using namespace std;
typedef int ElemengType;
void Bubble_Sort(ElemengType A[], int N) {for (int p = N - 1; p >= 0; p--) {int flag = 0;for (int 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(ElemengType A[], int N) {ElemengType Tmp;int i;for (int 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;}
}
int main()
{ElemengType A[10] = { 1,2,0,9,3,5,4,7,6,9 };Bubble_Sort(A, 10);for (int i = 0; i < 10; i++)cout << A[i] << " ";cout << endl;Insertion_Sort(A, 10);for (int i = 0; i < 10; i++)cout << A[i] << " ";cout << endl;return 0;
}

四.时间复杂度下界

I原始序列里的逆序列的对数

最好的复杂度欧米伽N^2下界