並べ替えアルゴリズム練習(速列&&スタック)——hdu 1040
2248 ワード
水問題は、主に速排と積み上げを学ぶために使われています.
これらのアルゴリズムはデータ構造の授業で接触したことがある.
しかし、本当に自分の手で問題に直面したときになってから、その役割と本当の意味を理解することができます.
速い列は基本的に自分で山の列をマスターすることができて、やはり本を読んでから書くことができます.
スタックのアルゴリズムには少し理解できないものがある.
テーマ————————hdu 1040
ACコード:
きゅうそくれつ
スタック
これらのアルゴリズムはデータ構造の授業で接触したことがある.
しかし、本当に自分の手で問題に直面したときになってから、その役割と本当の意味を理解することができます.
速い列は基本的に自分で山の列をマスターすることができて、やはり本を読んでから書くことができます.
スタックのアルゴリズムには少し理解できないものがある.
テーマ————————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;
}