1.二叉树 堆排序 O(nlogn)
满二叉树: 叶子节点全部在同一个高度,且除了叶子节点外,所有的节点都有左右子节点
一棵高度为h的满二叉树,一共有 (2^h-1) 节点
平衡二叉树: 从任意一个节点开始,它的左右子树的高度差不会超过1
完全二叉树: 除了最后一层的叶子节点必须是从左到右
大栈堆: 任意一个根节点的值都要大于(或等于)左右子树的所有的值 (完全二叉树 从上到下 从大到小排列)
小栈堆: 任意一个根节点的值都要小于左右子树的值 (完全二叉树 从上到下 从小到大排列)
把完全二叉树调整成大栈堆(小栈堆),从最后一个根节点(len/2-1)开始往前调整 ,每次循环将当前节点的值和子节点的值按从大到小排列,循环调整根节点即可完成大栈堆数组.将大栈堆中最大值交换到最后一个 len-1 节点上,再len-1个元素再次调整为大栈堆,循环len-1次后,数组有序.
void swap(int *str1,int *str2){
int tmp = *str1;
*str1 = *str2;
*str2 = tmp;
}
void stackOneSort(int arr[],size_t len,int index){
int big = 0;
int data = arr[index];
for(;index<len;index = big){
big = index*2+1;
if(big>=len){
break;
}
if(big+1<len&&arr[big+1]>arr[big]){
big++;
}
if(data < arr[big]){
arr[index] = arr[big];
}else{
break;
}
}
arr[index] = data;
}
void stackBigSort(int arr[],size_t len){//把数组排列成从上到下 由大到小的 大栈堆数组
for(int i=len/2-1;i>=0;--i){
stackOneSort(arr,len,i);
}
}
void stackSort(int arr[],size_t len){//将第一个最大的数和最后一个数交换,再把剩下的len--个数排列成大栈堆
stackBigSort(arr,len);
for(int i=len-1;i>0;--i){
swap(&arr[0],&arr[i]);
stackOneSort(arr,i,0);
}
}
2.冒泡排序 O(n^2)
循环比较两个元素,较大值(往后移)冒出来,最后移到最后一个,下一次再循环比较,重复后移到倒数第二个;循环结束后,数组有序.
void SelectSort(int arr[],size_t len){
for(int i=len-1;i>0;i--){
int max = i;
bool isSort = false;
for(int j=0;j<=i;j++){
if(arr[max]<arr[j])
max = j;
isSort = true;
}
if(max != i){
swap(&arr[max],&arr[i]);
}
if(!isSort)break;
}
}
3.选择 O(n^2)
遍历数组 能够记录 最大值的下标
把最大值 和 最后一个元素 交换
遍历第二遍(不需要最后一个)数组 又能记录最大值的下标
把最大值 和 倒数第二个元素进行交换
循环 len-1 次
void SelectSort(int arr[],size_t len){//选择排序
for(int i=len-1;i>0;i--){
int max = i;
for(int j=0;j<i;j++){
if(arr[j]>arr[max]){
max = j;//记录最大值下标
}
}
if(max != i){
swap(&arr[i],&arr[max]);
}
}
}
4.鸡尾酒排序 O(n^2)
每次记录最大值和最小值的下标
最大值放末尾 最小值放开始
循环len/2次，数组有序
void cookSort(int arr[],size_t len){//鸡尾酒排序
for(int i=0;i<len/2;i++){
int max = i;
int min = i;
for(int j=i+1;j<len-i;j++){
if(arr[j]>arr[max]){
max = j;
}
if(arr[j]<arr[min]){
min = j;
}
}
if(max != i){
swap(&arr[i],&arr[max]);
}if(i == min){//注意如果当最小值是arr[i] 但是arr[i]已经被交换到arr[max]
min = max;
}if(min != len-i-1){
swap(&arr[len-i-1],&arr[min]);
}
}
}
5.直接插入 O(n^2)
1,19,9,8,7,4,16,0,3,2,7,20,15,5,6,17,11,14
假设现在是第i个元素 前面i-1个元素都有序 把arr[i]插入到前面i-1元素中使数组保持有序
void insertSort(int arr[],size_t len){
for(int i=1;i<len;i++){//把arr[i..len-1]这些元素插入到前面使用[0,i]有序
int data = arr[i];//要插入的值
int j = i-1;
for(;j>=0 && arr[j]>data;--j){//arr[j]比要插入的元素大 arr[j]要往后移一个位置
arr[j+1] = arr[j];
}
arr[j+1] = data;
}
}
6.折半插入(二分插入) O(n^2)
void binaryInsertSort(int arr[],size_t len){//折半插入
for(int i=1;i<len;i++){
int right = i-1;
int left = 0;
int data = arr[i];
while(left<=right){
int mid = (left+right)/2;
if(data < arr[mid]){
right = mid-1;
}else{
left = mid+1;
}
}
int j = i-1;
for(;j>right;j--){
arr[j+1] = arr[j];
}
arr[j+1] = data;
}
}
7.希尔插入排序 O(nlogn)
void shellSort(int arr[],size_t len){//三层循环希尔排序
int step = len/2;
while((step/=2)!=0){
for(int j=step;j<len;j++){
int data = arr[j];
int i = j-step;
for(;i>=0&&arr[i]>data;i-=step){
arr[i+step] = arr[i];
}
arr[i+step] = data;
}
}
}
8.归并排序 O(nlogn)
把两个有序的数组合并成一个有序的数组
void mergerArr(int arr[],size_t left,size_t right){ //合并数组的两部分，使数组的这两部分合并成一个有序的部分
int mid = (left+right)/2; //[left,mid] [mid+1,right]分别是有序的
//合并 [left,right]区间有序
int lds = mid+1-left;
int *pd = malloc(lds*sizeof(int));
for(int i=0;i<lds;i++){
pd[i] = arr[left+i];
}
int i = 0,j = mid+1;//i记录pa的下标 j记录arr[mid+1,right]下标
int k = left;
while(i<lds && j<=right){
if(pd[i] < arr[j]){
arr[k++] = pd[i++];
}else{
arr[k++] = arr[j++];
}
}
while(i<lds){
arr[k++] = pd[i++];
}
free(pd);
}
void merger(int arr[],size_t left,size_t right){//递归调用
if(left>=right){
return;
}
int mid = (left+right)/2;
if(mid-left>=1)
merger(arr,left,mid);//对[left,mid]区间进行排序
if(right-mid-1>=1)
merger(arr,mid+1,right);//对[mid+1,right]区间进行排序
mergerArr(arr,left,right);//把[left,mid],[mid+1,right]两部分有序的合并成一个整体有序的
}
void mergerSort(int arr[],size_t len){
merger(arr,0,len-1);
}
9.快速排序 O(nlogn)
记下左右两端的数序号[left,right],记录一个数比如说 data = arr[left] 序号
然后去left右边 找一个比 arr[left] 小的数放在左边
后又去right左边找一个比 arr[left] 大的数放在右边
循环直到最后
递归调用自己 执行每一个数
void quick(int arr[],int left,int right){
int data = arr[left];
int i = left;
int j = right;
while(i<j){
while(i<j&&arr[j]>data){--j;} //查找左边的小于等于data的数
arr[i] = arr[j]; //放置在左边i
while(i<j&&arr[i]<data){++i;} //查找右边大于等于data的数
arr[j] = arr[i]; //放置在右边j
}
arr[i] = data;
if(i-left>1){ //假如左边的数个数大于1,再次递归循环
quick(arr,left,i-1);
}
if(right-i>1){ //假如右边的数的个数>1,再次递归循环
quick(arr,i+1,right);
}
}
void quickSort(int arr[],size_t len){
quick(arr,0,len-1);
}
10.计数(桶)排序 O(n)
适用于在某个比较小的区间内数据密度比较大的情况下
例:arr[10]={1,3,2,5,6,9,8,7,4,0};
比对数组 [min,max] 区间 寻找数组内的数在这个区间内各个整数所占的数量
void countSort(int arr[],size_t len){
int min = arr[0];
int max = arr[0];
for(int i=0;i<len;i++){
if(arr[i]>max)
max = arr[i];
if(arr[i]<min)
min = arr[i];
}
printf("%d %d\n",min,max);
int size = max+1-min;
int *pc=calloc(size,sizeof(int));
for(int i=0;i<len;i++){//遍历数组,求得[min,max]上各个整数的 个数
pc[arr[i]-min]++;
}
int j = 0;
for(int i=0;i<size;i++){
while(pc[i]!=0){//pc[i]是arr[j]这个数的个数;
arr[j++] = i+min;
pc[i]--;
}
}
free(pc);
}
11.基数排序 O(n+r)
a.找最大值
b.计算最大值是一个几位数
个位
十个容器(队列)
十位
十个容器
百位
typedef int T;
typedef struct Queue{
T *m_vect;
size_t cap;
size_t size;
size_t index;
}Que;
void init(Que *que,size_t cap){
que->m_vect = calloc(cap,sizeof(T));
que->size = 0;
que->index = 0;
que->cap = cap;
}
void push(Que *que,T data){
if(que->size == que->cap){
que->m_vect = realloc(que->m_vect,sizeof(T)*(que->cap+4));
que->cap += 4;
}
que->m_vect[que->size++] = data;
}
T pop(Que *que){
--que->size;
return que->m_vect[que->index++];
}
void destroy(Que *que){
free(que->m_vect);
}
bool isEmpty(Que *que){
return que->size == 0;
}
void reset(Que *que){
que->size = 0;
que->index = 0;
}
void baseSort(int arr[],size_t len){
int max = arr[0];
for(int i=0;i<len;i++){
if(max < arr[i]){
max = arr[i];
}
}
Que ps[10];
for(int i=0;i<10;i++){
init(&ps[i],4);
}
int cnt = 0;
printf("%d \n",max);
while(max!=0){
max/=10;
cnt++;
}
for(int i=0;i<cnt;i++){
for(int j=0;j<len;j++){
int n = arr[j];
for(int k=0;k<i;k++){//按位数除10
n = n/10;
}
push(&ps[n%10],arr[j]);//按n%10放入相应的位置
}
int m =0;
for(int j=0;j<10;j++){
while(!isEmpty(&ps[j])){
arr[m++] = pop(&ps[j]);//弹出ps[j]里的数
}
reset(&ps[j]);//为max的下一个位,复位
}
}
for(int i=0;i<10;i++){
destroy(&ps[i]);
}
}
版权声明：本文为weixin_42397177原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。