C言語の2つの方法で集計ソートを実現する

再帰的に統合ソート思想を実現する

再帰的方法を用いて要素

を分割する.

一時配列を使用して配列された要素

を保存する.

一時配列の要素を元の配列

にコピーする.

void mergeAdd(int arr[], int left, int mid, int right, int *temp){  “ ”
	int i = left;
	int j = mid + 1;
	int k = left;//    
	while (i <= mid&&j <= right){
		if (arr[i] < arr[j]){
			temp[k++] = arr[i++];
		}
		else{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid){
		temp[k++] = arr[i++];
	}
	while (j <= right){
		temp[k++] = arr[j++];
	}
	// temp      arr   
	//       ，      arr[left,right),     
	//          tmp[left,right)   
	memcpy(arr + left, temp + left, sizeof(int)*(right - left+1));
}
void mergeSort(int arr[],int left,int right,int *temp){//  “ ”
	int mid = 0;
	if (left < right){
		mid = left + (right - left) / 2;
		mergeSort(arr, left, mid, temp);
		mergeSort(arr, mid + 1, right, temp);
		mergeAdd(arr, left, mid, right, temp);
	}
	
}

テストコード

int main(){
	int arr[] = { 8,4,5,7,1,3,6,2};
	int len = sizeof(arr)/sizeof(arr[0]);
	int *temp = （int*)malloc(sizeof(int)*len);

	mergeSort(arr, 0, len - 1, temp);
	free(temp);
	for (int i = 0; i < len; i++){
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

再帰集計ソートの性質
時間複雑度:O(Nlogn)
空間複雑度:O(N)
安定性あんていせい:安定ソートあんていソート
非再帰実装集計ソート

void mergeAdd1(int arr[], int left, int mid, int right, int *tmp){
	int i = left;
	int j = mid + 1;
	int k = left;//    
	while (i <= mid&&j <= right){
		if (arr[i] < arr[j]){
			temp[k++] = arr[i++];
		}
		else{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid){
		temp[k++] = arr[i++];
	}
	while (j <= right){
		temp[k++] = arr[j++];
	}
	// temp      arr   
	//       ，      arr[left,right),     
	//          tmp[left,right)   
	memcpy(arr + left, temp + left, sizeof(int)*(right - left + 1));
}
void mergeSort2(int arr[], int len，int* tmp){
	if (len <= 1){
		return;
	}
	//      gap，    1，             1   
	int gap = 1;
	for (; gap <= len; gap *= 2){
		int i = 0;
		for (; i <= len; i += 2 * gap){
			int beg = i;
			int mid = (gap - 1) + i;
			if (mid >= len){
				mid = len;
			}
			int end = mid + gap;
			if (end >= len){
				end = len;
			}
			mergeAdd1(arr, beg, mid, end, tmp);
		}
	}
}

テストコードは同じです.