博客

#include<iostream>
#include<string>
using namespace std;
void insert_sort(int R[],int size)
{
//第一次排序
  将T数组排序
    int*  T;
    T = new int [size];
	for (int i = 0;i < size-1;i++)
	{
		T[i] = i + 1;
	}
	T[size - 1] = 0;
	int t = T[T[0]];
	T[T[0]] = 0;
	while (t)
	{
		int h = 0;
		int k = T[t];
		while (T[h] && (R[t] > R[T[h]]))
		{
			h = T[h];
		}
		T[t] = T[h];
		T[h] = t;
		t = k;
	}
//这里其实和插入排序一样都是将后面的比较插入
	
	for (int i = 0;i < size;i++)
	{
		cout << T[i] << " ";
	}
	cout << endl;
//第二次排序
 将R数组重排
		int i = 1;
		int j = T[0];
		while (i < size-1)
		{
			if (i == j) { i++;j = T[j]; }
			if (i < j)
			{
				int  P = T[j];
				int temp = R[j];
				R[j] = R[i];
				R[i] = temp;
				T[j] = T[i];
				T[i] = j;
				i++;
				j = P;
			}
			if (i > j)
			{
				while (i > j)
					j = T[j];
			}


		}//这里是将R数组重排
}  
int main()
{
	int R[11] = {-1,12,45,76,23,23,34,65,76,3,55};
	insert_sort(R,11);

	for (int i = 1;i < 11;i++)
	{
		cout << R[i] << " ";
	}


}