版权声明：本文为博主原创文章，未经博主同意不得转载。

https://blog.csdn.net/u012515223/article/details/24323125

表插入排序 具体解释 及 代码(C++)

本文地址: http://blog.csdn.net/caroline_wendy/article/details/24323125

表插入排序(List Insertion Sort)是使用静态链表进行插入排序, 每次插入改动指针项, 通过指针项的链接顺序,
使静态链表有序.

改动2n次指针, 取代移动2n次数据, 由于每次改动2个指针值(代码中可见), 但比較次数仍为O(n^2);

重排记录: 3(n-1)次记录移动, 记录须要交换,一次交换式三次移动数据. 

所以时间复杂度为O(n^2).

实例代码为C++, 使用2个数组, 清晰的显示了值域和指针域.

代码:

/*

 * test.cpp

 *

 *  Created on: 2014.04.22

 *      Author: Spike

 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>

#include <climits>

#include <deque>

using namespace std;

//打印排序的序列

void printSeq(const std::deque<int>& vals, std::deque<int>& ptrs) {

	int t = 0;

	for (std::size_t i=0; i<vals.size(); ++i) {

		t = ptrs[t];

		std::cout << vals[t] << " ";

		if (ptrs[t] == 0) {

			break;

		}

	}

	std::cout << std::endl;

}

//打印数组

void print(const std::deque<int>& L) {

	for (auto i : L) {

		std::cout << i << " ";

	}

	std::cout << std::endl;

}

//表插入排序

void ListInsertSort(const std::deque<int>& vals, std::deque<int>& ptrs) {

	const int length(vals.size());

	ptrs.resize(length);

	ptrs[0] = 1;

	ptrs[1] = 0;

	for (int i=2; i<length; ++i) {

		int t = 0; //从0開始查找

		int pre = 0; //记录前一个指针

		for (int j=0; j<i-1; ++j) {

			t = ptrs[t]; //找到指针的位置

			if (vals[t] > vals[i]) { //小于插到后面

				ptrs[i] = t;

				ptrs[pre] = i;

				break; //终止

			} else if (ptrs[t] == 0) { //末尾, 直接插入前面

				ptrs[i] = 0;

				ptrs[t] = i;

			}

			pre = t; //记录指针

		}

		//測试

		std::cout << "Pointer: "; print(ptrs);

	}

}

//重排记录

void Arrange(std::deque<int>& vals, std::deque<int>& ptrs) {

	const int length(vals.size());

	int t = 0;

	int pre = 0;

	t = ptrs[t];

	for (int i=1; i<length; ++i) {

		while( t<=i && t!=0) { //顺次找到结点

			t = ptrs[t];

		}

		if(t == 0)

			break;

		pre = ptrs[t];

		if (t != i) { //交换值, 交换指针

			int temp = vals[t];

			vals[t] = vals[i];

			vals[i] = temp;

			int temp2 = ptrs[i];

			ptrs[i] = t;

			ptrs[t] = temp2;

		}

		t = pre;

		std::cout << "Pointer: "; print(ptrs);

	}

}

int main(void) {

	std::deque<int> vals = {INT_MAX, 49, 38, 65, 97, 76, 13, 27, 49};

	std::deque<int> ptrs;

	print(vals);

	ListInsertSort(vals, ptrs);

	printSeq(vals, ptrs);

	Arrange(vals, ptrs);

	print(vals);

	return 0;

}

输出:

2147483647 49 38 65 97 76 13 27 49

Pointer: 2 0 1 0 0 0 0 0 0

Pointer: 2 3 1 0 0 0 0 0 0

Pointer: 2 3 1 4 0 0 0 0 0

Pointer: 2 3 1 5 0 4 0 0 0

Pointer: 6 3 1 5 0 4 2 0 0

Pointer: 6 3 1 5 0 4 7 2 0

Pointer: 6 8 1 5 0 4 7 2 3

13 27 38 49 49 65 76 97

Pointer: 6 6 1 5 0 4 8 2 3

Pointer: 6 6 7 5 0 4 8 1 3

Pointer: 6 6 7 7 0 4 8 5 3

Pointer: 6 6 7 7 6 4 0 5 3

Pointer: 6 6 7 7 6 8 0 5 4

Pointer: 6 6 7 7 6 8 7 0 4

Pointer: 6 6 7 7 6 8 7 8 0

2147483647 13 27 38 49 49 65 76 97