1、选择排序 过程简单描述： 首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。
#include<iostream> #include<algorithm> using namespace std; const int N = 10; int a[N] = { 21, 26, 5, 96, 45, 12, 26, 14, 15, 12 }; int main() { for (int i = 0; i <N; i++) { int min = i; for (int j = i + 1; j < N; j++) { if (a[j] < a[min]) { int temp = a[j]; a[j] = a[min]; a[min] = temp; } } } for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }首先来分析一下选择排序的时间复杂度，不管最好最坏情况时间复杂度都为O(1);空间复杂度为O（1），则为原地排序 涉及非相邻元素的交换，所以为非稳定排序。
2、插入排序 过程简单描述： 1、从数组第2个元素开始抽取元素。
2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。
3、继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。 代码实现
#include<iostream> #include<algorithm> using namespace std; const int N = 10; int a[N] = { 21, 26, 5, 96, 45, 12, 26, 14, 15, 12 }; int main() { for (int i = 1; i < N; i++) { int temp = a[i]; int k = i - 1; while (k >= 0 && a[k] > temp) { a[k + 1] = a[k]; k--; } a[k + 1] = temp; } for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }时间复杂度O（n^2），空间复杂度O（1），稳定排序，原地排序
3、冒泡排序 过程简单描述： 1、把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置….
我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。
除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。 代码实现：
#include<iostream> #include<algorithm> using namespace std; const int N = 10; int a[N] = { 21, 26, 5, 96, 45, 12, 26, 14, 15, 12 }; int main() { for (int i = 0; i < N; i++) { for (int j =0; j < N - i-1; j++) { if (a[j+1] < a[j]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了，我们无需再对剩余的元素重复比较下去了。
#include<iostream> #include<algorithm> using namespace std; const int N = 10; int a[N] = { 21, 26, 5, 96, 45, 12, 26, 14, 15, 12 }; int main() { for (int i = 0; i < N; i++) { bool mark = true; for (int j =0; j < N - i-1; j++) { if (a[j+1] < a[j]) { mark = false; int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } if (mark) break; } for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }时间复杂度O（n^2），只涉及到相邻元素的交换，当我们写代码时设置a[n-1]==a[n]时，什么都不用做，所以为稳定排序。 空间复杂度O（1），所以为原地排序。 改进后的代码中，最好时间复杂度为O(n)，最坏为O(n^2)。 所以平均为O（n^2）。
对选择、冒泡、插入三种排序选择的考虑 我们一般不会用选择排序，原因很简单，因为它是非稳定排序，这在整数的排序确实好像没什么实际作用，但如果是自定义数据结构排序呢？，比如说一个学生类，我们只是用学生成绩排名，但当成绩相同时，我们就能说它们的排名是一样的么。现实中并不是，我们要重新选择另外一种属性（比如说语文成绩的高低），这时，稳定和非稳定就显得非常重要。** 4、希尔排序（插入排序的优化） 希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。
希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。 代码实现：
#include<iostream> #include<algorithm> using namespace std; const int N = 10; int a[N] = { 21, 26, 5, 96, 45, 12, 26, 14, 15, 12 }; int main() { for (int i = N / 2; i > 0; i/= 2) { for (int j = i; j < N; j++) { int temp = a[j]; int k; for ( k = j - i; k >=0 && temp < a[k]; k -= i) a[k + i] = a[k]; a[k + i] = temp; } } for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }时间复杂度O（NlogN），空间复杂度O（1），为原地排序。 为非稳定排序，比如 3 9 5 5->3 5 5 9，相同元素前后位置发生变化
5、归并排序 过程简单描述： 将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。 递归实现：
#include<iostream> using namespace std; const int N = 10; int a[N] = { 21, 26, 5, 96, 45, 12, 26, 14, 15, 12 }; void arr_insert(int l, int mid, int r) { int *temp = new int[r - l + 1]; int i = l; int j = mid + 1; int k = 0; while (i <= mid && j <= r) { if (a[i] < a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; while (j <=r) temp[k++] = a[j++]; for (int i = 0; i < k; i++) a[l++] = temp[i]; } void binary_sort(int l, int r) { if (l < r) { int mid = (l + r) / 2; binary_sort(l, mid); binary_sort(mid + 1, r); arr_insert(l,mid, r); } } int main() { binary_sort(0, N-1); for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }归并排序空间复杂度为O（N），所以为非原地排序。 时间复杂度如何计算： 由递归可知，归并排序的效率与原数组的有序程度无关，时间复杂度都为O（NlogN），为稳定性排序。 6、快速排序 实现简单描述： 我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。 算法实现：
#include<iostream> using namespace std; const int N = 5; int a[N] = {6,11,3,9,8}; int partition(int l, int r) { int i, j; i = j = l; int temp = a[r]; for (; j < r; j++) { if (a[j] < temp) { int ans = a[j]; a[j] = a[i]; a[i] = ans; i++; } } int ans = a[i]; a[i] = temp; a[r] = ans; return i; } void quicksort(int l, int r) { if (l > r) return; int i = partition(l,r); quicksort(l, i - 1); quicksort(i + 1, r); } int main() { quicksort(0, N-1); for (int i = 0; i < N; i++) cout << a[i] << endl; getchar(); getchar(); }空间复杂度O（1），为原地排序。 对于时间复杂度，对于最坏情况（数组已经有序），比如说1,3,5,6,7，8中，进行n次分区，每次扫描n次，时间复杂度为O（n^2）. 最好情况（均等分区），时间复杂度为O（nlongn）。
