常见排序算法

冒泡排序的本质在于交换，每次通过交换的方式把当前剩余元素的最大值（最小值）移动到一端，当剩余元素减少为0时，排序结束。
举例：a=[3,4,1,5,2]，以移动最大值为例

第一趟：
①3与4比较，4大，保持不动，序列为{3，4，1，5，2}
②1和4比较，4大，交换位置，序列为{3，1，4，5，2}
③4和5比较，5大，保持不动，序列为{3，1，4，5，2}
④5与2比较，5大，交换位置，序列为{3，1，4，2，5}
第一趟排序结束，进行了四次比较。

第二趟：
①3与1比较，3大，交换位置，序列为{1，3，4，2，5}
②3与4比较，4大，保持不动，序列为{1，3，4，2，5}
③4与2比较，4大，交换位置，序列为{1，3，2，4，5}
第二趟排序结束，进行了三次比较。

第三趟：
①1与3比较，3大，保持不动，序列为{1，3，2，4，5}
②3与2比较，3大，交换位置，序列为{1，2，3，4，5}
第三趟排序结束，进行了两次比较。

第四趟：
①1与2比较，2大，保持不动，序列为{1，2，3，4，5}
第四趟排序结束，进行了一次比较。至此，冒泡排序结束，序列有序。

C++代码实现：

#include
using namespace std;
int main(){
	int a[10]={3,1,4,5,2};
	for(int i=1;i<=4;i++){
		for(int j=0;j<5-i;j++){
			if(a[j]>a[j+1]){
				int tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;
			}
		}
	}
	for(int i=0;i<5;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

整个排序过程平均情况下需要n*(n-1)/4次交换操作，时间复杂度为o(n^2)。

对于一个序列A中的n个元素，令 i 从1到n枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素与A[i]交换。

void select_sort(){
	for(int i=1;i<=n;i++){
		int k=i; 
		for(int j=i;j<=n;j++){
			if(A[j] 
两层for循环，时间复杂度为o(n^2)。
 
直接插入排序 
假设序列A有n个元素，初始将第一个元素置于有序序列中，令i从2到n枚举，需要进行n-1趟操作，每次将当前元素插入到有序序列中。
 
举例：序列A={5，2，4，6，3，1}
 第一趟：当前有序序列为{5}，把2插入有序序列中，生成新的有序序列{2，5}；
 第二趟：当前有序序列为{2，5}，把4插入有序序列中，生成新的有序序列{2，4，5}；
 第三趟：当前有序序列为{2，4，5}，把6插入有序序列中，生成新的有序序列{2，4，5，6}；
 第四趟：当前有序序列为{2，4，5，6}，把3插入有序序列中，生成新的有序序列{2，3，4，5，6}；
 第五趟：当前有序序列为{2，3，4，5，6}，把1插入有序序列中，生成新的有序序列{1，2，3，4，5，6}；
 
int A[maxn], n;  //下标从1开始
void insert_sort()
{
   for (int i = 2; i <= n; i++)//第二个元素开始
   {
      int tmp = A[i], j = i;  //tmp存放当前元素值，j为往前枚举的下标
      while (j > 1 && tmp < A[j - 1])
      {
         A[j] = A[j - 1];
         j--;
      }
      A[j] = tmp;
   }
}
 
时间复杂度为 O(n^2) ，但是在元素有序或近乎有序的情况下，时间复杂度可以降为 O(n) ，效率比 O(nlogn) 的算法还要高。 然而对于大规模的乱序数组，使用直接插入排序的效率是非常低的。