目录
一.排序的基本概念
1.1 排序的概念
1.2 常见的排序算法
二.常见排序算法的实现
2.1 插入排序（直接）
1.基本思想
2.直接插入排序的特性
3.代码实现
2.2 希尔排序
1.基本思想
2.希尔插入排序的特性
3.代码实现
2.3 选择排序
1.基本思想
2.选择排序的特性
3.代码实现
2.4 堆排序
1.基本思想
2.选择排序的特性
3.代码实现
2.5 冒泡排序
1.基本思想
2.选择排序的特性
3.代码实现
2.6 快速排序
1.基本思想
2.选择排序的特性
3.代码实现
2.7 归并排序
1.基本思想
2.选择排序的特性
3.代码实现
三.排序算法复杂度及稳定性分析
一.排序的基本概念
1.1 排序的概念
1.排序：使一串记录，按照其中的某个或者某些关键字的大小，递增或递减的排列起来的操作。
2.稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。（个人理解：如果排序前两个相等的元素的相对位置是正确的，那么排序后它们的相对位置仍然保持不变。换句话说，稳定性关注的是相等元素的相对顺序，而不是所有元素的绝对位置。）
3.内部排序：数据元素全部放在内存中的排序。
4.外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。
（内存指电脑的运行内存，外存指硬盘内存。内存排序就是直接在程序中存储数据并排序，外存排序可以是把每部分排好的数据和一个文本文档进行交互）
1.2 常见的排序算法
二.常见排序算法的实现
2.1 插入排序（直接）
1.基本思想
以递增顺序为例，当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，大于array[i], 则后移，否则找到插入位置即将array[i]插入。
2.直接插入排序的特性
1.元素集合越接近有序，直接插入排序算法的时间效率越高。
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：稳定
3.代码实现
//插入排序代码实现，*a为数组名，n为数组元素个数
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = tmp;
}
}2.2 希尔排序
1.基本思想
按间隔gap分组排序，第 1 组为从第 1 个数据开始，每隔gap取一个数据；
第 2 组为从第 2 个数据开始，每隔gap取一个数据；
.......
第 k 组为从第 k 个数据开始，每隔gap取一个数据，（k<=gap）
将上面1~k组分别进行直接插入排序。
第二轮，减小gap值，重复上述步骤。
直到gap为1，排序完成
以上图排序为例，第一趟，第1组9，4；第2组1，8；第3组2，6；第四组5，3；第五组7，5
gap=5 排序完为，第1组4，9；第2组1，8；第3组2，6；第四组3，5；第五组5，7
即：4，1，2，3，5，9，8，6，5，7
第二趟，第1组4，2，5，8，5；第2组1，3，9，6，7
gap=2 排序完为，第1组2，4，5，5，8；第2组1，3，6，7，9
即：2，1，4，3，5，6，5，7，8，9
第三趟，gap=1，排序完为1，2，3，4，5，5，6，7，8，9
2.希尔插入排序的特性
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比，对于大量数据来看，希尔排序速度远大于直接插入排序。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。我们的希尔排序按照Knuth提出的 gap = [gap/3]+1 计算。(+1是为了最后一次排序gap=1)。此时时间复杂度为O(n^1.3)
4.稳定性：不稳定。
3.代码实现
//插入排序代码实现，a为数组名，n为数组元素个数
void ShellSort(int* a, int n)
{
int gap = n;
while(gap > 1)
{
//+1保证最后一个gap是1，gap>1是预排序，gap=1是插入排序
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
}2.3 选择排序
1.基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
改进：每次从待排数据中同时选出最大与最小的数据下标，与数组头begin和数组尾end互换，再将begin++，end--。
2.选择排序的特性
1.直接选择排序容易理解，但是效率不好。实际中很少使用。
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：不稳定
3.代码实现
//选择排序O(N^2)，其中Swap函数功能为交换两个变量的值
void SelectSort(int* a, int n)
{
int begin = 0, end = n-1;
while(begin < end)
{
int mini = begin;
int maxi = end;
for (int i = begin; i < end; i++)
{
if (a[i] < a[mini])
mini = i;
if (a[i] > a[maxi])
maxi = i;
}
Swap(&a[begin], &a[mini]);
if (maxi == begin) //防止换错
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}2.4 堆排序
1.基本思想
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
2.选择排序的特性
1.堆排序使用堆来选数，效率高很多
2.时间复杂度：O(N*logN)，以2为底
3.空间复杂度：O(1)
4.稳定性：不稳定
3.代码实现
//堆排序
//交换函数
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
//降序，建小堆
//升序，建大堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
//printf("%d ", a[0]);
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}2.5 冒泡排序
1.基本思想
依次比较第一、二个元素，一大二小则交换，否则不变；
交换完再比较第二、三个元素，二大三小则交换，否则不变；
直到比完最后 n-1 和 n 两个数，完成一轮交换。此时最大的数在n位置。
再从第一个比到第n-1个数，完成第二轮交换，此时第二大的数在n-1位置。
比较n轮，完成排序
2.选择排序的特性
1.冒泡排序是一种非常容易理解的排序
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：稳定
3.代码实现
//冒泡排序:O(N^2) a为数组名，n为数据个数
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
int flag = 0;
for (int i = 1; i < n-j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
break;
}
}2.6 快速排序
1.基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
（1）hoare版本
（2）挖坑法
（3）前后指针法
2.选择排序的特性
1.快速排序整体的综合性能和使用场景都是比较好的，所以叫快速排序
2.时间复杂度O(N*logN)
3.空间复杂度：O(logN)
4.稳定性：不稳定
3.代码实现
1.hoare版本
// 快速排序hoare版本
void PartSort1(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
while(a[end] >= a[keyi] && begin < end)
end--;
while(a[begin] <= a[keyi] && begin < end)
begin++;
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;
PartSort1(a, left, keyi - 1);
PartSort1(a, keyi + 1, right);
}2. 挖坑法
// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = a[left];
int begin = left, end = right;
while (begin < end)
{
while (a[end] > keyi && begin < end)
end--;
a[begin] = a[end];
while (a[begin] < keyi && begin < end)
begin++;
a[end] = a[begin];
}
a[begin] = keyi;
int midi = begin;
PartSort2(a, left, midi - 1);
PartSort2(a, midi + 1, right);
}3. 前后指针法
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}2.7 归并排序
1.基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
2.选择排序的特性
1.归并排序的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排问题。
2.时间复杂度：O(N*logN)
3.空间复杂度：O(N)
4.稳定性：稳定
3.代码实现
//归并排序:O(N^logN) 空间复杂度：O(N)
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
_MergeSort(a, tmp, begin1, end1);
_MergeSort(a, tmp, begin2, end2);
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//循环归并
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail\n");
return;
}
//_MergeSort(a, tmp, 0, n - 1);
int gap = 1;
while (gap < n)
{
for (int i = 0,k = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//第二组都越界不存在，这一组就不需要归并了
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
//第二组begin2没越界，end2越界了，需要修正一下，继续归并
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[j++] = a[begin1++];
else
tmp[j++] = a[begin2++];
}
while (begin1 <= end1)
tmp[j++] = a[begin1++];
while (begin2 <= end2)
tmp[j++] = a[begin2++];
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}三.排序算法复杂度及稳定性分析
