集齐7种排序算法召唤神猿

俗话说得好，连7种基本的排序算法都没学会，还想找女朋友？好吧，还是乖乖回去写排序吧。

排序有很多种。最常用的就这7种：插入排序，冒泡排序，选择排序，归并排序，桶排序，堆排序，快速排序。

插入排序：

#include "stdio.h"

#define ARRAYLEN 10

void sort(int* array, int len)
{
	int i = 0;
	for(i=1; i<len; i++)
	{
		int base = array[i];
		int j = i;
		for(j=i-1;j>=0;j--)
		{
			if(array[j] > base)
			{
				array[j+1] = array[j];
			}
			else
			{
				array[j+1] = base;
				break;
			}
		}
		if(j == -1)
		{
			array[0] = base;
		}
	}
}

int main(void)
{
	int array[ARRAYLEN] = {};
	int i = 0;
	for(i=0; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN);
	for(i=0; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

选择排序：

#include "stdio.h"

#define ARRAYLEN 10

void sort(int* array, int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		int j = 0;
		int min = i;
		for(j=i; j<len; j++)
		{
			if(array[min] > array[j])
			{
				min = j;
			}
		}
		if(min != j)
		{
			int item = array[min];
			array[min] = array[i];
			array[i] = item;
		}
	}
}

int main(void)
{
	int array[ARRAYLEN] = {};
	int i = 0;
	for(i=0; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN);
	for(i=0; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

冒泡排序：

#include "stdio.h"

#define ARRAYLEN 10

void sort(int* array, int len)
{
	int i = 0;
	int j = 0;
	for(i=len-1; i>0; i--)
	{
		for(j=0; j<i; j++)
		{
			if(array[j] > array[j+1])
			{
				int item = array[j];
				array[j] = array[j+1];
				array[j+1] = item;
			}
		}
	}
}

int main(void)
{
	int array[ARRAYLEN] = {};
	int i = 0;
	for(i=0; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN);
	for(i=0; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

归并排序：

#include "stdio.h"

#define ARRAYLEN 10

void merge_array(int* left, int len_left, int* right, int len_right, int* tmp)
{
	int i = 0;
	int j = 0;
	int k = 0;
	while(i<len_left && j<len_right)
	{
		if(left[i]< right[j])
		{
			tmp[k++] = left[i++];
		}
		else
		{
			tmp[k++] = right[j++];
		}
	}
	while(i < len_left)
	{
		tmp[k++] = left[i++];
	}
	while(j < len_right)
	{
		tmp[k++] = right[j++];
	}
	for(i=0;i<k;i++)
	{
		left[i] = tmp[i];
	}
}

void merge_sort(int *array, int start, int end, int* tmp)
{
	int middle = (start + end) / 2;
	if(end-start < 1)
	{
		return;
	}
	merge_sort(array, start, middle, tmp);
	merge_sort(array, middle+1, end, tmp);
	merge_array(&array[start], middle-start+1, &array[middle+1], end-middle, tmp);
}

void sort(int* array, int len)
{
	int tmp[ARRAYLEN] = {};
	merge_sort(array, 0, len-1, tmp);
}

int main(void)
{
	int array[ARRAYLEN] = {};
	int i = 0;
	for(i=0; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN);
	for(i=0; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

桶排序

#include "stdio.h"

#define ARRAYLEN 10

void sort(int* array, int max, int min, int len)
{
	int range[ARRAYLEN + 1] = {};
	int i = 0;
	for(i=0; i<len; i++)
	{
		range[array[i] - min]++;
	}
	int j = 0;
	for(i=0; i<max-min+1; i++)
	{
		while(range[i] != 0)
		{
			array[j++] = i+min;
			range[i]--;
		}
	}
}

int main(void)
{
	int array[ARRAYLEN] = {};
	int i = 0;
	for(i=0; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN, 1, ARRAYLEN);
	for(i=0; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

堆排序

#include "stdio.h"

#define ARRAYLEN 11

void heap_adjust(int* array, int id, int size)
{
	int lchild = id * 2;
	int rchild = lchild + 1;
	if(id > size/2)
	{
		return;
	}
	int max = id;
	if(lchild <= size && array[lchild] > array[max])
	{
		max = lchild;
	}
	if(rchild <= size && array[rchild] > array[max])
	{
		max = rchild;
	}
	if(max != id)
	{
		int item = array[id];
		array[id] = array[max];
		array[max] = item;
		heap_adjust(array, max, size);
	}
}

void build_heap(int* array, int len)
{
	int i = 1;
	for(i=len/2; i>0; i--)
	{
		heap_adjust(array, i, len);
	}
}

void sort(int* array, int len)
{
	int i=1;
	build_heap(array, len-1);
	for(i=len-1;i>0;i--)
	{
		int item = array[1];
		array[1] = array[i];
		array[i] = item;
		heap_adjust(array, 1, i-1);
	}
}

int main(void)
{
	int i = 0;
	int array[ARRAYLEN] = {};
	for(i=1; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN);
	for(i=1; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

快速排序

#include "stdio.h"

#define ARRAYLEN 10

void sort(int* array, int len)
{
	if(len < 2)
	{
		return;
	}
	int start = 0;
	int i = 0;
	int base = array[0];
	int position = 0;
	int j = len-1;
	while(i != j)
	{
		while(j!=i && array[j]>base)
		{
			j--;
		}
		if(i != j)
		{
			array[position] = array[j];
			position = j;
		}
		while(j!=i && array[i]<base)
		{
			i++;
		}
		if(i!=j)
		{
			array[position] = array[i];
			position = i;
		}
	}
	array[position] = base;
	sort(array, position+1);
	sort(&array[position+1], len-position-1);
}

int main(void)
{
	int array[ARRAYLEN] = {};
	int i = 0;
	for(i=0; i< ARRAYLEN; i++)
	{
		scanf("%d", &array[i]);
	}
	sort(array, ARRAYLEN);
	for(i=0; i< ARRAYLEN; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}