堆排
#include<iostream> #include<cstring> #include<cstdio> #include<string> #include<queue> #include<algorithm> #include<functional> #include<stack> using namespace std; const int MAX = 3005; int num[MAX * MAX ], T[ MAX ]; void AjustHeap(int *num, int i, int n){ int temp = num[i]; int j = 2 * i; while (j <= n){ if (j + 1 <= n && num[j] >= num[j + 1]) j++; if (num[j] >= temp) break; num[i] = num[j]; i = j; j = 2 * i; } num[i] = temp; } void BuildHeap(int *num, int n){ for (int i = n / 2; i >= 1; i--){ AjustHeap(num, i, n); } } void HeapSort(int *num,int n){ for (int i = n; i > 1; i--){ swap(num[1], num[i]); AjustHeap(num, 1, i - 1); } } int main(){ int n, m; while (scanf( "%d%d", &n, &m ) != EOF){ for (int i = 1; i <= n; ++i) scanf("%d", &T[i]); //cin >> T[i]; int k = 1; for (int i = 1; i <= n; ++i){ for (int j = i + 1; j <= n; ++j){ num[k++] = T[i] + T[j]; } } BuildHeap(num, k); HeapSort(num, k ); for (int i = 1; i < m; ++i) printf("%d ", num[i]); //cout << num[i] << " "; printf("%d\n", num[m]); //cout << num[ m ] << endl; } return 0; }
快排
#include<iostream> #include<cstring> #include<cstdio> #include<string> #include<queue> #include<algorithm> #include<functional> #include<stack> using namespace std; const int MAX = 15; int num[MAX]; void QuickySort(int *num, int l, int r){ int value = num[l]; if (l > r){ return; } int i = l, j = r; while ( i < j){ while (i < j && num[j] >= value) j--; num[i] = num[j]; while (i < j && num[i] <= value) i++; num[j] = num[i]; } num[i] = value; QuickySort(num, l, i - 1); QuickySort(num, i + 1, r); } int main(){ int Cast,n; cin >> Cast; while (Cast--){ cin >> n; for (int i = 1; i <= n; ++i){ cin >> num[i]; } QuickySort(num, 0, n); cout << num[2] << endl; } return 0; }
归并
/* *********************************************** Author :bo-jwolf Created Time :2015年02月26日 星期四 15:20:17 File Name :guibing.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAX = 10005; int num[ MAX ], temp[ MAX ]; int n; void Merge( int *num, int *temp, int s, int mid, int e ){ int i = s, j = mid + 1, k = s; while( i <= mid && j <= e ){ if( num[ i ] < num[ j ] ) temp[ k++ ] = num[ i++ ]; else temp[ k++ ] = num[ j++ ]; } while( i <= mid ){ temp[ k++ ] = num[ i++ ]; } while( j <= e ){ temp[ k++ ] = num[ j++ ]; } for( int i = s; i <= e; ++i ){ num[ i ] = temp[ i ]; } } void Sort( int *num, int *temp, int s, int e ){ if( s == e ) temp[ s ] = num[ s ]; else{ int mid = ( s + e ) >> 1; Sort( num, temp, s, mid ); Sort( num, temp, mid + 1, e ); Merge( num, temp, s, mid, e ); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while( cin >> n ){ for( int i = 1; i <= n; ++i ){ cin >> num[ i ]; } Sort( num, temp, 1, n ); for( int i = 1; i <= n; ++i ){ cout << num[ i ] << endl; } } return 0; }