冒泡排序C实现

常规版本冒泡排序

#include <stdio.h>

void swap(int* a,int* b){
	int temp=*a;
  	*a=*b;
  	*b=temp;
}

void bubbleSort(int* arr,int len){
	for(int i=0;i<len-1;i++){//下文并没有用到arr[i]可知i仅仅是控制执行次数的
    	for(int j=0;j<len-1-i;j++){
        	if(arr[j]>arr[j+1]){
            	swap(&arr[j],&arr[j+1]);
            }
        }
    }
}

int main() {
	int arr[5] = {1,5,4,3,2};
	int len = sizeof(arr) / sizeof(*arr);

	//quickSort(arr,0,4);
	bubbleSort(arr, len);

	for (int i = 0; i < len;i++) {
		printf("%d",arr[i]);
	}

	return 0;
}

1. 对于arr[j]==arr[j+1]的情况不进行交换，使之成为稳定排序。
2. 冒泡排序是从后往前逐渐排出的，已经被排序的序列就是最终样子。
3. 时间复杂度是O(n2)，因为有两层遍历，外层i仅起到计数作用，内层j可以视为指针从左往右遍历未排序序列。

改进的冒泡排序

void bubbleSort2(int arr[], int len) 
{
	bool flag=true;//必须要初始化置1
  
    for(int i=0 ; i<len-1 && flag ; i++)//在进行len-1轮排序的过程中，如果flag为0也退出
	{
        flag=false;//每一轮冒泡之前都将标志修改为0
		for(int j=0;j<len-1-i;j++)//第1轮都对arr[0]到arr[len2](倒数第2个)进行遍历
		{
			if(arr[j]>arr[j+1])//波及到最后一个
			{
				swap(&arr[j],&arr[j+1]);
                flag=true;//如果到这一轮已经升序，一个交换操作都没有，就不会进入这里，那么flag就保持0后面就结束了。
			}
		}
	}
}