总结并编写了部分常用的排序算法,包括前向、后向冒泡排序、简单选择排序、直接插入排序、希尔排序、堆排序、并归排序和快速排序。
具体的原理请参考《大话数据结构》。

#include<stdio.h>

//从前向后冒泡
void bubble(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

//从后向前冒泡
void bubble2(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = n - 1; j > i; j--)
		{
			if (arr[j - 1] > arr[j])
			{
				int temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
			}
		}
	}
}

//选择排序
void selectsort(int arr[], int n)
{
	for (int i = 0; i < n ; i++)
	{
		int index = i;
		for (int j = i + 1; j < n; j++)
		{
			if (arr[index] > arr[j])
				index = j;
		}
		if (i != index)
		{
			int temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}
}


//插入排序
void insertionsort(int arr[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = arr[i];
		while (i >= 0 && arr[i - 1] > temp)
		{
			arr[i] = arr[i - 1];
			i--;
		}
		arr[i] = temp;
	}
}

//希尔排序
void shellsort(int arr[], int n)
{
	int gap = n;
	int temp;
	int i, j;
	do
	{
		gap = gap / 2;
		for (i = gap; i < n; i++)
		{
			if (arr[i] < arr[i - gap])
			{
				temp = arr[i];
				for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
					arr[j + gap] = arr[j];
				arr[j + gap] = temp;
			}
		}
	} while (gap > 1);
}

int main()
{
	int arr[] = { 4,1,5,2,3,6,9,7,8 };
	//冒泡排序
	//bubble(arr, 9);
	//bubble2(arr, 9);
	//选择排序
	//selectsort(arr, 9);
	//插入排序
	//insertionsort(arr, 9);
	//希尔排序
	//shellsort(arr, 9);

	for (int i = 0; i < 9; i++)
		printf("%d ", arr[i]);

	return 0;
}
09-02 15:45