排序算法（一）（C语言实现）

排序算法（一）（C语言实现） 常用排序算法 一、冒泡排序 1.1 基本思想

相邻两两比较，较大的下沉，较小的上升
第一轮之后，最小的数就被放到第一个位置

1.2 优化

如果在进行到某趟排序时，已经排好了，则没有必要进行下一次排序。故可以使用flag标志来判断。

1.3 代码展示

#include 
#include 
#include 

void bubbleSort(int a[], int length) {
	int len = length;
	int temp;//中间变量 
	bool flag;//优化的标志 ,是否有交换 
	for (int i = 0; i < len; i++) {//外层循环控制比较趟数，比较了N-1趟
		flag = false;
		for (int j = len - 1; j > i;j--) {//内层循环控制第i+1趟比较了N-1-i次
			if (a[j] < a[j - 1]) {
				temp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = temp;
				flag = true;
			}
		}
		if (!flag) break;
	}
	printf("冒泡排序的结果：n");
	for (int i = 0; i < len; i++) {
		printf("%d ", a[i]);
	}
	printf("nn");

}
int main()
{
    //arr为要排序的数组 
	int arr[] = { 5, 9, 4, 1, 7, 8, 2, 6,10 };
	printf("原始数组为：n");
	int lengthArr = 9;
	for (int i = 0; i < lengthArr;i++) {
		printf("%d ", arr[i]);
	}
	printf("nn");
	bubbleSort(arr, lengthArr);//函数调用
    return 0;
}

1.4 运行结果

1.5 时间复杂度

排序完需要（N-1）趟（N为数组长度），而每趟需要比较N-1-i趟(i为数组下标)，即第一趟需要8次，第二次需要7次，依此类推：

（n-1）+（n-2）+....+2+1==-

根据复杂度的规则，去掉低阶项（也就是n/2），并去掉常数系数，那复杂度就是O（n^2）了

二：选择排序 2.1 基本思想

一开始从原始序列中找到最小的元素，放到序列的起始位置作为已
排序序列；然后，在从剩下的未排列的元素中继续寻找最小元素，放到已
排序的序列末尾....直到所有元素排列完毕

2.2 代码展示

#include 
#include 
#include 

void selectSort(int a[], int length) {
	int len = length;
	int minIndex;//假定的最小元素
	int temp;//中间变量
	for (int i = 0;i < len;i++) {
		//i是已排列的序列的末尾
		minIndex = i;
		for (int j = i + 1;j < len;j++) {
			//在剩下的无序区间中选择最小的元素，将最小元素，与无序区间的第一个元素比较
			if (a[j]

2.3 运行结果

2.4 时间复杂度

 （n-1）+（n-2）+....+2+1==-

故时间复杂度为O(n^2)。