一些知识点：
常见的 n^2 的排序算法有：冒泡排序，选择排序，交换排序
常见的 nlogn 的排序算法有：归并排序（稳定排序），快速排序，堆排序，利用AVL 排序
代码实现：
冒泡排序（稳定排序）：
/**************************************** * File Name: bubble_sort.cpp * Author: sky0917 * Created Time: 2014年04月 2日 20:16:56 ****************************************/ #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1001; int a[maxn]; int main(){ int n; while (scanf("%d",&n)!=EOF){ for (int i=0; i<n; i++){ scanf("%d",&a[i]); } for (int i=0; i<n; i++){ for (int j=0; j<n-1; j++){ if (a[j] > a[j+1]){ swap(a[j], a[j+1]); } } } for (int i=0; i<n; i++){ printf("%d\n",a[i]); } } return 0; }
选择排序（不稳定排序）：
/**************************************** * File Name: select_sort.cpp * Author: sky0917 * Created Time: 2014年04月 2日 20:31:51 ****************************************/ #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1002; int a[maxn]; int main(){ int n; while (scanf("%d",&n)!=EOF){ for (int i=0; i<n; i++){ scanf("%d",&a[i]); } for (int i=0; i<n; i++){ int g = i; for (int j=i+1; j<n; j++){ if (a[j] < a[g]){ g = j; } } swap(a[i], a[g]); } for (int i=0; i<n; i++){ printf("%d\n",a[i]); } } return 0; }
举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法
原文：http://www.cnblogs.com/sky0917/p/3641566.html
