交换类排序-----冒泡排序

た入场券 2022-05-03 01:56 222阅读 0赞

冒泡排序：

//冒泡排序
    # include<stdio.h>//时间复杂度 O(n^2) 稳定 
    void BubbleSort(int a[], int n){
    	for(int i = 1; i <= n; i++) //每一趟结束都把一个最大的数放到最下面 
    	    for(int j = 1; j <= n-i; j++)
    	     if(a[j] > a[j+1]){
    		   int t = a[j];
    		   a[j] = a[j+1];
    		   a[j+1] = t;
    		} 
    } 
    
    
    int main(){
    	int n;
    	printf("请输入你要排序的数的个数:"); 
    	scanf("%d", &n);
    	int *a = new int[n];//申请一个整型变量空间,没有赋初值，并定义一个整型指针a指向该地址空间 
    	for(int i = 1; i <= n; i++)
    	scanf("%d", &a[i]);
    	BubbleSort(a, n);
    	printf("排序后:"); 
    	for(int j = 1; j <= n; j++)
    	printf("%6d", a[j]);
    	delete []a;//回收数组a的空间 
    	return 0;
    }

冒泡排序改进1：

//冒泡排序--改进1添加标志位，如果某一次排序中出现没有交换位置，说明排序完成 
    # include<stdio.h>
    void BubbleSort(int a[], int n){
    	int flag = 0;    //初始化表示没有交换 
    	for(int i = 1; i <= n; i++){    //每一趟结束都把一个最大的数放到最下面
    	flag = 0;
    	for(int j = 1; j <= n-i; j++)
    	     if(a[j] > a[j+1]){
    		   int t = a[j];
    		   a[j] = a[j+1];
    		   a[j+1] = t;
    		   flag = 1; //表示已经交换过了 
    		} 
    		if(flag == 0) break;//一趟冒泡完成以后，若flag=0,则已经有序 ，跳出循环 
    	}	    
    } 
    
    
    int main(){
    	int n;
    	printf("请输入你要排序的数的个数:"); 
    	scanf("%d", &n);
    	int *a = new int[n];//申请一个整型变量空间,没有赋初值，并定义一个整型指针a指向该地址空间 
    	for(int i = 1; i <= n; i++)
    	scanf("%d", &a[i]);
    	BubbleSort(a, n);
    	printf("排序后:"); 
    	for(int j = 1; j <= n; j++)
    	printf("%6d", a[j]);
    	delete []a;//回收数组a的空间 
    	return 0;
    }

冒泡排序改进2：

/*冒泡排序--改进2，添加标志位，记录最后一次交换位置的地方，证明最后一次
    交换位置后的地方是排好序的，下一次只需要排最后一次之前的地方就好*/ 
    # include<stdio.h>
    void BubbleSort(int a[], int n){
    	int flag = n-1; //刚开始，最后交换位置的地方设置为数组的最后一位  
        while(flag > 1){   //flag在逐渐减小，到最后肯定会变为1 
            int pos = 1; //每一轮的最开始，标志位置在数组1 
        	for(int i = 1; i <= flag; i++)//第一趟要比n-1次
    	     if(a[i] > a[i+1]){
    		   int t = a[i];
    		   a[i] = a[i+1];
    		   a[i+1] = t;
    		   pos = i;   //pos记录最后一次交换位置的地方，pos往后的数都是有序的
    		} 
    		flag = pos;//因为冒泡排序是每次把最大的数沉到最底部，当下一趟排序遇到之前标记的位置pos时就可以不用再冒泡了
        }
    }
    
    
    int main(){
    	int n;
    	printf("请输入你要排序的数的个数:"); 
    	scanf("%d", &n);
    	int *a = new int[n];//申请一个整型变量空间,没有赋初值，并定义一个整型指针a指向该地址空间 
    	for(int i = 1; i <= n; i++)
    	scanf("%d", &a[i]);
    	BubbleSort(a, n);
    	printf("排序后:"); 
    	for(int j = 1; j <= n; j++)
    	printf("%6d", a[j]);
    	delete []a;//回收数组a的空间 
    	return 0;
    }