並べ替えアルゴリズム練習(速列&&スタック)——hdu 1040

2248 ワード

水問題は、主に速排と積み上げを学ぶために使われています.
これらのアルゴリズムはデータ構造の授業で接触したことがある.
しかし、本当に自分の手で問題に直面したときになってから、その役割と本当の意味を理解することができます.
速い列は基本的に自分で山の列をマスターすることができて、やはり本を読んでから書くことができます.
スタックのアルゴリズムには少し理解できないものがある.
テーマ————————hdu 1040
ACコード:
きゅうそくれつ
#include
#include
using namespace std;

/*
  
*/

int a[1002];

void quicksort(int a[], int l, int r){
	if (l < r){
		int i, j, x;
		i = l;
		j = r;
		x = a[i];
		while (i < j){
			while (ix){
				j--;   //          x  
			}
			if (i < j){
				a[i++] = a[j];
			}
			while (i < j&&a[i] < x){
				i++;  //          x  
			}
			if (i < j){
				a[j--] = a[i];
			}
		}
		a[i] = x;
		quicksort(a, l, i - 1);
		quicksort(a, i + 1, r);
	}
}

int main(){
//	freopen("TestDate.txt", "r", stdin);

	int n,tnum,i;
	cin >> n;
	while (n--){
		cin >> tnum;
		for (i = 0; i < tnum; i++)
			cin >> a[i];
		quicksort(a,0,tnum-1);
		for (i = 0; i < tnum; i++){
			cout << a[i];
			if (i + 1 != tnum){
				cout << " ";
			}
			else{
				cout << endl;
			}
		}
	}
	return 0;
}

スタック
#include
#include
using namespace std;

int a[1002];

void heap_down(int a[], int start, int end){
	int c = start;
	int l = 2 * c + 1;
	int tmp = a[c];
	for (; l <= end; c = l, l = 2 * l + 1){
		if (l < end&&a[l] < a[l + 1]){
			l++;
		}
		if (tmp >= a[l]){
			break;
		}
		else{
			a[c] = a[l];
			a[l] = tmp;
		}
	}
}

void swap(int *a, int *b){
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void heap_sort_asc(int a[], int n){
	int i;
	for (i = n / 2 - 1; i >= 0; i--){
		heap_down(a, i, n - 1);
	}
	for (i = n - 1; i > 0; i--){
		swap(&a[0], &a[i]);
		heap_down(a, 0, i - 1);
	}
}

int main(){
	freopen("TestDate.txt", "r", stdin);
	int n, tnum, i;
	cin >> n;
	while (n--){
		cin >> tnum;
		for (i = 0; i < tnum; i++)
			cin >> a[i];
		heap_sort_asc(a, tnum);
		for (i = 0; i < tnum; i++){
			cout << a[i];
			if (i + 1 != tnum){
				cout << " ";
			}
			else{
				cout << endl;
			}
		}
	}
	return 0;
}