表排序

0x00 什么是表排序

​ 当每个元素本身大小很大（比如是一个庞大的结构体，移动起来很慢），不移动元素本身而之移动指针的排序方式称为间接排序，表排序就是简介排序的一种。

​ 表排序的思路是： 1 定义一个指针数组作为‘’表“table 初始时table[i]=i

​

​

​ 2 用排序算法对元素序列的key（用来比较的属性）进行排序，但是不交换元素

而是交换对应的table[i]的值

​

当排序完成后，我们的表就更新完成了，我们就可以访问表的值来得到元素的顺序关系

0x01 对表排序进行对应的物理排序

​ 如果我们不仅仅只想输出对应的元素顺序关系，而是真的要在物理上改变元素的存放顺序，那该怎么办呢？

​

​ 什么是环呢？ 我们table[0]=3 table[3]=1 table[1]=5 table[5]=0，这样 针对序列中的任一环 如果table[i]!=i,就说明环没结束，需要交换

​ 那我们 ElementType tmp =data[0] thispos=0 nextpos1=table[thispos]

​ data[thispos]=data[nextpos] ;table[thispos]=thispos;thispos=nextpos ;nextpos1=table[thispos];//对于顺序已经正确的table我们让table[i]=i

​ data[thispos]=data[nextpos] ;table[thispos]=thispos;thispos=nextpos ;nextpos1=table[thispos];；

​ 不断的这样重复下去直到data[5]=temp, 所以 我们循环的条件是 nextpos!=this&&table[nextpos]!=nextpos 然后再执行data[pos]=temp

​ 这样我们就可以处理一个环

​ 对于所有的环 我们想遍历 只需遍历该序列，如果thispos 和nextpos不等，就进入上面的循环，所以整体伪代码描述如下

void real_sort(ElementType data[],int N){
    int i;
    int table[]=table_sort(data,N);//先用table_sort得到table表
    for(i=0;i<N;i++){
        int thispos=i;
        int nextpos=table[thispos];
        if(thispos!=nextpos){
            ElementType tmp=data[i];
            while(table[nextpos]!=nextpos){
                data[thispos]=data[nextpos];
                table[thispos]=thispos;
                thispos=nextpos;
                nextpos1=table[thispos];；
            }
            data[thispos]=tmp;//出来的时候就说明data[thispos]该等于tmp了而不是继续data[nextpos]
        }
    }
}