目录
排序的概念
1.直接插入排序
基本思想
代码实现
算法分析
2.希尔排序
基本思想
代码实现
算法分析
3.冒泡排序
基本思想
代码实现
算法分析
4.快速排序
基本思想
代码实现
算法分析
5.简单选择排序
基本思想
代码实现
算法分析
6.堆排序
基本思想
代码实现
算法分析
7.归并排序
基本思想
代码实现
算法分析
8.基数排序
基本思想
代码实现
算法分析
总结
排序的概念
排序：所谓排序，就是一串记录，按照某个关键字的大小，按照递增或者递减的顺序进行排列的操作。
稳定性：排序的稳定性，在排序前，有许多相同关键字的记录，他们是按照一定的次序排列的。在排序后，还能按照原先的次序进行排序，那么我们称这种排序算法是稳定的，否则是不稳定的。
内部排序：数据全部在内存中排序。
外部排序：数据元素过多，无法在内存中排序，需要通过内外存之间移动数据来进行排序。
相关算法：
1.直接插入排序
基本思想
直接插入排序是一种简单的插入排序，思想是把待排序的记录按照其关键值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完成，得到一个新的有序序列。
就比如说，我们现实生活中的玩扑克牌的方式就用了这种思想，我们每摸到一张牌的时候，原先手上的牌是排好序的，我们拿到这张新的牌，会插入到原先的有序序列，然后插入之后，我们新的序列又是有序的。之后，每次摸牌都按照这种方式，最终会得到一个完全有序的序列。
代码实现
有两种一种是直接插入，另一种是折半插入，区别在于查找插入位置的方法不同而已。
//1.直接插入排序
void InsertSort(int *a,int n){
int j;
for(int i=1;i<n;i++){
if(a[i]<a[i-1]){
int temp=a[i];
for( j=i-1;j>=0&&a[j]>temp;j--){
a[j+1]=a[j];
}//找到temp需要插入的位置，并将元素后以一个
//j等于
a[j+1]=temp;
}
}
}
1.2.折半插入排序
void InsertSort2(int *a,int n){
int i,j,low,high,mid;
for(i=1;i<n;i++){
int temp=a[i];
low=0;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(a[mid]>temp){
high=mid-1;
}else{
low=mid+1;
}
}//of while找到插入的位置
for(j=i-1;j>=high+1;j--){
a[j+1]=a[j];
}
a[high+1]=temp;
}
} 算法分析
首先，我们先分析算法的时间复杂度，要考虑算法的最好、最坏以及平均复杂度。最好的情况是当这个数组已经有序或者接近有序的情况下，我们只需要进行比较，不需要移动元素，最好时间复杂度为O(N)。而最坏的情况是，这个数组是完全逆序的时候，我们每次比较后，都要移动大量的元素，最坏时间复杂度为O(N2)**，平均复杂度为**O(N^2)。
那么，这个算法的空间复杂度为O(1)，因为只需要使用常量级别的空间。
最后，这个算法是否稳定，答案是稳定的。因为每次是从后往前依次比较，不会改变原先的次序，移动的过程中也是一个一个进行移动的。
2.希尔排序
基本思想
希尔排序也是插入排序中的一种，因为其本质就是使用了插入排序，我们从插入排序的结论中可以得出，越接近有序的数组使用插入排序的效率越高。
希尔排序的思想，就是使一个数组先部分有序，最后在全局有序。那么如何实现部分有序呢，我们可以对数组的元素按照某种规律进行分组，分组后，对组内的记录进行排序，如何重复进行分组和排序，当最终每组的成员只剩一个时，在进行排序的时候，就是使用了插入排序。
代码实现
我们定义了一个d变量，这个变量是用来进行分组的，当d大于0的时候，每次排序其实都是在预排序，也就是对分组内的成员进行排序，d是间隔，也就是将i，i+d，i+2*d...依次进行排序，之后，d/2或者d/3+1，按照某种规律，最终d=1的时候，在进行排序，就是进行了一次直接插入排序。
//2.希尔排序
void shellSort(int *a,int n){
int i,j,d;
for(d=n/2;d>=1;d=d/2){//分成不同的趟数，第一趟分割d=n/2
for(i=d;i<n;i++){//对每一堂的每个小组排序
if(a[i]<a[i-d]){
int temp=a[i];
for(j=i-d;j>=0&&a[j]>temp;j=j-d){
a[j+d]=a[j];
}
a[j+d]=temp;
}//of if
}//of for2
}//of for1
}算法分析
希尔排序的时间复杂度是一个复杂的问题，在Kunth所著的《计算机程序设计技巧》第3卷中，利用大量的实验统计资料得出，平均复杂度为O(N^1.25)到O(1.6 * N^1.25)。这里的就暂且不讨论该结果具体得出的方式。
希尔排序是否是稳定的算法呢？答案是不稳定的，因为我们在预排序的过程中，我们会进行大量的跳动式的移动元素的值，因此会导致不能按照原先的序列进行排序。
希尔排序中的d是如何取值的呢？当成Shell，也就是该算法的原作者，提出取d= d/2，然后向下取整，直到d=1时。后来Kunth提出取d= d/3 + 1 ，d/3向下取整的方式，直到gap=1时。这两种方式没有说哪个好，哪个坏，因此，使用其中一个即可。
3.冒泡排序
基本思想
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。如果遍历一遍数组，发现没有进行交换，故该数组已经有序，就不需要再进行排序。
代码实现
该排序算法的代码实现也很简单，每趟排序，遍历一遍数组，两两比较，每一趟会将最小的值放在第一位。如果该趟排序没有元素交换，则不需要再进行排序了。
//3.冒泡排序
void BubbleSort(int *a,int n){
for(int i=0;i<n;i++){//总共要冒n躺
for(int j=0;j<n-i;j++){//每一趟比较前n-i个元素
if(a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}算法分析
时间复杂度，当元素为逆序时，需要进行n-1趟排序，而每趟需要比较n-1次。故最坏时间复杂度为O(N^2)。当元素为有序时，第一趟后，发现不需要交换元素，则只需要进行n-1次比较。故最好时间复杂度为O(N)。
空间也是仅使用了常数个辅助单元，故空间复杂度为O(1)。
冒泡排序是一种稳定的算法。
4.快速排序
基本思想
快速排序是Hoare于1962年提出的一种以二叉树结构的交换排序。
其本质是基于分治法实现的，基本思想是任取待排序元素序列中的某个元素作为基准，按照该排序码将待排序集合分割成两子序列，左子序列的所有元素均小于基准值，右子序列均大于基准值。然后左右子序列重复该操作，知道该序列有序为止。
代码实现
关于快速排序，其实c语言的<stdlib>库中自带快排函数qsort()，可以直接用，详情请看：
C语言学习--快速排序函数sqort()-CSDN博客
- 先将选定的基准值(最左边)直接取出，然后留下一个坑，
- 当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位，
- 然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位，
- 重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。
- 之后也是以基准值为界限，递归排序基准值左右区间。
//4.快速排序
// 挖坑法
int PartSort(int* a, int begin, int end){
int key = a[begin];
int piti = begin;
while (begin < end){
// 右边找小，填到左边的坑里面去。这个位置形成新的坑
while (begin < end && a[end] >= key){
--end;
}
a[piti] = a[end];
piti = end;
// 左边找大，填到右边的坑里面去。这个位置形成新的坑
while (begin < end && a[begin] <= key){
++begin;
}
a[piti] = a[begin];
piti = begin;
}
a[piti] = key;
return piti;
}
// 快速排序递归实现
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PartSort(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}算法分析
快速排序整体的综合性能与使用场景都是比较好的，所以才能称为快速排序。时间复杂度在优化后，基本上能达到O(N*logN)，且优化后，优势更加明显。
空间复杂度，因为使用了递归，导致空间复杂度为O(logN)。
算法是不稳定的。
5.简单选择排序
基本思想
就是每一次从待排序的数据元素中选择最小或者最大的元素，放在序列的起始位置，直到全部排序完毕。
代码实现
//5.简单选择排序
void SelectSort(int *a,int n){
for(int i=0;i<n-1;i++){//n-1躺，每一趟找一个最小值放到最前面
int min=i;//记录最小值所在的下标便于交换位置
for(int j=i+1;j<n;j++){
if(a[j]<a[min]){
min=j;
}
}//最小值所在下标min
int temp=a[min];
a[min]=a[i];
a[i]=temp;//把每趟的最小值已到了最前面来
}
}每次找到最小（最大）的值，记录当前的位置，并且与开始位置进行交换。然后重复进行该操作，直到集合中只剩一个元素为止。
算法分析
简单选择排序是比较简单的一种，但是效率并不高，无论是什么情况，算法时间复杂度都为O(N^2)，因此，实际中很少使用。
空间复杂度为O(1)，仅使用了常量级别的空间。
直接选择排序是否是稳定的算法呢？答案是不稳定的，在交换的过程中，可能会导致相对次序进行改变。比如，表L={2,2,1}，经过第一趟排序后，结果为L={1,2,2}，显示已经和原先的次序不一致，故该排序算法是不稳定的。
6.堆排序
后面三种，堆排序，归并排序，和基数排序不太好实现，我觉得理解原理就可以了；
基本思想
在了解堆排序之前，首先要知道堆这个数据结构。
堆是一颗完全二叉树，满足根节点大于或者小于左右孩子结点。堆可以分为大根堆和小根堆。大根堆的最大元素存放在根结点，任意一颗非根节点的值小于等于其双亲结点的值。而小根堆与大根堆恰好相反，小根堆的根元素为最小。
大根堆可以存放在一个数组中，节点下标i，对应的左右孩子分别是：2*i，2*i+1
那么，堆排序的思想很简单，首先在排序前，将待排序的数组构建成为一个堆，以大根堆为例，将堆顶元素与堆底元素进行交换，然后继续将堆顶元素进行向下调整，然后保持大根堆的特性。因为对顶元素永远是当前堆中最大的一个，将其放在最后，就相当于把最大元素放在了数组的最后，再将堆的范围缩小，因此大根堆排序后的结果为升序。
代码实现
//6.堆排序
void swap(int* p1, int* p2){
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 堆排序
// 向下取整
void AdjustDwon(int* a, int n, int root){
int child = root * 2 + 1;
while (child < n){
if (child + 1 < n && a[child + 1] > a[child]){
child++;
}
if (a[child] > a[root]){
swap(&a[child], &a[root]);
root = child;
child = root * 2 + 1;
}
else{
break;
}
}
}
void HeapSort(int* a, int n){
// 建堆方式2：O(N)
for (int i = (n-2) / 2; i >= 0; --i){
AdjustDwon(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0){
swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
--end;
}
}
算法分析
堆排序是一种效率很高的排序，通过使用堆的数据结构来进行排序，时间复杂度为O(N*logN)，建堆的时间为O(N)，然后有n-1次向下调整操作，每次调整的时间复杂度与高度有关，而h=log2n + 1，故时间复杂度为O(N*logN)。
空间也是仅使用了常数个辅助单元，故空间复杂的为O(1)。
堆排序是否是稳定的算法呢？答案是不稳定的，在进行筛选的过程中，可能把后面相同的元素调整到前面来。
7.归并排序
基本思想
归并排序是建立在归并操作上的一种有效的排序算法，该算法采用的是分治法。其思想就是将序列分成n个子序列，再使用子序列有序，之后，将其合并为一个新的有序表，如果两个有序表合并为一个有序表，称为二路归并。
代码实现
//7.归并排序
void _MergeSort(int* a, int begin, int end, int* tmp){
int mid = (begin + end) / 2;
// [begin, mid] [mid+1, end] 分治递归，让子区间有序
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//归并 [begin, mid] [mid+1, end]
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin1;
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);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}算法分析
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
每趟归并的时间为O(N)，并且需要log2N趟归并，所以时间复杂度为O(N*logN)。
二路归并排序不会改变相同关键字记录的相对次序，因此是一种稳定的算法。
8.基数排序
基本思想
- 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
- 这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤
注意：基数排序中不能出现负数！！！
代码实现
//8.基数排序
//基数排序
void RadixSort(int* arr, int n){
//max为数组中最大值
int max = arr[0];
int base = 1;
//找出数组中的最大值
for (int i = 0; i < n; i++){
if (arr[i] > max){
max = arr[i];
}
}
//循环结束max就是数组最大值
//临时存放数组元素的空间
int* tmp = (int*)malloc(sizeof(int)*n);
//循环次数为最大数的位数
while (max / base > 0){
//定义十个桶，桶里面装的不是数据本身，而是每一轮排序对应（十、白、千...）位的个数
//统计每个桶里面装几个数
int bucket[10] = { 0 };
for (int i = 0; i < n; i++){
//arr[i] / base % 10可以取到个位、十位、百位对应的数字
bucket[arr[i] / base % 10]++;
}
//循环结束就已经统计好了本轮每个桶里面应该装几个数
//将桶里面的元素依次累加起来，就可以知道元素存放在临时数组中的位置
for (int i = 1; i < 10; i++){
bucket[i] += bucket[i - 1];
}
//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置
//开始放数到临时数组tmp
for (int i = n - 1; i >= 0; i--){
tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
bucket[arr[i] / base % 10]--;
}
//不能从前往后放，因为这样会导致十位排好了个位又乱了，百位排好了十位又乱了
/*for (int i = 0; i < n; i++)
{
tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
bucket[arr[i] / base % 10]--;
}*/
//把临时数组里面的数拷贝回去
for (int i = 0; i < n; i++){
arr[i] = tmp[i];
}
base *= 10;
}
free(tmp);
}
算法分析
基数排序的时间复杂度跟基数选取有关，平均复杂度为O(k·n)。基数排序为稳定排序算法。
总结
![[MySQL]数据库基础](https://img-blog.csdnimg.cn/direct/64a213090e444564a75adf2f49c4bc68.png)
![[数据结构]堆](https://img-blog.csdnimg.cn/direct/e8ae4653849d4d6caa7457a0d9908358.png)
