빠 른 정렬, 병합 정렬, 쌓 기 정렬 의 실현

최근 에 면접 에서 서열 을 정리 하 는 질문 을 자주 받 는데, 다음은 우리 가 한 번 가 보 겠 습 니 다.
1. 빠 른 정렬
엄 울 민 데이터 구조 교 재 를 참고 하여 다음은 본인 이 쓴 빠 른 정렬 실현 입 니 다.

#include<iostream>
using namespace std;
int Partition(int arr[], int low, int high)
{
	int pivotkey = arr[low];
	while (low<high)
	{
		while (low<high && arr[high] >= pivotkey) --high;
		arr[low] = arr[high];
		while (low<high && arr[low] <= pivotkey) ++low;
		arr[high] = arr[low];
	}
	arr[low] = pivotkey;
	return low;
}
void QiuckSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int pivotloc = Partition(arr, low, high);
		QiuckSort(arr, low, pivotloc - 1);
		QiuckSort(arr, pivotloc + 1, high);
	}
}
int main(int argc, char * argv[])
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	QiuckSort(a, 0, (sizeof(a) / sizeof(int)) - 1);
	for (int i = 0; i<sizeof(a) / sizeof(int); i++)
		cout << a[i] << " ";
	return 0;
}

2. 병합 정렬
       병합 정렬 은 병합 작업 에 있어 서 효과 적 인 정렬 알고리즘 입 니 다.이 알고리즘 은 분 치 법 (Divide and Conquer) 을 사용 한 매우 전형 적 인 응용 이다.
       우선 두 개의 질서 있 는 수열 을 어떻게 합병 할 것 인 가 를 고려 해 보 자.이것 은 매우 간단 합 니 다. 두 수열 의 첫 번 째 숫자 를 비교 하면 작은 사람 이 먼저 가 고 가 져 온 후에 해당 수열 에서 이 수 를 삭제 합 니 다.그리고 비교 해 보 세 요. 수열 이 비어 있 으 면 다른 수열 의 데 이 터 를 순서대로 꺼 내 면 됩 니 다.

//     a[] b[]   c[]   
void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
    int i, j, k;  
  
    i = j = k = 0;  
    while (i < n && j < m)  
    {  
        if (a[i] < b[j])  
            c[k++] = a[i++];  
        else  
            c[k++] = b[j++];   
    }  
  
    while (i < n)  
        c[k++] = a[i++];  
  
    while (j < m)  
        c[k++] = b[j++];  
}  

질서 있 는 수열 을 합병 하 는 효율 이 비교적 높 고 O (n) 에 이 를 수 있 음 을 알 수 있다.
위의 합병 질서 수열 문 제 를 해결 한 다음 에 병합 정렬 을 보면 그 기본 적 인 사 고 는 배열 을 2 조 A, B 로 나 누 는 것 이다. 만약 에 이 2 조 안의 데이터 가 모두 질서 가 있다 면 이 두 조 의 데 이 터 를 편리 하 게 정렬 할 수 있다.어떻게 이 두 조 안의 데 이 터 를 질서 있 게 합 니까?
A, B 조 를 각각 2 조로 나 눌 수 있다.순서대로 유추 하면 분 리 된 팀 이 하나의 데이터 만 있 을 때 이 팀 내 에 질서 가 있다 고 생각 한 다음 에 인접 한 두 팀 을 합병 하면 된다.이렇게 해서 먼저 재 귀적 으로 수열 을 분해 한 다음 에 수열 을 합치 면 병합 정렬 이 완 료 됩 니 다.
다음은 자신 이 쓴 C + + 예 와 엄 울 민 데이터 구조 교재 입 니 다.

#include<iostream>
using namespace std;
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
{
	int i = startIndex, k = startIndex;
	int j = midIndex + 1;
	for (; i <= midIndex&&j <= endIndex; ++k)
	{
		if (sourceArr[i]<sourceArr[j])
			tempArr[k] = sourceArr[i++];
		else
			tempArr[k] = sourceArr[j++];
	}
	while (i <= midIndex)
		tempArr[k++] = sourceArr[i++];
	while (j <= endIndex)
		tempArr[k++] = sourceArr[j++];
	for (int i = startIndex; i <= endIndex; ++i)
		sourceArr[i] = tempArr[i];
}
//      
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
	int midIndex;
	if (startIndex<endIndex)
	{
		midIndex = (startIndex + endIndex) / 2;
		MergeSort(sourceArr, tempArr, startIndex, midIndex);
		MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
		Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
	}
}

int main(int argc, char * argv[])
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	int b[sizeof(a)/sizeof(int)];
	MergeSort(a, b, 0, sizeof(a) / sizeof(int)-1);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
		cout << a[i] << " ";
	return 0;
}

병합 정렬 의 효율 이 비교적 높 습 니 다. 수열 의 길 이 를 N 으로 설정 하고 수열 을 작은 수열 로 나 누 면 모두 logN 단계 가 필요 합 니 다. 모든 단 계 는 질서 있 는 수열 을 합 치 는 과정 입 니 다. 시간 복잡 도 는 O (N) 로 기록 할 수 있 기 때문에 모두 O (N * logN) 입 니 다.병합 정렬 은 매번 인접 한 데이터 에서 작 동 하기 때문에 병합 정렬 은 O (N * logN) 의 몇 가지 정렬 방법 (빠 른 정렬, 병합 정렬, 힐 정렬, 쌓 기 정렬) 도 효율 이 비교적 높다.
3. 쌓 기 정렬
엄 울 민 데이터 구조 교 재 를 참고 하여 쌓 기 순 서 는 다음 과 같다.

#include<iostream>
using namespace std;
void HeapAdjust(int arr[],int s,int m)
{
	int temp = arr[s];
	for (int j = 2 * s+1; j <=m; j=j*2+1)
	{
		if (j<m && arr[j] < arr[j + 1])++j;
		if ( temp>=arr[j] )break;
		arr[s]=arr[j];
		s = j;
	}
	arr[s] = temp;
		
}
void HeapSort(int arr[], int m)
{
	for (int i = m / 2-1; i >=0; --i)
	{
		HeapAdjust(arr, i, m);
	}
	for (int i = m; i >=1; --i)
	{
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		HeapAdjust(arr, 0, i - 1);
	}
}
int main(int argc, char * argv[])
{
	int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	HeapSort(arr, sizeof(arr) / sizeof(int)-1);
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
		cout << arr[i] << " ";
	return 0;
}