【数据结构】12.排序

一、排序的概念及其运用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 排序的应用

1.3 常见的排序算法

二、常见排序算法的实现

2.1 插入排序

详细的讲解请看插入排序

2.2 希尔排序

详细的讲解请看希尔排序

2.3 选择排序

//选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		// 选出最小值和最大值的位置
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}

			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}

		Swap(&arr[begin], &arr[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap(&arr[end], &arr[maxi]);
		++begin;
		--end;
	}
}

2.4 堆排序

详细情况请看堆排序

2.5 冒泡排序

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				exchange = 1;
				swap(&arr[j], &arr[j + 1]);
			}
		}
		if (!exchange)
		{
			break;
		}
	}
}

2.6 快速排序

详细请看快速排序

2.7 归并排序

1945年，约翰·冯·诺依曼（John von Neumann）发明了归并排序，这是典型的分治算法的应用。

2.7.1归并排序的思路

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.7.2 归并排序的实现

void _MergeSort(int* arr, int left, int right, int* temp)
{
	if (left == right)
	{
		return;
	}
	int mid = (left + right) / 2;
	//[left,mid][mid+1,right]
	_MergeSort(arr, left, mid, temp);
	_MergeSort(arr, mid+1,right, temp);

	// 归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	// 依次比较，取小的尾插tmp数组
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			temp[i++] = arr[begin1++];
		}
		else
		{
			temp[i++] = arr[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		temp[i++] = arr[begin1++];
	}

	while (begin2 <= end2)
	{
		temp[i++] = arr[begin2++];
	}

	memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1));
}


//归并排序
void MergeSort(int* arr, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("malloc fail!");
		return;
	}
	_MergeSort(arr, 0, n - 1, temp);
	free(temp);
	temp = NULL;
}

2.8 非比较排序

2.8.1 计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
   

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}

	memset(count, 0, sizeof(int) * range);

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

三、排序算法复杂度及稳定性分析