一、排序的概念及其运用
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 计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
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;
}
}
}
三、排序算法复杂度及稳定性分析
