1、排序的概念及其运用
1.1 排序的概念
排序： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性： 若经过排序，这些记录的序列的相对次序保持不变，即在原序列中，r[i] = r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序： 数据元素全部放在内存中的排序。 外部排序： 数据元素太多不能同时放在内存中，根据排序过程的要求在内存外面的排序。（例如归并排序）
1.2常见的排序算法
- 插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 归并排序
- 计数排序（非比较排序）
1.3排序算法的接口
排序 OJ(可使用各种排序跑这个OJ) : 排序数组
代码语言：javascript复制#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void print(int arr[], int n);
// 插入排序
void InsertSort(int arr[], int n);
// 希尔排序
void ShellSort(int arr[], int n);
// 选择排序
void SelectSort(int arr[], int n);
// 堆排序
void AdjustDown(int arr[], int n, int root);
void HeapSort(int arr[], int n);
// 冒泡排序
void BubbleSort(int* a, int n);
// 快速排序递归实现
//三数取中函数
int GetMidIndex(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
// 归并排序递归实现
void MergeSort(int* a, int n);
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);
// 计数排序
void CountSort(int* a, int n);1.4测试算法接口
代码语言：javascript复制#include "sort.h"
// 测试排序的性能对比
void TestOP()
{
srand((unsigned int)time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%dn", end1 - begin1);
printf("ShellSort:%dn", end2 - begin2);
printf("SelectSort:%dn", end3 - begin3);
printf("HeapSort:%dn", end4 - begin4);
printf("QuickSort:%dn", end5 - begin5);
printf("MergeSort:%dn", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}附：Swap接口（使用异或的方法实现）
代码语言：javascript复制void Swap(int* a, int* b)
{
if(*a == *b)//这个条件要加，因为如果两个数相等，会变成0
return;
*a ^= *b;
*b ^= *a;
*a ^= *b;
}优点： 无需开辟临时变量，且不会发生溢出。
2、排序算法的实现
1、插入排序
基本思想： 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 实际中我们玩扑克牌时，就用了插入排序的思想。 直接插入排序： 当插入第 i (i >= 1)个元素时，前面的 array[0], array[1],…,array[i - 1] 已经排好序，此时用 array[i] 的排序码与 array[i - 1],array[i - 2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。 直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
代码实现：
代码语言：javascript复制void InsertSort(int* arr, int n)
{
for(int i = 0; i < n - 1; i)
{
int end = i;
int tmp = arr[end 1];
while(end >= 0)
{
if(arr[end] > tmp)
{
arr[end 1] = arr[end];
--end;
}
else
break;
}
arr[end 1] = tmp;
}
}2、⏯ 希尔排序( 缩小增量排序 )
希尔排序的由来： 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
在以前排序算法不多的时候，科学家们想着如何优化时间复杂度… 这时希尔想到，插入排序最坏的情况是 O(N^2) ，是在序列逆序的情况下，以目标排升序为例，最大的数字在最前面，那么要是将插入进行分组会不会交换的更快？答案是确实是快了！ 因为将插入排序的思想进行分组插入后，如果分组越大，那么大的数字能更快的向后移动，而分组越小，大的数字就会越慢的向后移动。相反，分组越大，那么这个序列也越不接近有序，而分组越小，反而越接近有序。 所以希尔就根据这种特点，创造了缩小增量排序的基本思想！ 简单来说： 希尔排序是按照不同步长对元素进行插入排序，==当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。==所以，希尔排序的时间复杂度会比o(n^2)好一些。 实质就是一种分组插入的思想！ 希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快 ，可看作 O(n)。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N1.3—N2）
- 稳定性：不稳定
总结：
gap 越大，大的和小的数可以更快的挪到对应的方向去 gap 越大，越不接近有序
gap 越小，大的和小的数可以更慢的挪到对应的方向去 gap 越小，就越接近有序
代码：
代码语言：javascript复制void ShellSort(int* arr, int n)
{
int gap = n;
while(gap > 1)
{
gap = (gap / 3) 1; //加一防止gap最后为0
for(int i = 0; i < n - gap; i)
{
int end = i;
int tmp = arr[end gap];
while(end >= 0)
{
if(arr[end] > tmp)
{
arr[end gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end gap] = tmp;
}
}
}3、选择排序
基本思想：（采用双向选择，同时找大找小，进行一定程度的优化） 每一次从待排序的数据元素中选出最小和最大的两个元素，存放在序列的起始位置以及末尾，直到全部待排序的数据元素排完 。 直接选择排序:
- 在元素集合 array[i] – array[n-1] 中选择关键码最大与最小的数据元素
- 若它不是这组元素中的最后一个或者第一个元素，则将它与这组元素中的最后一个或第一个元素交换
- 在剩余的 array[i] – array[n-2]（array[i 1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
代码：
代码语言：javascript复制void SelectSort(int* arr, int n)
{
int left = 0;
int right = n - 1;
//同时找最大和最小，从两边开始互换位置
while(left <= right)
{
int max = left;
int min = right;
for(int i = left; i < right 1; i)
{
if(arr[i] < min)
min = i
if(arr[i] > max)
max = i;
}
Swap(&arr[left], &arr[right]);
// 如果max和left位置重叠，max被换走了，要修正一下max的位置
if (left == max)
max = min;
Swap(&arr[right], &arr[max]);
left ;
right--;
}
}4、⏯ 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 （具体的参考二叉树中的堆的笔记） 堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN) —>向下调整的 logN 乘以 一共 N 个数
- 空间复杂度：O(1)
- 稳定性：不稳定
代码：
代码语言：javascript复制//向下调整算法（大堆）
void AdjustDown(int* arr, int n, int root)
{
int parent = root;
int child = parent * 2 1;
while(child < n)
{
if (child 1 < n && arr[child] < arr[child 1])
{
child = 1;
}
if (arr[parent] < arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 1;
}
else
break;
}
}
void HeapSort(int* arr, int n)
{
//建大堆
for(int i = (n-1-1) / 2; i >= 0; i)
AdjustDown(arr, n, i);
int end = n - 1;
while(end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
--end;
}
}5、冒泡排序
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
代码：
代码语言：javascript复制void BubbleSort(int* arr, int n)
{
for(int i = 0; i < n - 1; i)
{
int flag = 1;
for(int j = 0; j < n - 1 - i; j)
{
if(arr[j] > arr[j 1])
{
Swap(&arr[j], &arr[j 1]);
flag = 0;
}
}
if(flag == 1)
break;
}
}6、⏯ 快速排序
递归实现版本：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 将区间按照基准值划分为左右两半部分的常见方式有：（会一种即可）
- hoare版本
- 挖坑法
- 前后指针版本
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN) （递归树的深度）
- 稳定性：不稳定
在写出个版本之前，我们先写出快速排序的主函数，让各版本的快排作为子函数，减少耦合性。
代码语言：javascript复制void QuickSort(int* arr, int left, int right)
{
if(left >= right) //递归结束的条件
return;
int key = PartQuickSort(arr, left, right); //将快排作为子函数排序
QuickSort(arr, left, key -1); //继续递归调用子区间
QuickSort(arr, key 1, right);
}而在快排的主函数中，我们又可以有以下两种优化手段：
- 三数取中法 取key
- 递归到小的子区间时，可以考虑使用插入排序
对于 三数取中 与 小区间优化 的方法：
优化的产生原因： 在理想情况下，我们都希望每次更好都是二分，每行有 N 个数，共有 logN 行，所以时间复杂度为O(N*logN) 但是对于最坏的情况，就是这个数据序列本来就有序，共有 N 行，每行分别为 N、N-1、N-2、…、2、1 个，共 N(N-1)/2个。 若进行快排，则会有时间复杂度O(N^2)，效率非常低，但是我们可以发现，其实本来就不需要排多少个，居然会花了这么久的时间，所以就有了三数取中的方法，避免了这种最坏的情况。
三数取中：
将每次所给的区间中的 最左边的值 、最右边的值、 最中间的值 ，挑大小为中间的那个，并将这个数与最左边的数交换位置。（因为后面三个版本的排序都以最左边的值为key）。
代码：
代码语言：javascript复制int GetMidIndex(int* arr, int left, int right)
{
int mid = (left right) >> 1; //运用位运算符防止溢出
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[right] < a[left])
return left;
else
return right;
}
else //a[left] >= a[mid]
{
if (a[right] < a[mid])
return mid;
else if (a[left] < a[right])
return left;
else
return right;
}小区间优化: 当要排的数据序列较大的时候，递归的层数就越深，特别是最后那几层或者几十层。但是我们仔细一想，其实在快排的前面的递归中，大部分区间的数据已经是解决有序了，所以这个时候我们**可以考虑让剩下的几层或者几十层使用插入排序，进行优化，减少递归的深度，防止过多的开辟栈空间。**（效率其实是相差不大的，如今编译器对递归的优化很大，不亚于迭代）
所以将上述的两种优化放到快排的主函数中，代码如下：
代码语言：javascript复制void QuickSort(int* a, int left, int right)
{
//记得递归返回条件
if (left >= right)
return;
//分小区间，数据多的继续递归，少的就直接插入排序
//这里的小区间取不同的大小，效果不一样，得看要排的数据多大
if (right - left > 20)
{
//三数取中
int mid = GetMidIndex(a, left, right);
Swap(&a[mid], &a[left]);
int key = PartSort1(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key 1, right);
}
else
{
InsertSort(a left, right - left 1);
}
}1、hoare版本
hoare版本比较经典，就是 左右指针法 的思路。 步骤：
- 选出一个 key， 一般选最左边的值为 key，因为我们通过了三数取中的优化，不怕出现最坏的情况。
- 然后先让 right 从右边开始向左走，直到找到比 key处的值 要小的数 或者 遇到了 left。
- 若 right 找到后，就让 left 向右走，直到找到比 key处的值 要大的数 或者 遇到了 right。
- 交换 left 与 right 的值，然后一直循环，直到两个指针相遇。
- 最后将 key处的值 与 left处的值交换，将 left 作为返回值返回。
代码：
代码语言：javascript复制int hoareQuickSort(int* arr, int left, int right)
{
int key = left;
while(left < right)
{
//记得判断left < right，以及要a[right]要>=a[key]，否则死循环
while(left < right && arr[right] >= arr[key])
right--;
while(left < right && arr[left] <= arr[key])
left ;
Swap(&arr[left], &arr[right]);
}
//因为是右边先动，所以相遇时候left一定小于key的值，所以无需判断
Swap(&arr[key], &arr[left]);
return left;
}2、挖坑法
挖坑法顾名思义就是不断挖坑
