数据结构-顺序表的交换排序

顺序表的初始化

const int M = 505;
 
typedef struct{
    int key;            //关键元素
    int others;         //其他元素
}info;
 
typedef struct{
    info r[M+1];        
    int length();       //表长
}SeqList,*PSeqList;

冒泡排序

分析：

顺序表的冒泡排序和数组的冒泡排序的原理相同。通过不停比较相邻两个数据，如果不满足排序要求就交换两个值，直到所有的记录都排好序。

void Bubble_Sort(PSeqList PL)
{
    for(int i = 1;i <= PL->length;i++)
        for(int j = 2;j <= 1 + S->length-i;j++)
            if(PL->r[j].key < PL->r[j-1].key)
            {
                int temp = PL->r[j];
                PL->r[j] = PL->r[i];
                PL->r[i] = temp;
            }
}

复杂度：

空间复杂度

只使用了一个辅助单元temp，所以空间复杂度是 $O(1)$

时间复杂度

通过冒泡排序的算法可知每次交换，循环都需要比较 $(n-1)$ 次，最多交换 $(n-i)$ 次，最少交换 $0$ 次。平均交换 $(n-i)/2$ 次。

总的比较次数为 $\sum_{i =1}^{n-1}(n-i)=n(n-1)/2$ 。时间复杂度为 $O(n^{2})$ 。

总的交换次数为 $\sum_{i-1}^{n-1}(n-i)/2=n(n-1)/4$ 。时间复杂度为 $O(n^{2})$ 。

因此冒泡排序的总时间复杂度为 $O(n^{2})$ 。

快速排序

分析：

快速排序是对冒泡排序的一种改进，它的基本思想是铜鼓哦一趟排序将待排序的数据分割成独立的两个部分，其中一部分比另一部分要小。然后分别对这两部分继续分割，直至整个序列有序。

使用的方法是双指针法，快速排序并不稳定。

具体操作：

（1）在序列 $S$ 中任意选择一个记录 $r$ 作为轴 $k$

（2）将剩余的部分分割成两个子序列 $L$ 和 $R$ ，子序列 $L$ 中的数据均小于或等于 $k$ 。子序列 $R$ 中的数据均大于或者等于 $k$ 。

（3）将子序列 $L$ 中所有记录放在记录 $r$ 左边，子序列 $R$ 中所有记录放在记录 $r$ 右边。

（4）对 $L$ 和 $R$ 递归直至子序列中只含有0或者1个元素。

int Quick_Elem(PSeqList PL,int l,int h)
{
    int piv;
    int p = PL->r[l];                        //取子表的第一个记录为轴记录
    piv = PL->r[l].key;                      //取轴记录关键字
    while(l < h)
    {
        while(l < h && PL->r[h].key >= piv)
            h--;
        PL->r[l] = PL->r[h];                 //更新范围
        while(l < h && PL->r[l].key <= piv)
            l++;                
        PL->r[h] = PL->r[l];                 //更新范围
    }
    PL->r[l] = p;                            //轴记录
    return l;
}

void Quick_Sort(PSeqList PL,int l,int h)
{
    int piv;
    if(l < h)
    {
        piv = Quick_Elem(PL,l,h);            //分割序列
        Quick_Sort(PL,l,piv - 1);            //对L递归
        Quick_Sort(PL,piv + 1,h);            //对R递归
    }
}