时间复杂度和简单排序算法

认识时间复杂度

时间复杂度为一个算法流程中，常数操作数量的一个指标。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常熟操作，进而总结出常数操作数量的表达式。

在表达式中只要高阶项，剩下的部分如果为f(N)，那么时间复杂度为O(f(N))

简单排序算法

引用自[十大经典排序算法]

冒泡排序

从第一个数开始比较相邻的元素，如果第一个比第二个大，就交换它们两个，重复直到排序完成。

代码引用自[冒泡排序)

java代码

public class BubbleSort implements IArraySort{
    
    @Override
    public int[] sort(int[] sourceArray) throws Exception{
        //对arr进行拷贝，不改变参数内容
        int[] arr=Array.copyOf(sourceArray,sourceArray.length);
        
        for(int i=1;i<arr.length;i++){
            //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag=true;
            
            for(int j=0;j<arr.length-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    
                    flag=false;
                }
            }
            
            if(flag){
                break;
            }
        }
        return arr;
    }
}

C语言代码

#include<stdio.h>
void bubble_sort(int arr[],int len){
    int i,j,temp;
    for(i=0;i<len-1;i++)
        for(j=0;j<len-1-i;j++)
            if(arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
}
int main(){
    int arr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};
    int len=(int) sizeof(arr)/sizeof(*arr);
    bubble_sort(arr,len);
    int i;
    for(i=0;i<len;i++)
        printf("%d ",arr[i]);
    return 0;
}

C++代码

#include<iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用，若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[],int len){
    int i,j;
    for(i=0;i<len-1;i++)
        for(j=0;j<len-1-i;j++)
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
}
int main(){
    int arr[]={61,17,29,22,34,60,72,21,50,1,62};
    int len=(int) sizeof(arr)/sizeof(*arr);
    bubble_sort(arr,len);
    for(int i=0;i<len;i++){
        cout<<arr[i]<<' ';
        cout<<endl;
        float arrf[]=17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len=(float) sizeof(arrf)/sizeof(*arrf);
        bubble_sort(arrf,len);
        for(int i=0;i<len;i++)
            cout<<arrf[i]<<' '<<endl;
        return 0;
    }
}