一、冒泡排序
    基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换
    算法：
    void bubble_sort(SqList &L){ //冒泡排序算法
    int m,i,j; RedType x; //交换时临时存储
    for(m=1;m<=n-1;m++){ //总共需m趟
    for(j=1;jif(L.r[j].key>L.r[j+1].key){ //发生逆序
    x=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=x; //交换
    }
    }
    }
    优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素
    提高效率：一旦某一趟比较时不出现记录交换，说明已排好序，就可以结束算法
    改进的冒泡排序算法：
    void bubble_sort(SqList &L){ //改进的冒泡排序算法
    int m,i,j; flag=1;RedType x; //flag作为是否有交换的标记
    for(m=1;m<=n-1 && flag==1;m++){
    flag=0；
    for(j=1;jif(L.r[j].key>L.r[j+1].key){ //发生逆序
    flag=1; //发生交换，flag置为1，若本趟没发生交换，flag保持为0
    x=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=x; //交换
    }
    }
    }
    时间复杂度
    ①最好情况（正序）
    比较次数：n-1
    移动次数：0
    ②最坏情况（逆序）
    比较次数：n(n-1)/2
    移动次数：3n(n-1)/2

    二、快速排序
    基本思想：任取一个元素为中心（pivot），所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表，对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个
    通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序：
    ①每一趟的子表的形成是采用从两头向中间交替式逼近法
    ②由于每趟中对各子表的操作都相似，可采用递归算法
    算法：
    void main(){
    QSort(L,1,L.length);}
    void QSort(SqList &L, int low, int high){ //对顺序表L快速排序
    if(lowpivotloc=Partition(L,low,high);
    //将L.r[low..high]一分为二，pivotloc为枢轴元素排好序的位置
    QSort(L,low,pivotloc-1); //对低子表递归排序
    QSort(L,pivotloc+1,high); //对高子表递归排序
    }
    }
    int Partition(SqList &L,int low, int high){
    L.r[0]=L.r[low]; pivotkey=L.r[low].key;
    while(lowwhile(low= pivotkey) —high;
    L.r[low]=L.r[high];
    while(low= pivotkey) ++low;
    L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0];
    return low;
    }
    时间复杂度：平均计算时间是O(nlog2n)
    空间复杂度：快速排序不是原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度，在平均情况下需要O(logn)的栈空间，最坏情况下，栈空间可达O(n)
    快速排序不适于对原本有序或基本有序的记录序列进行排序
    快速排序算法分析：
    ①划分元素的选取是影响时间性能的关键
    ②输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法
    ③改变划分元素的选取方法，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能