● 直接插入排序(Insert Sort)
1、算法描述:
该算法是一种简单直观的是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上只需用到O(1)的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
2、步骤:
1)从第一个元素开始,该元素可以认为已经被排序
2)取出下一个元素,在已经排序的元素序列中从后向前扫描
3)如果该元素(已排序)大于新元素,将该元素移到下一位置
4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5)将新元素插入到该位置中
6)重复步骤2
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率,但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。
具体实现如下:
voidInsertSort(int*arr,size_tsize)//直接插入排序 { assert(arr); for(size_ti=0;i<size-1;++i) { intend=i; inttmp=arr[i+1];//tmp取出要插入的元素(下一个元素) while(end>=0&&arr[end]>tmp)//end要大于等于0 { arr[end+1]=arr[end];//大于tmp的数后移 --end; } arr[end+1]=tmp; } }
● 希尔排序(Shell Sort)
1、算法描述:
希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序而提出改进方法的。设置增量为gap=size/3+1,在gap不为1时,希尔排序是在进行预排序,在gap==1时,进行插入排序时,可提高效率。
1)设置增量gap为size
2)使gap=gap/3+1,同时对所有组进行插入排序,直到size-gap-1时,表示所有组已经排序完成
3)重复步骤2,直到gap为1时停止
具体实现如下:
voidShellSort(int*arr,size_tsize)//希尔排序 { assert(arr); intgap=size;//gap设置插入排序区间 while(gap>1) { gap=gap/3+1;//防止gap为2时,下一次gap为1,使得最后一次的gap为1 //例如(254936871)使多组同时进行直接插入排序 for(size_ti=0;i<size-gap;++i) { intend=i; inttmp=arr[i+gap]; while(end>=0&&arr[end]>tmp) { arr[end+gap]=arr[end]; end-=gap; } arr[end+gap]=tmp; } } }
● 选择排序(Select Sort)1、算法描述:
首先在未排序序列中找到最小和最大元素,存放到排序序列的两端,然后,再从剩余未排序元素中继续寻找最小和最大元素,然后放到排序序列(该序列缩短了2个元素,不包含原序列的两端)两端。以此类推,直到所有元素均排序完毕。
1)一重循环:通过i和size控制进行寻找最小和最大元素的区间
2)使min为区间的首位元素位置,max为区间的末尾元素位置
3) 二重循环:从序列中寻找最小和最大元素,注意在进行不断比较过程中进行交换,不能在找到的它们的下标后才进行交换。
具体实现如下:
voidSelectSort(int*arr,size_tsize) { intmin,max; for(size_ti=0;i<size;++i,--size) { min=i; max=size-1;//max为当前选择排序段的最后一个数据 //max=size-1-i时:注意不能用size进行减1,防止max=size-i-i中size的改变,重新定义len进行变化 for(intj=i;j<=max;++j) { if(arr[j]<arr[min]) { swap(arr[j],arr[min]); } if(arr[j]>arr[max]) { swap(arr[j],arr[max]); } } } }
● 堆排序(Heap Sort)
堆积排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
升序序列的实现需要建立大堆,降序序列的实现需要建立小堆。下面对升序序列的实现进行分析。
1)大堆的建立:通过下调建立大堆,先比较左右子结点的大小,使child指向较大数,再比较父亲结点的child所指数据的大小,小于孩子结点就进行交换。
2)每次使堆的左右子树为大堆,故从下向上进行大堆的建立
3)交换堆顶元素的堆的最后一个元素,然后重新使堆(不包含最后一个元素)成为大堆
4)重复步骤3,直到堆中只有一个元素为止
具体实现如下:
voidAdjustDown(int*arr,size_tparent,size_tsize)//建大堆(每次选出最大的放在后面) { size_tchild=2*parent+1; while(child<size) { if(child+1<size&&arr[child+1]>arr[child]) { ++child; } if(arr[child]>arr[parent]) { swap(arr[child],arr[parent]); parent=child; child=2*parent+1; } else { break; } } } voidHeapSort(int*arr,size_tsize)//升序(大堆),降序(小堆) { assert(arr); for(inti=(size-2)/2;i>=0;--i)//注意边界条件,i>=0和i=(size-2)/2 { AdjustDown(arr,i,size); } for(size_ti=0;i<size;++i) { swap(arr[0],arr[size-1-i]);//交换,使大数放在堆的最后 AdjustDown(arr,size-1-i); } }
● 冒泡排序(Bubble Sort)
重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误(升序的)就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换(flag==0),也就是说该数列已经排序完成。该算法是越小的元素会经由交换慢慢“浮”到数列的顶端。
1)设置标志flag。
2)从开始第一对到结尾的最后一对,比较相邻的元素。如果第一个比第二个大,就交换他们两个。
3)如果flag==0,则在进行一趟比较后没有发生交换,则序列已经有序了。
4)持续每次对越来越少的元素重复步骤2、3,总共进行了size-1趟。
具体实现如下:
voidBubbleSort(int*arr,size_tsize)//冒泡排序,依次将大数据存放在后面 { assert(arr); intflag=0;//标志位判断数组是否接近有序 for(size_ti=0;i<size-1;++i)//进行了size-1趟冒泡 { for(size_tj=0;j<size-i-1;++j)//进行比较,交换 { if(arr[j]>arr[j+1]) { swap(arr[j],arr[j+1]); flag=1; } } if(flag==0)//一趟结束后没有一次交换,跳出循环 { break; } } }
其余比较排序算法的实现见博主的下一篇博文