基本排序算法

void bubble_sort(int* arr,int sz)
{
	int i = 0;
	int flag = 1;
	for (i = 0; i < sz-1; i++)
	{
		int j = 0;
 //一趟冒泡排序之后，数组中最大的元素就在数列的末尾
		for (j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])//如果左边的数比右边的数大，就交换
			{
				flag = 0;
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
		if (flag == 1)//如果已经有序，提前跳出循环
			break;
	}
}

//left=0 左边界
//right=length-1 右边界
void Quicksort(int* arr, int left, int right)
{
	if (left < right)
	{
		int l = left;
		int r = right;
	
		int base = arr[left];//基准数
		while (l < r)
		{
			while (l<r && arr[r]>=base)
			{
				r--;//从右向左找第一个小于base的数
			}
			if (l < r)
				arr[l] = arr[r];//右边的数小于base，就与arr[l]交换
			while (l < r && arr[l] <= base)
				l++;//从左向右找第一个大于base的数
			if (l < r)
				arr[r] = arr[l];//左边的数大于base，就与arr[r]交换
		}
		arr[l] = base;
		Quicksort(arr, left, r-1);//对左边的子数列按照同样的方法进行排序
		Quicksort(arr, r+1, right);//对右边的子数列按照同样的方法进行排序
	}
}

#define LENGTH(arr) (sizeof(arr)/sizeof(arr[0]))
void select_sort(int* arr, int n)
{
	int i, j, min;
	for (i = 0; i < n; i++)	
	{
		min = i;
		for (j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}
			//如果min！=i，则交换arr[i],arr[min]
			//保证arr[0]到arr[i]之间是有序的
			if (min != i)
			{
				int tmp = arr[min];
				arr[min] = arr[i];
				arr[i] = tmp;
			}
	}
}

//arr[] 待排序的数组
//n 数组长度
void Insert_sort(int arr[], int n)
{
	int i, j, k;
	//0~i-1为一个有序区间
	for (i = 1; i < n; i++)
	{
		//无序区的第一个数据为arr[i],为arr[i]在前面的有序区间内找一个合适的位置，将其插入
		for (j = i - 1; j >= 0; j--)
			if (arr[j] < arr[i])//如果有序区内有数比arr[i]小，就跳出循环，直接插入
				break;
		//找到了位置
		if (j != i - 1)
		{
			//比arr[i]大的数据往后移
			int temp = arr[i];
			for (k = i-1; k > j; k--)
				arr[k + 1] = arr[k];
			//将arr[i]放在合适的位置
			arr[k + 1] = temp;
		}
	}
}

//分组插入
// 假设数组为1，3，4，5，6，7，8
// 步长为2，组内相邻两个数下标的差为2
// 则被分为两组
// 一组是1，4，6，8
// 一组是3，5，7
//a 待排序的数组
//n 数组长度
void group_sort(int a[], int n, int i, int gap)
{
	int j;
	for (j = i + gap; j < n; j += gap)
	{

		//如果a[j]<a[j-gap](子列中两个相邻的元素),则寻找a[j]的位置，并将后面的数据后移
		if (a[j] < a[j - gap])
		{
			int tmp = a[j];
			int k = j - gap;
			while (k >= 0 && a[k] > tmp)
			{
				a[k + gap] = a[k];
				k -= gap;
			}
			a[k + gap] = tmp;
		}
	}
}
void shell_sort(int a[], int n)
{
	int i,  gap;
	//gap为步长，每次减小为原来的一半
	for (gap = n / 2; gap > 0; gap /= 2)
	{
		//共gap个组，对每一个组进行直接插入排序
		for (i = 0; i < gap; i++)
		{
			group_sort(a, n, i, gap);
		}
		int m = 0;
		for (m = 0; m < n; m++)
		{
			printf("%d ", a[m]);
		}
		printf("\n");
	}
}

int buckets[100000];
int arr[2000000];
void bucket_sort(int* a, int n, int max)
{
	int i, j;
	//计数
	for (i = 0; i < n; i++)
	{
		buckets[a[i]]++;
	}
	//排序
	for (i = 0, j = 0; i <= max; i++)
	{
		while ((buckets[i]--) > 0)
		{
			a[j++] = i;
		}
	}
}