这两天学习排序，简单的记录下，等看完之后再进行总结。
1.首先看了交换排序，顾名思义，也就是当无序时进行元素交换，从而达到元素有序。
【1】初级的是冒泡排序，冒泡排序的思想是：两两相邻的数据元素进行比较，如果反序则交换，直到有序为止，同时每一轮比较之后较小（大）的数上浮，较大（小）的数下沉，因此命名为冒泡排序。因为是两两相邻的数进行比较，且相等时不进行交换，所以是一种稳定的排序算法。
冒泡排序（Bubble Sort）代码实现为：
void bubblesort(vector & a) //这里的排序进行从小到大的排序，当从大到小时改变if中的条件即可{ bool change = true; //此处设置标志位的作用是当两两元素比较为有序时，则不需要进行后面的比较 for (int i = 0; i = i; j--) if (a[j]>a[j + 1]) { swap(a[j], a[j + 1]); change = true; } } cout << "bubble sort：" << endl; for (size_t k = 0; k != a.size(); k++) //此处可以用范围for语句打印 { cout << a[k] << " "; }} 【2】在冒泡的基础上改进为快速排序，快速排序的思想是：将待排序的元素分为独立的两部分，（设置pivotkey，使得它左边元素均小于它，右边的元素均大于它，返回pivotkey的下标pivot）然后再对这两部分（【low到pivot-1】和【pivot+1到high】）继续进行快排。（递归）。
当元素基本上有序时，此时选择的pivotkey将待排序的元素可能分成严重不均等的两部分，（一部分可能有一个元素，另一部分可能有n-1个元素），此时快速排序退化为冒泡排序。同时因为它比较和交换是跳跃的，所以是一种不稳定的排序方法。
快速排序（Quick Sort）代码实现为：
/*************************************************Quick Sort***********************************************************/int partition(vector & a,int low,int high){ //设置枢轴元素为第一个元素，使得枢轴元素的左边均小于它，右边均大于它,这里总是选择下标为low的元素作为pivot,改进为三中选一，或九中选一等。 int pivotkey = a[low]; while (low < high) { while (low < high&&a[high] >= pivotkey) high--; swap(a[low], a[high]); while (low < high&&a[low] <= pivotkey) low++; swap(a[low], a[high]); } return low;}void Quicksort(vector & a,int low,int high) //当数组大时快排效果好，当数组小时，因为快排中总是用递归，反而性能不好，此处可以加一个判断，当大于某个临界时用快排，否则用直接插入排序{ int pivot; if (low < high) //if((high-low)>MAX_LENGTH) { pivot = partition(a, low, high); Quicksort(a,low,pivot-1); Quicksort(a,pivot+1,high); } //else //Insertsort(a);}
2.对选择排序，重点在选择二字，也就是每进行一轮比较，选择出最小（大）元素，选择好后再进行交换。
因为是跳跃式交换，所以是一种不稳定的排序算法。
【1】简单选择排序（Simple Selection Sort）代码实现为：
void selectsort(vector & a){ for (int i = 0; i < a.size(); i++) { int min = i; for (int j = i + 1; j < a.size(); j++) if (a[min]>a[j]) min = j; if (i != min) swap(a[min], a[i]); } cout << "simple selection sort：" << endl; for (auto c : a) cout << c << " ";} 【2】在简单选择选择排序的基础上改进出了一种新的方法为堆排序，堆排序重点在于建立堆和重建堆，堆首先是一颗完全二叉树，分为大顶堆和小顶堆。（这里默认读者已经对堆的概念已经掌握），算法的主要步骤是：首先对待排序的元素建立一个大顶堆（从非叶节点开始），然后交换堆顶元素（最大的元素）（移走）和末尾元素，对剩下的元素（n-1）进行重建堆，就会得到次大的元素，不断的重复，就可以得到一个有序序列了。
它比较和交换是跳跃的，所以是一种不稳定的排序方法。
堆排序（Heap Sort）代码实现为：
void HeapAdjust(vector & array, int i, int len) //调整第i个元素，使之成为一个大顶堆（下溯过程）,(隐含了i的左右两边已经是堆的情况){ int temp = array[i]; int j = 2 * i + 1; while (j < len) { if (j + 1 < len && array[j] < array[j + 1]) ++j; if (array[j] < temp) break; else { array[i] = array[j]; i = j; j = 2 * i + 1; } } array[i] = temp;}void heapsort(vector & a){ //建立一个大顶堆（也可以是小顶堆），从非叶节点开始建立堆 for (int i = (a.size() - 2) / 2; i >= 0; i--) HeapAdjust(a, i, a.size()); for (int i = a.size() - 1; i>0; i--) { swap(a[0], a[i]); HeapAdjust(a, 0, i ); //表示调整第0个元素，让剩下的i个元素保持大顶堆 } cout << "heap sort：" << endl; for (auto c : a) cout << c << " "; }
3.插入排序，它的思想是将一个记录插入到已经排序好的有序表中，从而得到一个新的，记录数增1的有序表。具体是这样实现的：从第二个元素开始（外循环），依次与前面的元素进行比较（内循环），然后选择合适的位置插入元素。
也就是设置a[i]（从第二个元素开始）为哨兵，每次将a[i]和a[i-1]进行比较，如果无序，则将元素后移，直到找出正确的位置插入a[i]。因为插入的元素如果与之前一个元素相等，插入的位置为相等元素的后面，所以是一种稳定的排序算法。在直接插入排序的基础还有二分插入排序和二路插入排序。
【1】直接插入排序（Insertion Sort）代码实现为：
/**************************************************Insertion Sort***************************************************/void Insertsort(vector & a){ int temp,j; for (int i = 1; i != a.size(); ++i) //外循环 { if (a[i] < a[i - 1]) { temp = a[i]; //复制为哨兵，也就是待排序（插入）的元素 for (j = i - 1; j >= 0 && temp < a[j]; j--) //比哨兵大（小）的元素后移，内循环 a[j + 1] = a[j]; a[j + 1] = temp; //插入到正确的位置 } } cout << "Insertion sort：" << endl; for (auto c : a) cout << c << " ";} 二分插入排序代码：
/******************在直接插入的基础上有二分插入排序和二路插入排序****************************************************/void BInsertsort(vector & a) //二分插入排序{ int temp, j,low,high; for (int i = 1; i != a.size(); ++i) { if (a[i] < a[i - 1]) { low = 0; high = i - 1; temp = a[i]; while (low <= high) //和直接插入排序不同的就是在low和high中折半查找插入的位置 { int m = (low + high) / 2; if (temp < a[m]) high = m - 1; else low = m + 1; } //循环完后low>high,[high+1]为插入位置 for (j = i - 1; j>=high+1; j--) a[j + 1] = a[j]; a[high + 1] = temp; //插入到正确的位置 } } cout << "Binary Insertion sort：" << endl; for (auto c : a) cout << c << " ";} 【2】在直接插入排序的基础上，对其进行了改进有了希尔排序，本质是一样的，都是找到正确的插入位置插入待排序的元素，希尔排序的精华在于：不像直接插入排序，小的关键字a[i]不是一步一步向前移动（a[i]与a[i-1]比较），而是跳跃式的向前移动（a[i] 与a[i - increasment]比较），跳跃的距离取决于增量序列 increasment，但最后的增量值一定是1，这样和直接插入排列一样，但移动的次数大大减小，因为元素已经基本有序。因为是跳跃式的移动和比较，所以是一种不稳定的排序方法。
希尔排序（Shell Sort）代码实现为：
/********************************************Shell Sort*****************************************************************/void Shellsort(vector & a){ int temp,j; int increasment = a.size() / 2; //设置增量序列 while (increasment >= 1) //最后的增量序列必须为1，类似与插入排序，才能保证序列有序 { for (int i = increasment; i != a.size(); ++i) { if (a[i] < a[i - increasment]) { temp = a[i]; //复制为哨兵，也就是待排序（插入）的元素 for (j = i - increasment; j >= 0 && temp < a[j]; j-=increasment) //比哨兵大（小）的元素后移 a[j + increasment] = a[j]; a[j + increasment] = temp; //插入到正确的位置 } } increasment/= 2; } cout << "Shell sort：" << endl; for (auto c : a) cout << c << " ";}
4.归并排序，它的思想是：借助辅助空间temp，将待排序序列a分成若干个子序列，再进行归并为有序的temp，之后再把有序的temp归并为整体有序序列a。
归并排序有两种实现方式：第一种是递归方法实现，空间复杂度除了temp,还有递归用到的栈空间，所以整体的空间复杂度为n+log2n;而非递归方法，只有辅助空间temp，所以它的空间复杂度为n，因此归并排序更推荐使用非递归归并排序方法。因为它比较元素时如果相等，先将位于序列前面的元素归并在前面，所以不会改变相等元素的顺序，是一种稳定的排序方法。此处是两两归并，也称2路归并排序。
归并排序（Merging Sort）代码实现为：
【1】递归方法：
/*******************************************Merging Sort(递归方法)*****************************************************************///此函数的功能是借助temp将a（从i到n大小，以m为分界的两个子序列）归并（合并）为一个有序的序列a.（先将a中的子序列归并到temp,再将归并好的子序列传回给a）void Merge(vector &temp,vector &a,int i,int m,int n){ int j,k,l,beg=i; for (j = m + 1, k = i; i <= m &&j <= n; ++k) { if (a[i] <= a[j]) //此处为小于等于，否则不是稳定的排序方法 temp[k] = a[i++]; else temp[k] = a[j++]; } if (i <= m) //将剩余的元素a[i.....,m]复制到temp { for (l = 0; l <= m - i; l++) temp[k + l] = a[i + l]; } if (j <= n) //将剩余的元素a[j.....,n]复制到temp { for (l = 0; l <= n - j; l++) temp[k + l] = a[j + l]; } for (; beg <= n; beg++) //这里实现将a归并的后的temp赋给a,也就是temp[beg....n]复制到a[beg....n],此处beg为刚传进来的i,所以开始的时候i没有参与运算时要进行初始化beg a[beg] = temp[beg];}//temp为辅助空间，a为待排序的序列，将a不断分为若干个子序列,归并到temp,再传回给avoid Msort(vector &temp, vector &a, int s, int e){ int m; if (s 