蓝桥刷题note13（排序)

1.冒泡排序

适用场景：

数据量较小：适用于数据量较小的情况，例如数组长度在 10 以内。

优点

稳定性：冒泡排序是一种稳定的排序算法，相同元素的相对顺序不会改变。

缺点

时间复杂度高：平均和最坏时间复杂度为 O(n^2) ，效率较低。

不适用于大数据量：对于较大的数据量，排序时间会显著增加。

#include <stdio.h>
 #include<stdlib.h>
void swap(int *a,int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}
void pao_sort(int *arr,int length){
	for(int i=0;i<length-1;i++){
		for(int j=0;j<length-1-i;j++){
			if(arr[j]>arr[j+1]){
				swap(&arr[j],&arr[j+1]);
			}
		}
	}
}

int main(){
	int arr[5]={3,1,2,5,4};
	pao_sort(arr,5);
	for(int i=0;i<5;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}

 2.选择排序 

每次选择最小的元素排在第一位

缺点：

数据量较小：适用于数据量较小的情况，例如数组长度在 10 以内。

时间复杂度高：平均和最坏时间复杂度为 O(n^2) ，

#include <stdio.h>
 #include<stdlib.h>
void swap(int *a,int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}
void selection_sort(int *arr,int length){
	for(int i=0;i<length-1;i++){
	int min=i;
	for(int j=i+1;j<length;j++){
		if(arr[j]<arr[min]){
			min=j;
		}
	 }
	if(min!=i){
		swap(&arr[i],&arr[min]);
	 }
	}
}

int main(){
	int arr[5]={3,1,2,5,4};
	selection_sort(arr,5);
	for(int i=0;i<5;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}

3.归并排序 

将数组不断从中间拆分直至不可再分再按次序合并。

适用于大数据量、需要稳定排序的场景，尤其是链表排序和外部排序。

平均和最坏时间复杂度为 O(n log n)

#include <stdio.h>
 #include<stdlib.h>

void merge(int *arr,int left,int mid,int right){
	int n1=mid+1-left;
	int n2=right-mid;

    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

	for(int i=0;i<n1;i++){
		L[i]=arr[left+i];
	}
	for(int j=0;j<n2;j++){
		R[j]=arr[mid+1+j];
	}

	int i=0,j=0,k=left;
	while(i<n1&&j<n2){
		if(L[i]<=R[j]){
		arr[k]=L[i];
		i++;
		}
		else{
		arr[k]=R[j];
		j++;
		}
		k++;
	}
	while(i<n1){
		arr[k]=L[i];
		i++;
		k++;
	}
	while(j<n2){
		arr[k]=R[j];
		j++;
		k++;
    }
}

void merge_sort(int *arr,int left,int right){
	if(left<right){
		int mid=(left+right)/2;
	
	merge_sort(arr,left,mid);
	merge_sort(arr,mid+1,right);

	merge(arr,left,mid,right);
	}
}
int main(){
	int arr[5]={3,1,2,5,4};
	merge_sort(arr,0,4);
	for(int i=0;i<5;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}

 4.快速排序

设置一个参照数，比起小的排至其左边，大的排到右边。

平均时间复杂度为 O(n log n)

最坏时间复杂度为 O(n^2) ，当数组已经部分有序时，性能会下降。

#include <stdio.h>
 #include<stdlib.h>
 
void quick_sort(int *arr,int low,int high){
	if(low<high){
	int left=low;
	int right=high;
	int pivot=arr[low];
	while(left<right){
		while(arr[right]>pivot&&left<right){
			right--;
		}
		if(left<right){
			arr[left]=arr[right];
			left++;
		}
		while(arr[left]<pivot&&left<right){
			left++;
		}
		if(left<right){
			arr[right]=arr[left];
			right--;
		}
	}
	arr[left]=pivot;
	quick_sort(arr, low, left - 1);
    quick_sort(arr, left + 1, high);
	}
}
int main(){
	int arr[5]={3,1,2,5,4};
	quick_sort(arr,0,4);
	for(int i=0;i<5;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}