做羊水亲子鉴定网站/电子商务网站建设

目录

1.冒泡法

2.冒泡法改进版

3.插入排序

4.希尔排序

5.选择排序

6.选择排序改进版

7.快速排序(利用递归)

7.归并排序(利用递归)

8.二分查找

---

 

1.冒泡法

时间复杂度：O(N^2)

//冒泡
void popSort(int * arr,int num)
{for(int i =0;i<num-1;i++){for(int j = 0;j<num-1-i;j++){if(arr[j]>arr[j+1]){arr[j]^=arr[j+1];arr[j+1]^=arr[j];arr[j]^=arr[j+1];}}}
}

2.冒泡法改进版

（若上一次已经有序，那么就不用继续排序了,简称“序而不排”）

时间复杂度：O(N^2)

void popSort2(int * arr,int num)
{int flag;for(int i =0;i<num-1;i++){flag = 1;for(int j = 0;j<num-1-i;j++){if(arr[j]>arr[j+1]){arr[j]^=arr[j+1];arr[j+1]^=arr[j];arr[j]^=arr[j+1];flag = 0;}}if(flag ==1)break;}
}

 

3.插入排序

时间复杂度：O(N^2)

void insertSort(int * arr,int num)
{int i ,j ,t;for(i =1;i<num;i++){t = arr[i];for(j = i ;t<arr[j-1]&& j-1>-1    ;j-- ){arr[j] = arr[j-1];}arr[j] =t;}
}

 

4.希尔排序

时间复杂度：O(N^1.3)

void shellSort(int * arr,int num)
{int d = num/2;while(d>=1){int i,j,t;for(i = d;i<num;i++){t = arr[i];for(j = i; t<arr[j-d]&&j-d>-1;j-=d){arr[j] = arr[j-d];}arr[j] = t;}d =d /2;}
}

 

5.选择排序

时间复杂度：O(N^2)

void selectSort(int * arr,int num)
{for(int i = 0;i<num-1;i++){for(int j = i+1; j<num;j++){if(arr[j]<arr[i]){arr[j] ^= arr[i];arr[i] ^= arr[j];arr[j] ^= arr[i];}}}
}

 

6.选择排序改进版

（“比而不换”）

时间复杂度：O(N^2)

void selectSort2(int * arr,int num)
{int idx ;for(int i = 0;i<num-1;i++){idx = i;for(int j = i+1; j<num;j++){if(arr[idx]>arr[j]){idx = j;}}if(idx !=  i){arr[idx] ^= arr[i];arr[i] ^= arr[idx];arr[idx] ^= arr[i];}}
}

 

7.快速排序(利用递归)

时间复杂度：O(N*LogN)

void quickSort(int * arr,int left , int right)
{if(left<right){int lh = left, hh = right,t = arr[left];while(lh<hh){while(lh < hh && arr[hh] >= t)hh--;arr[lh] = arr[hh];while(lh<hh && arr[lh] <= t)lh++;arr[hh] = arr[lh];}arr[hh]  = t;quickSort(arr,left,hh-1);quickSort(arr,hh+1,right);}
}

 

7.归并排序(利用递归)

时间复杂度：O(N*LogN)

需要额外的空间，称为外排序

//(a和b数组输入时有序)-2个数组
void mergeArr1(int * a, int an,int * b, int bn,int * c, int cn)
{int i = 0, j = 0,k = 0;while(i !=  an && j != bn){if(a[i]<b[j]){c[k++] = a[i++];}else{c[k++] = b[j++];}}if(i == an)while(j != bn)c[k++] = b[j++];elsewhile(i != an)c[k++] = a[i++];
}//(a数组包含2个有序数组)-1个数组
void mergeArr2(int * a ,int * c, int start, int mid, int end)
{int i = start, j = mid+1, k = start;while(i !=  mid+1 && j != end+1){if(a[i] < a[j])c[k++] = a[i++];elsec[k++] = a[j++];}if(i == mid +1)while(j != end+1 )c[k++] = a[j++];elsewhile(i != mid +1)c[k++] = a[i++];while(start<=end){a[start] = c[start];start++;}
}//归并排序
void mergeSort(int*arr, int *tmp,int start, int end)
{if(start<end){int mid = (start +end)/2;mergeSort(arr,tmp,start,mid);mergeSort(arr,tmp,mid+1,end);mergeArr2(arr,tmp,start,mid,end);}
}

 

8.二分查找

//二分查找(迭代版本)
bool binSearch(int * a, int low, int high, int find)
{int mid ;while(low<=high){mid = (low+high)/2;if(a[mid] > find)high = mid-1;else if(a[mid]<find)low = mid +1;elsereturn true;}return false;
}//递归版本
bool binSearchTraverse(int * a, int low, int high, int find)
{int mid ;while(low<=high){mid = (low+high)/2;if(a[mid] > find)return binSearchTraverse(a,low,mid-1,find);else if(a[mid]<find)return binSearchTraverse(a,mid+1,high,find);elsereturn true;}return false;
}