冒泡排序

基础算法

#include <stdio.h>
int main(void)
{
    int T = 0;
    printf("请输入排序总数量\n");
    scanf("%d",&a[i]);
    int a[T];
    int i= 0, j = 0, t= 0;
    for (; i < T; i++)
    {
        printf("请输入%d/%d位数字\n", i+1, sizeof(a) / sizeof(int));
        scanf("%d",&a[i]);
    }
    for (i = 0; i < T-1; i++)
    {
        for (j = 0; j < T - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
    for (i = 0; i < T; i++)
    {
        printf("%d ", a[i]);
    }
}

改进

标记上一循环 位置给予POS标记 既然每次排序已经有了最大数 那么下次排序时 和已经确定的最大数字比较是无效计算 可从此进行优化
例 给定arr数组:

    int i = strlen(arr)-1;
    while(i > 0) {
    //i=最大
        int pos = 0;
        for(int j = 0 ; j < i;j++){
            if(arr[j] > arr[j+1]){
                pos = j;  //标记
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        i = pos;
    }
}

改进

正反同时进行冒泡排序 不断确定最大值和最小值 通过给定最大最小标记来减少无效运算

#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
    int T = 0;
    cin >> T;
    int arr[T];
    int i = 0;
    while (cin >> arr[i])
    {
        if (cin.get() == '\n') break;
        i++;
    }
    cout<<"Success:"<<endl;
    for(int j=0;j<T;j++)
    {
        cout<<arr[j]<<" ";
    }
    cout<<endl;
    int small_ = 0;
    int max_ = T-1;
    int sum_num = 0;
    while (small_ < max_) {
        for (int j = small_; j < max_; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
            sum_num++;
        }
        max_--;
        for (int k = max_; k > small_; k--) {
            if (arr[k] < arr[k - 1]) {
                int tmp = arr[k];
                arr[k] = arr[k - 1];
                arr[k - 1] = tmp;
            }
            sum_num++;
        }
        small_++;
    }
    cout<<"共排序次数:"<<sum_num<<endl<<"排序结果:";
    for(int v =0;v<T;v++)
    {
        cout<<arr[v]<<" ";
     } 
}