1.插入排序算法
直接插入排序：
插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。稳定
void InsertSort(int* a,int size){ assert(a); for(int i=0;i =0 && a[end]>tmp) { a[end+1]=a[end]; end--; } a[end+1] = tmp; }}void print(int* a,int size){ for(int i=0;i
希尔排序算法
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ， 则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题，
希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。时间和空间复杂度是 O(N^1.3)，O(1) 不稳定
void ShellSort(int* a,int size){ int gap = size; while(gap>1) { gap = gap/3+1; for(int i=0;i =0 && a[end]>tmp) { a[end+gap] = a[end]; end-=gap; } a[end+gap]=tmp; } }} 2.选择排序算法
选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(N^2 ) 和 O(1) 。不稳定
void SelectSort(int* a,int size){ for(int i=0;i 3.堆排序
时间和空间复杂度是 O(N*lgN)，O(1) 不稳定
void Adiustdown(int* a,int size,int root){ int child = root*2+1; while(child a[root]) { swap(a[child],a[root]); } root = child; child = root*2+1; }}void HeapSort(int* a,int size){ for(int i=(size-2)/2;i>=0;i--) { Adiustdown(a,size,i); } for(int i=size-1;i>=0;i--) { swap(a[0],a[i]); Adiustdown(a,i,0); }}
3.冒泡排序算法
冒泡排序是將比較大的數字沉在最下面，较小的浮在上面
时间和空间复杂度是 O(N^2)，O(1) 稳定
void BubbleSort(int* a,int size){ for(int i=0;i a[j+1]) { swap(a[j],a[j+1]); } } }} 4.快速排序算法
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的，本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base，首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后,从序列的最左边开始找比base大的，如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小，循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。时间和空间复杂度是 O(N*lgN)，O(lgN) 不稳定
//左右指针int SingleSort(int* a,int left,int right){ size_t key = right; size_t begin = left; int end = right-1; while(begin a[key]) { end--; } swap(a[begin],a[end]); } if(a[end]>a[key]) { swap(a[end],a[key]); } return end;}void QuickSort(int* a,int left,int right){ if(left =a[key]) { cur++; } if(cur 5.归并排序算法
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间 时间和空间复杂度是 O(N*lgN)，O(N) 稳定
void Merge(int* a,int* dst, int begin1,int end1,int begin2,int end2){ int index = begin1; while(begin1 二、非比较排序
//基数排序 时间和空间复杂度是 O(N*位数)，O(N) 稳定int digit(int* a,int size){ int sum = 1; int num = 1; for(int i=0;i sum*10) { sum*=10; num++; } } return num;}void BaseSort(int* a,int size){ int dig = digit(a,size); int sum = pow(10,dig); int num = 1; int *dst = new int[size]; memset(dst,0,sizeof(int)*size); while(num<=sum) { int counts[10]={0}; int start[10]={0}; for(int i=0;i max) { max=a[i]; } } int *array = new int[max]; int *dst = new int[size]; memset(dst,0,sizeof(int)*size); memset(array,0,sizeof(int)*max); for(int i=0;i size) break; } } memcpy(a,dst,sizeof(int)*size); delete[] dst;}void CountSortTest(){ int array[10] ={25,13,75,86,32,8,41,50,69,77}; CountSort(array,10); print(array,10);}