【数据结构】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  
2.4 堆排序
 
详细情况请看堆排序
 
2.5 冒泡排序
 
//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i  
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 
		if (arr[begin1] 
			temp[i++] = arr[begin1++];
		}
		else
		{
			temp[i++] = arr[begin2++];
		}
	}
	while (begin1 
		temp[i++] = arr[begin1++];
	}
	while (begin2 
		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;
}

	int min = a[0], max = a[0];
	for (int i = 1; i