一、冒泡排序

空间复杂度：O(1)

时间复杂度：最好O(n)，最坏和平均为O(n^2)

稳定性：稳定

适用性：顺序表、链表

//冒泡排序
void BubbleSort(int A[],int n){
    for(i=0;i<n-1;i++){
        flag=false;            //本趟是否发生了交换
        for(j=n-1;j>i;j--){
            if(A[j]<A[j-1]){
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(flag==false)       //说明没发生交换，已经有序
            return;
    }
}

二、快速排序

空间复杂度：最好和平均为O(logn)，最坏O(n)

时间复杂度：最好O(nlogn)，最坏为O(n^2)，平均接近O(nlogn)

稳定性：不稳定

适用性：顺序表

//快速排序
int Partition(int A[],int low,int high){
    int pivot=A[low];
    while(low<high){
        while(A[high]>=pivot&&low<high) high--;
        A[low]=A[high];
        while(A[low]<=pivot&&low<high]) low++;
        A[high]=A[low];
    }
    A[low]=pivot;              //最终基准（枢轴）放在low所指的位置，此时low==high
    return low;
}

void QuickSort(int A[],int low,int high){
    if(low<high){
        int pivotpos=Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}