弱化版直接插入
void InsertSort(int*a,int n){ assert(a); int end=n-2; int x; while(end>=0){ //针对的是原本有顺序的，最后一个和x比，然后加入x后恢复有序 if(a[end]>x){ a[end+1]=a[end]; --end; } else { break; } } a[end+1]=x; }
原本是有序，插入x来使数组继续有序
//升级一下,假如说是随机数，怎么来给他变成有序。 //我们需要假设有序，也就是第一个数存在时，认为第一个数有序，然后第二个数是插入，然后。。。到最后（n个数组也就是 end最后n-2,和插入的最后一个n-1来比较插入 void InsertSort(int *a,int n) { assert(a); for(int i=0;i<n-1;i++){ int end=i;//从头开始默认谁开始就是最后一个，也就是最大的，换句话说无时无刻都在插入的过程 while(end>=0){ if(a[end]>x){ // a[end+1]=a[end]; //最好O（N）有顺序，最坏O（N*N） --end; } else{ break; } } }
弱化版希尔排序
gap是分组的意思，也就是分三组，开始只换9和5.把一个大问题慢慢分成小问题
void ShellSort(int*a,int n){ //按gap分组数据进行排,说白了就是预排处理 int gap=3; int end=0； int x=a[gap+end]; while(end>=0){ if(a[end]>x){ a[end+gap]=a[end]; end-=gap; } else { break; } a[end+gap]=x; } } }
假如是分三组，就是将
较弱版希尔排序，简单的排一组
void ShellSort(int*a,int n){ //按gap分组数据进行排,说白了就是预排处理 int gap=3; for(int i=0;i<n-gap;i+=gap) //加了一个这个，简单排一组的黑线， int end=i; int x=gap+end; //为什么是n-gap看下面 while(end>=0){ if(a[end]>x){ a[end+gap]=a[end]; end-=gap; } else { break; } a[end+gap]=x; } } }
为什么要在n-gap : 首先i=0；，n-gap就是上面的6，6的前面是倒数第二个黑线，我们是要把下一个视为插入的元素，那么就是要他们在他们这些线的倒数第二个元素之前都可以，但是也同样不能碰到后面的那几个，因为他们彼此是最后一个元素，所以只有n-gap处于刚刚好的位置。
这是排的一组黑线，如果要全排完,看下面
完全版，希尔排序：一组一组的排版
void ShellSort(int*a,int n){ //按gap分组数据进行排,说白了就是预排处理 int gap=3; for(int j=0;j<gap;++j) for(int i=j;i<n-gap;i+=gap) int end=i; int x=gap+end; while(end>=0){ if(a[end]>x){ a[end+gap]=a[end]; end-=gap; } else { break; } a[end+gap]=x; } } }
多组一起排版：
void ShellSort(int*a,int n){ //按gap分组数据进行排,说白了就是预排处理 int gap=3; for(int i=0;i<n-gap;++i){ int end=i; int x=gap+end; while(end>=0){ if(a[end]>x){ a[end+gap]=a[end]; end-=gap; } else { break; } a[end+gap]=x; } } }
多组一起排：也就是将9和5先换，然后1和7.。，都给他排一遍
希尔排序，也就是预排序可以进行多次，
因此诞生了 多组预排序➕直接插入（gap==1）假如gap ==1希尔排序就会变成直接插入排序
void ShellSort(int*a,int n){ //按gap分组数据进行排,说白了就是预排处理 int gap=n; while(gap>1){ gap/=2 //或者gap=gap/3+1 for(int i=0;i<n-gap;++i){ int end=i; int x=gap+end; while(end>=0){ if(a[end]>x){ a[end+gap]=a[end]; end-=gap; } else { break; } a[end+gap]=x; } } }
gap无论是上面的除二还是除3最后都必须保证有一个个数是一个一，所以是看N来进行选择gap 到底要选择什么。
所以最好的是O（n）自然有顺序
最坏是换组拿最大的换也就是 (1+2+……+到N/gap)*gap 算是拿那个一组一组的gap分的
将gap带入N/2 最后时间复杂度差不多是N*logN
选择排序：
void Swap(int*ps,int*py){ int tmp=*ps; *ps=*py; *py=tmp } void SelectSort(int*a,int n){ int begin=0; int end=n-i; while(begin<end){ //奇数的话会自己相等，偶数的话会自己错开 int mini=begin; //随便给个值，但不可以不给，不能选值而是选择下标 int maxi=begin; if(a[i]<a[mini]){ mini=i; } if(a[i]>a[maxi]){ maxi=i; }//找最大和最小下标 Swap(&a[begin],&a[mini]); if(begin==maxi){ //这一步很重要，具体下面具体阐述 maxi=mini; } Swap(&a[end],&a[maxi]); ++begin; --end; } }
选择排序，先找最大和最小的，两个两个来，然后两个次大的和次小的。。。一直一直直到彼此错开。
如果没有注释的那行代码，会导致最大的和begin在一个位置，这样1和begin换位置的同时，最大的位置26改变，但是maxi的位置却没有改变，导致，maxi位置在交换的时候会出现错误。
选择排序的缺点就是时间复杂度O（N^2） 因为不管是顺序还是逆序我们都要进行遍历一遍，然后再判断谁是最大的，谁是最小的，所以复杂度会很高
