Insertion Sort and Merge Sort
不想努力的小白同学 人气:0Insertion Sort(插入排序)
思路:for 循环遍历数组中的每一个数
用while将每次遍历到的数于左侧的数进行对比,将小的排到左边
void InsertionSort(int*A, int n){ int key,i=0,p; for(p=0;p<n;p++){ key=A[p]; i=p-1; while(i>=0 && A[i]>key){ A[i+1]=A[i]; i=i-1; } A[i+1]=key; } }
中规中矩的排序方法
时间复杂度:
Best-case Running time : O(n)(数组已经被排好序的情况)
Worst-case Running Time : O(n^2)
Average Running Time : O(n^2)
从时间复杂度来看,处理少量数据还可以。当数据量较为庞大时,速度就很慢了
Merge Sort
思路:利用递归将数组分成两个相同大小的部分,直至长度为1
然后利用merge函数分别对每个部分进行排序
最后重新放在一起
void Merge(long int*A,long int left,long int center,long int right){ long int i1=left,i2=center+1,i=0,j; long int B[100000]; long int length =sizeof(B)/sizeof(B[0]); //比较左右两侧的大小,然后将小的的放入数组B while (i1<=center && i2<=right) { if(A[i1]>A[i2]){ B[i++]=A[i2++]; }else{ B[i++]=A[i1++]; } } //将左侧或者右侧剩余的数以此放入数组B中 for(;i1<=center;i1++){ B[i++]=A[i1]; } for(;i2<=right;i2++){ B[i++]=A[i2]; } //将数组B中排好序的值赋给A //由于每调用一次函数,B数组都会重新创建,因此B从0开始,A从left开始 for(j=0,i=left;j<=right-left;j++,i++){ A[i]=B[j]; } } void MergerSort(long int*A,long int left,long int right){ long int center=0; if(left>=right){ return ; } center=(left+right)/2; //这种先进行第一个递归,直至最后,没进行一次就相当于建立一层平台,当进行完后再返回上一层,执行下一个语句 MergerSort(A,left,center); MergerSort(A,center+1,right); Merge(A,left,center,right); }
这个就是merge sort 的排序过程:
个人觉得递归部分的代码不是很好理解,其余部分都还可以
时间复杂度:
加载全部内容