삽입 배열의 귀속과 비귀속 실현

1207 단어
삽입 배열의 비귀속은 매우 간단하여 두 층의 순환으로 해결할 수 있기 때문에 시간 복잡도는 O(n^2)이고 공간 복잡도는 O(1)이다.
코드는 다음과 같습니다.
void InsertSort(int* pArr, int len)
{
	if (len<2)
		return;
	int key, j;	
	
	for (int i = 1; i < len; ++i )
	{
		key = pArr[i];	// 
		for (j = i-1; j >= 0; --j)
		{
			if ( key >= pArr[j] )
				break;
			else
				pArr[j+1] = pArr[j];
		}
		pArr[j+1] = key;
	}
}

 
플러그인 귀속이 실현되고 자신의 n-1번을 호출할 수 있으며 찾은 후 n-1개 원소의 정확한 위치를 삽입할 수 있으며 시간 복잡도도 O(n^2)이고 공간 복잡도는 O(n)이다.
코드는 다음과 같습니다.
// pArr index , len
void InsertSortRecursion(int* pArr, int index, int len)
{	
	if (len<2)	// 
		return;
	int key = pArr[index];	// 
	int i = index-1;		// 

	if ( index < len )
	{
		for (; i>=0; i--)
		{
			if ( key >= pArr[i] )
				break;
			else	// 
				pArr[i+1] = pArr[i];
		}
		
		pArr[i+1] = key;	// key 
		InsertSortRecursion(pArr, index+1, len);
	}
}

 
개인적인 관점:
귀속 쓰기 플러그인을 사용하지 않는 것은 필기시험에서 귀속 쓰기를 요구하기 때문이다.

좋은 웹페이지 즐겨찾기