文章目录:1.插入排序2 .水蛭排序3 .选择排序4 .鼓泡排序5 .堆积排序6 .快速排序5.1 hoare版本(左右指针法) 5.2挖洞法5.2.1递归5.2.2非递归5.3前后端口
1 .插入排序
步骤:
1 .从第一个元素开始,该元素被认为已经排序
2 .取下下一个元素tem,从后向前扫描已排序的元素序列
3 .如果元素大于tem,则将元素移动到下一位
4 .重复步骤3,直到找到排序的元素中小于或等于tem的元素
5.tem插入在元素之后,如果所有已排序的元素都大于tem,则在下标为0的位置插入tem
6 .重复步骤2至5
http://www.Sina.com/http://www.Sina.com /
假设在要排序的元素中,前n-1个元素是按顺序排列的,则第n个元素将插入到前面的数组中,就像前n个元素是按顺序排列的一样。 使用此方法插入所有元素,直到整个序列变得有序。
但是,我们不能确定排列的元素的哪个部分是有序的,所以一开始只能认为第一个元素是有序的,然后依次把后面的元素插入这个有序的数组中,直到整个数组都是有序的。动图演示如下:
voidinsertsort(int*arr,int n ) for ) intI=0; i n - 1; I )//记录有序数组最后一个元素的下标int end=i; //要插入的元素int tem=arr[end 1]; //一列while(end=0) ) /大于插入的数量时为if ) temarr[end] ) {arr[end 1]=arr[end]; 结束---; //小于插入的数量,循环else{break; }}//tem放在小于插入数的后面的arr[end 1]=tem; //有两种情况可以将代码运行到此位置://1。 查找要插入的元素应插入的位置(break循环到此为止)//2。 (要插入的元素小于当前排序序列中的所有元素) while循环结束到此为止) )时间复杂度)最坏情况为o ) n ) n ),在这种情况下排序为逆序或接近逆序
有时是o(n ),在这种情况下,排序对象列接近升序或升序。
空间复杂性: o(1) ) ) ) ) ) ) ) ) )。
2 .希尔排序思路:
1 .选择小于n的整数gap作为第一个增量,然后将所有远离gap的元素分成同一组,并直接插入和排序各组的元素。 然后,取小于第一个增量的整数作为第二个增量,重复上述操作.
2 .增量大小减小到1表示整个序列被分成一个组,直接插入排序一次,排序完成。 http://www.Sina.com/http://www.Sina.com /
希尔排序在排序前对要排序的列进行排序,使要排序的列接近有序,然后再次插入该列进行排序。 在这种情况下,插入排序时间复杂度是o(n ),
代码如下:
//希尔排序voidshellsort(int*arr,int n ) ) intgap=n; while(gap1)//每次对gap进行折半操作的gap=gap/2; //1次排序for(intI=0; i n - gap; I ) {int end=i; int tem=arr[end gap]; while(end=0) ) if ) temarr[end] ) {arr[end gap]=arr[end]; 结束-=Gap; }else{break; }}arr[end gap]=tem; }}平均时间复杂度: o(n^1.3 )
空间复杂性: o(1) ) ) ) ) ) ) ) ) )。
3 .排序步骤:
从要排序的列中一次选择一个最小值,并将其置于序列的开头,直到所有数据都已排序。
实际上,通过一次选择两个值、一个最大值和一个最小值,并将它们放在序列的开头和结尾,可以使选择排序的效率加倍。
http://www.Sina.com/http://www.Sina.com /
//排序voidswap(int*a,int* b ) {int tem=*a; *a=*b; *b=tem; }voidselectsort(int*arr,int n ) /下标int begin=0,end=n - 1,保存参与单次排序的第一个数和最后一个数; while(beginend )//保存最大值的下标int maxi=begin; //保存最小值下标int mini=begin; //找到最大值和最小值下标for (inti=begin; i=end; I ) if(arr[I]arr[mini] ) {mini=i; (if ) arr[I]ar
r[maxi]){maxi = i;}}//最小值放在序列开头swap(&arr[mini], &arr[begin]);//防止最大的数在begin位置被换走if (begin == maxi){maxi = mini;}//最大值放在序列结尾swap(&arr[maxi], &arr[end]);++begin;--end;}}时间复杂度:最坏情况:O(N^2)
最好情况:O(N^2)
空间复杂度:O(1)
思路:
左边大于右边交换一趟排下来最大的在右边
动图如下:
代码如下:
时间复杂度:最坏情况:O(N^2)
最好情况:O(N)
空间复杂度:O(1)
堆排可看之间这篇博文----->[堆排]
6.快速排序 5.1 hoare版本(左右指针法)思路:
1、选出一个key,一般是最左边或是最右边的。
2、定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
3、在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
4.此时key的左边都是小于key的数,key的右边都是大于key的数
5.将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时此部分已有序
单趟动图如下:
代码如下:
时间复杂度:
快速排序的过程类似于二叉树其高度为logN,每层约有N个数,如下图所示:
思路:
挖坑法思路与hoare版本(左右指针法)思路类似
1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)
后面的思路与hoare版本(左右指针法)思路类似在此处就不说了
单趟动图如下:
代码如下:
思路:
1、选出一个key,一般是最左边或是最右边的。
2、起始时,prev指针指向序列开头,cur指针指向prev+1。
3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。
经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作
//快速排序法 前后指针版本void QuickSort2(int* arr, int begin, int end){if (begin >= end)return;int cur = begin, prev = begin - 1;int keyi = end;while (cur != keyi){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}++cur;}swap(&arr[++prev],&arr[keyi]);keyi = prev;//[begin,keyi -1]keyi[keyi+1,end]QuickSort2(arr, begin, keyi - 1);QuickSort2(arr, keyi + 1, end);}