정렬 알고리즘 (빠 른 정렬, 쌓 기 정렬)

5. 빠 른 정렬
먼저 하나의 수 (정렬 할 데이터 의 첫 번 째 데이터) 를 비교 기준 으로 선택 한 다음 에 뒤에서 기준 보다 작은 것 을 찾 아 앞쪽 의 빈자리 위치 에 두 었 다. 이 어 예전 에 기준 보다 큰 데 이 터 를 뒤쪽 의 빈자리 위치 에 두 었 다. i 와 j 가 만 날 때 까지 기준 을 i 위치 에 두 었 다. 기준 앞의 데 이 터 는 모두 기준 보다 작고 기준 후의 데 이 터 는 모두 기준 보다 크다.그리고 왼쪽 과 오른쪽 을 재 귀적 으로 처리 합 니 다.

//    
typedef struct stack
{
	int* data;
	int top;
}stack;
int quickonce(int *arr, int left, int right) //O(n)
{
	int i = left;
	int j = right;
	int tmp = arr[i];//   
	while (i tmp)
		{
			j--;
		}
		if (i== j)
		{
			break;
		}
		arr[i] = arr[j];
		//               
		while (i < j && arr[i] < tmp)
		{
			i++;
		}
		if (i == j)
		{
			break;
		}
		arr[j] = arr[i];
	}

	arr[i] = tmp;

	return i;
}

void Quick(int *arr, int left, int right) // O(nlogn) O(logn)     
{
	
	int i = left;
	int j = right;
	int pos = quickonce(arr, i, j);

	if (i< pos-1)
	{
		Quick(arr, i, pos - 1);
	}
	if (j>pos+1)
	{
		Quick(arr, pos + 1, j);
	}
}
//           ：             
void QuickSort1(int *arr, int len)
{
	Quick(arr, 0, len - 1);
}

//            ，         ，    ，    
void QuickSort2(int *arr, int len)
{
	stack st;
	int left = 0;
	int right = len - 1;
	int i = left;
	int j = right;
	int top = 0;
	int n = (int)(log10(double(len - 1)) / log10(double(2))) + 1;
	st.data = (int *)malloc(2 * sizeof(int)* n);
	st.top = 0;

	st.data[top++] = i;
	st.data[top++] = j;

	while (top != 0)
	{
		j = st.data[--top];
		i = st.data[--top];

		int pos = quickonce(arr, i, j);
		//         
		if (i < pos-1)
		{
			st.data[top++] = i;
			st.data[top++] = pos - 1;
		}
		//      
		if (j > pos+1)
		{
			st.data[top++] = pos + 1;
			st.data[top++] = j;
		}
	}

	free(st.data);
	
}

여섯, 더미 정렬
큰 뿌리 더미: 한 그루 의 나무 중에서 어떤 나무 든 지 그 아버지의 노드 는 좌우 아이 보다 크다.
생각:
1. 마지막 나무 에서 위로 올 려 야 한다.
2. 조정 할 때마다 하위 트 리 의 뿌리 부분 부터 아래로 조정

//        （       ，                
//   ：i     ：2i+1     ：2i+2        i，     （i-1）/2

//    
//1.               
//2.                    
void AdjustHeap(int *arr, int len, int start)// O(logn) 
{
	int tmp = arr[start];//      ，             
	int i = start * 2 + 1;//   
	while (i arr[i])//        &&   >   
		{
			i += 1;
		}//       ， i            

		if (arr[i] > tmp)
		{
			arr[start] = arr[i];
			start = i;//     
			i = 2 * start + 1;//   
		}
		else
		{
			break;
		}
	}
	arr[start] = tmp;
}
//   
void CreateHeap(int *arr, int len) //O(n)
{
	for (int i = (len-2)/2; i >= 0; i--)//len-1                      
	{
		AdjustHeap(arr, len , i);
	}
}
void swap(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void HeapSort(int *arr, int len) // O(nlogn), O(1),    
{
	CreateHeap(arr, len); // O(nlogn)    
	int end = len - 1;//         

	//while (end > 0)
	//{
	//	swap(&arr[0], &arr[end]);
	//	AdjustHeap(arr, end, 0);
	//	end--;
	//}
	for (int i = 0; i < len; ++i) // O(nlogn)
	{
		swap(&arr[0], &arr[len - 1 - i]);
		AdjustHeap(arr, len-1-i,0);
	}
}