lianbiao.cpp

来自「软件算法处理」· C++ 代码 · 共 80 行

/*template <class T>
class ChainNode {
friend Chain<T>;
	private:
	T data;
	ChainNode<T> *link;
} ;*/

template <class T>

void TableInsertSort(T a[], int N)

{

    int* link = new int[N]; 

    int head = 0, pre, cur, i; 

    link[0] = -1;

    for (i = 1; i < N; i++)

    {

                  if (a[head] > a[i]) 

                  { 

                      link[i] = head; 

                      head = i;

                  }//杤?昞?丆場崯廀梫崯敾抐丆幐??崯師敾抐杤?擖KCN

                  else 

                  {

                      for (cur = head; cur != -1 && a[cur] <= a[i]; cur = link[cur]) 

                          pre = cur;

                      link[pre] = i; link[i] = cur;

                  }

    }

    cur = head;//廳攔彉楍

    for (i = 0; i < N; i++)

    {

        while (cur < i) 

            cur = link[cur];

        pre = link[cur];

        if (cur != i)

        {

            swap(a[i], a[cur]);

            link[cur] = link[i]; 

            link[i] = cur;

        }

        cur = pre;

    }

    delete []link;

}