排序

1.冒泡排序

平均时间复杂度为O(n^2) 空间复杂度O(1)

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

int main(){
	int a[] = {1,6,3,7,0,2};
	int n = sizeof(a) / sizeof(int);
	for (int i = 0;i < n;++i){
		for(int j = 0;j < n - 1 -i;j++){
			if(a[j] > a[j+1]){
				//swap
				int t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
	return 0;
}

2.快速排序

平均时间复杂度 O(N*logN)

在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边，对左右两个分区重复以上步骤直到所有元素都是有序的。

#include <stdio.h>

void quick_sort(int* nums,int left,int right){
	if(left >= right)
		return;
	//选定参照
	int flag =  nums[left];
	int i = left;
	int j = right;

	while(i < j){
		//找比flag小的，直到找到
		while(i < j && nums[j] >= flag)
			--j;
		//找比flag大的，直到找到
		while(i < j && nums[i] <= flag)
			++i;
		
		//swap i,j
		if(i < j){
			int t = nums[i];
			nums[i] = nums[j];
			nums[j] = t;
		}
		
	}
	
	nums[left] = nums[i];
	nums[i] = flag;

	quick_sort(nums,left,i-1);
	quick_sort(nums,i+1,right);
	
}

int main(){
	int a[] = {1,0,8,3,5,2,6,4,5,6,1};
	int len = sizeof(a) / sizeof(int);
	quick_sort(a,0,len-1);
	for(int i = 0;i < len;++i)
		printf("%d ",a[i]);
	
	return 0;
}