No.35 我与代码的日常： 数据结构——排序

“排序”在我们日常生活中用得可谓很频繁了，例如：淘宝上价格排序，学生成绩排序，网站点击量排序。往往需要我们排序的数据有很多，我们也不可能人为地进行排序。因此，我们可以利用计算机，进行高效率的数据排序。

1.插入排序：

void InsertSort(int arr[], int size)
{
	int i = 0;
	for (i = 1; i < size; i++)
	{
		int tmp = arr[i];
		int j = 0;
		for (j = i - 1; j >= 0 && arr[j] > tmp; j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = tmp;
	}
}

2.希尔排序：

void InsretWithGap(int arr[], int size, int gap)
{
	int i = 0;
	for (i = gap; i < size; i++)
	{
		int key = arr[i];
		int j = 0;
		for (j = i - gap; j >= 0 && arr[j]>key; j -= gap)
		{
			arr[j + gap] = arr[j];
		}
		arr[j + gap] = key;
	}
}

void ShellSort(int arr[], int size)
{
	int gap = size; 
	while (1)
	{
		gap = gap / 3 + 1;
		InsretWithGap(arr, size, gap);
		if (gap == 1)
		{
			break;
		}
	}
}

3.选择排序:

void SelectSort(int arr[], int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		int m = 0;
		int j = 0;
		for (j = 0; j < size - i; j++)
		{
			if (arr[j]>arr[m])
			{
				m = j;
			}
		}
		Swap(arr + m, arr + size - i - 1);
	}
}

4.堆排序：

//向下调整，排升序建大堆
void AdjustDown(int arr[], int size, int r)
{
	int left = 2 * r + 1;
	int right = 2 * r + 2;
	if (left >= size)
	{
		return; //数组越界
	}
	int m = left;
	if (right<size && arr[right]>arr[left])
	{
		m = right;
	}
	if (arr[r] > arr[m])
	{
		return; //满足对的性质
	}
	Swap(arr + r, arr + m);
	AdjustDown(arr, size, m);
}

//先建堆
void CreatHeap(int arr[], int size)
{
	int i = 0;
	for (i = (size - 1 - 1) / 2; i >= 0; i--)
		//最后一个非叶子节点开始
	{
		AdjustDown(arr, size, i);
	}
}


void HeapSort(int arr[], int size)
{
	int i = 0;
	//先建堆
	CreatHeap(arr, size);
	for (i = 0; i < size; i++)
	{
		Swap(arr, arr + size - 1 - i);
		AdjustDown(arr, size - i - 1, 0);
	}
}

5.冒泡排序：

void BubbleSort(int arr[], int size)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < size; i++)
	{
		for (j = 0; j < size - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
				Swap(arr + j, arr + j + 1);
		}
	}
}

完整的测试代码如下：（测试环境为VS2013）

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

//插入排序
void InsertSort(int arr[], int size)
{
	int i = 0;
	for (i = 1; i < size; i++)
	{
		int tmp = arr[i];
		int j = 0;
		for (j = i - 1; j >= 0 && arr[j] > tmp; j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = tmp;
	}
}

//希尔排序
void InsretWithGap(int arr[], int size, int gap)
{
	int i = 0;
	for (i = gap; i < size; i++)
	{
		int key = arr[i];
		int j = 0;
		for (j = i - gap; j >= 0 && arr[j]>key; j -= gap)
		{
			arr[j + gap] = arr[j];
		}
		arr[j + gap] = key;
	}
}

void ShellSort(int arr[], int size)
{
	int gap = size; 
	while (1)
	{
		gap = gap / 3 + 1;
		InsretWithGap(arr, size, gap);
		if (gap == 1)
		{
			break;
		}
	}
}

//交换函数（选择排序会用到）
void Swap(int*a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//选择排序
void SelectSort(int arr[], int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		int m = 0;
		int j = 0;
		for (j = 0; j < size - i; j++)
		{
			if (arr[j]>arr[m])
			{
				m = j;
			}
		}
		Swap(arr + m, arr + size - i - 1);
	}
}

//堆排序
//向下调整，排升序建大堆
void AdjustDown(int arr[], int size, int r)
{
	int left = 2 * r + 1;
	int right = 2 * r + 2;
	if (left >= size)
	{
		return; //数组越界
	}
	int m = left;
	if (right<size && arr[right]>arr[left])
	{
		m = right;
	}
	if (arr[r] > arr[m])
	{
		return; //满足对的性质
	}
	Swap(arr + r, arr + m);
	AdjustDown(arr, size, m);
}

//先建堆
void CreatHeap(int arr[], int size)
{
	int i = 0;
	for (i = (size - 1 - 1) / 2; i >= 0; i--)
		//最后一个非叶子节点开始
	{
		AdjustDown(arr, size, i);
	}
}


void HeapSort(int arr[], int size)
{
	int i = 0;
	//先建堆
	CreatHeap(arr, size);
	for (i = 0; i < size; i++)
	{
		Swap(arr, arr + size - 1 - i);
		AdjustDown(arr, size - i - 1, 0);
	}
}

void BubbleSort(int arr[], int size)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < size; i++)
	{
		for (j = 0; j < size - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
				Swap(arr + j, arr + j + 1);
		}
	}
}

//打印函数
void Print(int arr[], int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 8, 5, 2, 9, -1, 0, 6 };
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("插入排序: ");
	InsertSort(arr, size);
	Print(arr, size);
	printf("希尔排序: ");
	ShellSort(arr, size);
	Print(arr, size);
	printf("选择排序: ");
	SelectSort(arr, size);
	Print(arr, size);
	printf("堆 排 序: ");
	HeapSort(arr, size);
	Print(arr, size);
	printf("冒泡排序: ");
	HeapSort(arr, size);
	Print(arr, size);
	system("pause");
	return 0;
}

结果如下：