各种排序方式的汇总及学习（只更了冒泡排序）

首先了解排序：

排序的定义

假设含有n个记录的序列为{r1,r2,…,rn}，其相应的关键字分别是{k1,k2,…,kn}，需要确定1,2,…,n的一种排列p1,p2,…,pn，使其相应的关键字满足kp1<=kp2<=…<=kpn 非递减（或非递增）的关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,…,rpn}，这样的操作就称为排序[1]。

简单来说，排序就是使输入的序列变成符合一定规则（关键字）的有序序列（非递减或非递增）。大多数遇到的排序问题都是按数据元素值的大小规则进行排序的问题。所以本文为了方便起见，只讨论数据元素值大小比较的排序问题。

排序的稳定性

假设ki=kj（1<=i<=n，1<=j<=n，i!=j），且在排序前的序列中ri领先于rj（即i<j）。

• 如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；
• 反之，若可能使得排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。

简单来概括稳定和不稳定[2]：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b前面；
• 不稳定：如果a原本在b前面，而a=b，排序之后a可能在b的后面。

时间和空间复杂度

• 时间复杂度：对排序数据的总的操作次数。反应当n变化时，操作次数呈现什么规律

• 空间复杂度：算法在计算机内执行时所需要的存储空间的容量，它也是数据规模n的函数。
  

1. 冒泡排序（Bubble Sort）：

1.1 一般的冒泡排序：

基本思想

比较相邻的两个元素，将值大的元素交换到右边（降序则相反）

步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3. 针对所有的元素重复以上的步骤，除了最后一个；

4. 重复步骤1~3，直到排序完成。

   #include<stdio.h>
   int main(){
   	int n,i,j;
   	scanf("%d",&n);
   	int a[n]; 
   	//input
   	for(i=0;i<n;i++){
   		scanf("%d",&a[i]);
   	}
   	//bubble sort 
   	for(i=0;i<n-1;i++){//从第一个到倒数第二个
   		for(j=0;j<n-1;j++){//从第一个倒数第二个
   			if(a[j]>a[j+1]){
   				int t=a[j];
   				a[j]=a[j+1];
   				a[j+1]=t;
   			}
   		}
   	}
   	//output
   	for(i=0;i<n;i++){
   		printf("%d ",a[i]);
   	}
   	return 0;
   }

比如有n个元素，那么第一次比较迭代，需要比较n-1次（因为是相邻成对比较，最后一个元素没有与下一个相邻比较的对象，所以是n-1次），此次迭代完成后确定了最后一个元素为最大值；第二次比较迭代，需要比较n-2次，因为第一次迭代已经确定好了最后一个元素，所以不再需要比较；…；第 i次比较迭代，需要比较n-i次，此时确定后面i个元素是有序的较大元素；…；第n-1次比较迭代，需要比较n-(n-1)次，此时完成冒泡排序操作。

原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是 o(n^2) = (n-1)*(n-1)

代码使用双循环来进行排序。外部循环控制所有的回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。

1.2优化版冒泡排序：

优化结果：解决了在已经调整好顺序后继续循环的问题。

优化方向：如果我们能判断出数列已经有序（最后几个数字），并且做出标记（但仅仅标记了数列是有序的），剩下的几轮排序就可以不必执行，提早结束工作。

代码思路：代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

#include<stdio.h>
int main(){
	int n,i,j;
	scanf("%d",&n);
	int a[n]; 
	//input
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	//bubble sort 
	int issort=0;//此处有变动
	for(i=0;i<n-1;i++){
		for(j=0;j<n-1;j++){
			if(a[j]>a[j+1]){
				int t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
				issort=1; //此处有变动
			}
		}if(issort==0)break;//此处是最后一处变动了，，此处解决的是大循环的结束条件。
	}
	//output
	for(i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

1.3再次优化版冒泡排序：

这个问题的关键点在哪里呢？关键在于对数列有序区的界定。

按照现有一般的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1（为最后一个），第二轮排序过后的有序区长度是2 ….

实际上，数列真正的有序区可能会大于这个长度，比如如果后面5个元素实际都已经属于有序区。因此后面的许多次元素比较（这里是指在大循环）是没有意义的。

如何避免这种情况呢？我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

#include<stdio.h>
int main(){
	int n,i,j;
	scanf("%d",&n);
	int a[n]; 
	//input
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	//bubble sort 
	int issort=0;
	int tem=n-1;
	int border=n-1;
	for(i=0;i<n-1;i++){
		for(j=0;j<border;j++){ //此次更改的是小循环的结束条件。
			if(a[j]>a[j+1]){
				int t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
				issort=1; 
				tem=j;//此时tem记录的是小循环里的最后一次交换	
					//极有可能与大循环冲突。 	
			}
		}
		border=tem;
		if(issort==0)break;
	}
	//output
	for(i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

总结：此次优化是将大循环，小循环的结束条件进行修正。

本文来自一些微信公众号与csdn和自己的总结与修改（抱歉，我找不到文章链接了），在此表示感谢，如有侵权，联系立删。