[数据结构与算法]选择排序，冒泡排序及改进

? ? ? ?本人是个编程小白，刚接触编程不久，学习了选择排序，冒泡排序这两个简单的排序方法，为了能更好的去啃那几个高级排序，以及方便以后研究更高深的算法，所以决定自己写一下，巩固基础，把地基打牢。

一，选择排序法

1，算法思想

（1），在未排序的序列中找到最大（小）的数，放到起始位置构成有序序列

（2），接着遍历剩下的序列，找到最大（小）的数，放在有序序列末尾

（3），不断遍历，直到排序完成

2，算法分析

（1），平均时间复杂度：O(n2)

（2），空间复杂度：O(1) ??? //空间复杂度就是在交换元素时那个临时变量所占的内存空间；

（3），稳定性：不稳定?

3，代码实现

#include<stdio.h>
#include<stdlib.h>   //随机函数头文件
#include<time.h>   //设置时间 ，随机数种子头文件 
void xuanze(int v[], int s)
{
	int i, j, p, q, t;
	for (i = 0; i < s; i++) {
		p = i; q = v[i];
		for (j = i + 1; j < s; j++) {
			if (q <v[j]) {
				p = j; q = v[j];
			}
		}
		if (p != i) {
			t= v[i]; v[i] = v[p]; v[p] = t;
		}	
	}
}
int main() {
	srand((unsigned int)time(NULL));  //随机数种子 
	int i, j, p, q, s; int a[10];
	for (i = 0; i < 10; i++)  a[i]=rand()%101;
	xuanze(a, 10);
	for (i = 0; i < 10; i++)  printf("%d ", a[i]);
}

二，冒泡排序法

1，算法思想

（1），比较开头相邻的两个数，如果第一个数大于第二个数，就交换他们两个

（2），往后遍历，对每一对相邻的元素执行同样的操作，直到最后一对数。此时放在最后的元素是最大的数，将该数固定

（3），然后对未固定的元素重复以上操作，直到整个序列排序完成

2，算法分析

（1），平均时间复杂度：O(n2)

（2），最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；

?????????? 最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；

?????????? 平均的空间复杂度为：O(1)；

（3），稳定性：稳定?

3，代码实现

#include<stdio.h>
#include<stdlib.h>   //随机函数头文件
#include<time.h>   //设置时间 ，随机数种子头文件 
void maopao(int v[], int s)
{
	int p, j, t;
	for (p = 0; p < s-1 ; p++) {//从上到下遍历两个数大的就交换，每一轮会把最大的数
		//沉到最下面，比较的次数每一轮会比前一轮少
		for(j=0;j<s-p-1;j++)
			if (v[j] < v[j + 1]) {
				t = v[j];
				v[j] = v[j + 1];
				v[j + 1] = t;
			}
	}
}
int main() {
	srand((unsigned int)time(NULL));  //随机数种子 
	int i, j, p, q, s; int a[10];
	for (i = 0; i < 10; i++)  a[i]=rand()%101;
	maopao(a, 10);
	for (i = 0; i < 10; i++)  printf("%d ", a[i]);
}

其实冒泡排序还可以做一些简单的改进，省去一些重复的操作，如果不需要交换就直接退出循环

代码实现

void maopao(int v[], int s)
{
	int p, j, t, f = 1;
	for (p = 0; p < s-1 && f == 1; p++) {
		f = 0;
		for(j=0;j<s-p-1;j++)
			if (v[j] < v[j + 1]) {
				t = v[j];
				v[j] = v[j + 1];
				v[j + 1] = t;
				f = 1;
			}
	}
}

这次先写到这里吧，等开学到学校我再研究研究更高级的算法。