目录
一、排序的概念与应用
二、插入排序
三、希尔排序
四、选择排序
五、堆排序
六、冒泡排序
七、快速排序
1.快速排序——霍尔方法
3.前后指针法
4.快速排序的非递归实现
1.排序的概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
我们在淘宝中寻找商品时，在左上有四种排序方式：综合、信用、价格降序、价格升序。这四种方式都可以把搜索到的数据进行排序，将更符合你需要的商品放在前面。
头一个就是杨村糕干hhhh
再比如说报志愿的时候，我们要考虑学校排名、专业排名、学费高低排名……这些大学的信息很多，通过排序就可以更好地反映大学或者专业的好坏程度，帮助你做出更好的选择。
河北工业大学，河北人永远的痛……
2.常见的排序算法
排序算法主要包括：插入排序、选择排序、交换排序、归并排序
插入排序包括：直接插入排序、希尔排序
选择排序包括：选择排序、堆排序
交换排序包括：冒泡排序、快速排序
1.概念介绍
void InsertSort(int* a, int n);
时间复杂度：O(N^2)
首先拿到一个数组后，我们认为首个元素是有序的，后面的对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，将每一个未排序的数据插入合适的位置就完成了插入排序。
插入排序在实现上，通常在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2.代码实现
我们的代码都是先写单趟的排序，然后再写整个的循环。
void InsertSort(int* a,int n)//a为待排序数组，n为数组的元素个数
{
int end;//用end储存有序序列的尾下标，此时暂时不需要指出end是什么值
int temp = a[end+1];//储存无序的首元素
while (end >= 0)//最多插到下标为0处
{
if (temp < a[end])
{
a[end+1] = a[end];//把前面的数据挪到后面
end--;//继续向前找小数据
}
else
break;
}
a[end+1] = temp;
//一方面，找到比自己小的元素就插到后一位
//另一方面，在end等于0依旧比temp大的时候，此时end等于-1，end+1又回到了0
}
这个单趟排序需要将除第一个以外的所有元素进行排列，所以循环进行元素个数减一次；最开始排的元素应该是第二个元素，end+1最初等于1，故end从0开始。
//直接插入排序
void InsertSort(int* a,int n)//a为待排序数组，n为数组的元素个数
{
int i = 0;
for (i=0; i= 0)
{
if (temp < a[end])
{
a[end+1] = a[end];
end--;
}
else
break;
}
a[end+1] = temp;
}
}
1.概念介绍
void ShellSort(int* a, int n);
时间复杂度：O(N^1.3)（希尔排序的时间复杂度很难计算，但是根据统计数据大概在N的1.3次方左右）
简单地说，希尔排序是插入排序的优化版本，这个排序比较难懂，但是时间复杂度低，是可以与堆排序一较高下的优质算法。
希尔排序需要一个预排序操作，而预排序就是对数组的全部元素进行分组，然后各组的元素进行插入排序。此时我们需要一个关键变量gap，这个gap是数组元素划分间隔的标准，我们先假定gap为3，观察预排序的过程。
预排序可以让大数据更快地到达尾端，小数据更快地到达头部，让整个数组相对有序。
聪明如你可能已经想到了，当这个gap等于1时就是直接插入排序。我们需要做的就是让gap不断缩小到1就可以完成这个数组的排序了。但最后直接排序的数组已经相当有序了，所以相比插入排序它的效率会高很多。
2.代码实现
老样子，先写单趟插入排序，然后通过循环改为一组元素的预排序。
void ShellSort(int* a, int n)
{
int gap;//先不指定值
int i = 0;//完全一样的思路，不过加一减一改成了加减gap
for (i=0; i=0)
{
if(temp < a[end])
{
a[end] = a[end+gap];
end-=gap;
}
else
break;
}
}
}
然后再次改为对各组元素插入排序，各组元素的开头元素从0到gap-1，尾元素不超过n
void ShellSort(int* a, int n)
{
int gap;//先不指定值
int j = 0;
for (j=0; j=0)
{
if(temp < a[end])
{
a[end] = a[end+gap];
end-=gap;
}
else
break;
}
}
}
}
最后控制gap的大小，先让gap等于元素个数然后逐渐减小。有两种减小方式，gap=gap/2或者gap=gap/3+1,这两种方法都能保证gap最后必为1，用gap>1的条件判断，gap减小后等于1时进行一次循环就退出了。
void ShellSort(int* a, int n)
{
int gap = n;
while(gap>1)
{
gap=gap/2;
int j = 0;
for (j=0; j=0)
{
if(temp < a[end])
{
a[end] = a[end+gap];
end-=gap;
}
else
break;
}
}
}
}
}
1.概念介绍
void SelectSort(int* a, int n);
时间复杂度：O(N^2)
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
在我们的实现方法中，会在数组中同时寻找最大值和最小值，最大值放在尾部，最小值放在头部。
2.代码实现
先写单趟
void SelectSort(int* a, int n)
{
int begin = 0;//起始节点
int end = n - 1;//尾节点
int min_i = begin;
int max_i = end;//保存头尾下标
int i = 0;
for (i = begin + 1; i <= end; i++)//通过打擂台的方式找最大值
{
if (a[i] > a[max_i])
max_i = i;
if (a[i] < a[min_i])
min_i = i;
}
swap(&a[begin], &a[min_i]);//小数据放在前面
if (max_i == begin)
max_i = min_i;
swap(&a[end], &a[max_i]);//大数据放在后面
}
循环起来
// 选择排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)//两个下标向中间走
{
int min_i = begin;
int max_i = end;
int i = 0;
for (i = begin; i <= end; i++)
{
if (a[i] > a[max_i])
max_i = i;
if (a[i] < a[min_i])
min_i = i;
}
swap(&a[begin], &a[min_i]);
if (max_i == begin)//这里有一个小bug，需要修正一下
max_i = min_i;
swap(&a[end], &a[max_i]);
end--;//向前减小返回
begin++;//向后增大范围
}
}
1.概念介绍
void HeapSort(int* a, int n);
时间复杂度：O(NlogN)（log以2为底）
堆排序是一个效率十分高的排序算法，它真的可以说吊打我们学过的冒泡排序，下面介绍一下堆排序的步骤：
（1）建立大堆
你可能会想，为什么不建小堆呢？小堆可以让数组更加有序。
其实不然，小堆确实可以确定头节点为最小值，数组也相对有序。但是，你无法找到次小元素，因为小堆只保证父节点小于子节点，但是你无法判断左右子节点数据的大小。所以，我们通过建立大堆就一定可以在头节点找到最大的元素。
（2）交换首尾元素并让堆的有效数据减一
大堆的头节点一定是最大的元素，那么我们交换最大的数据到最后，它也就在了它最终该在的位置。然后有效数据减一，让整个堆不再管辖最后的这个正确位置的数据
（3）重新建堆
并不是把整个堆清空，而是将你交换到头节点的元素向下调整构成新的堆。
（4）重复上述步骤直到堆中不存在元素即可
整体思路就是堆删除数据的变形
2.代码实现
代码就直接放在这里了，内部有排序的主函数还有辅助的函数
// 堆排序
typedef struct Heap
{
int* arr;
int volume;
int size;
}HP;
void swap(int* p1, int* p2)
{
int temp = 0;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
//向上调整
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] < a[child])//改
{
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
//向下调整
void AdjustDwon(int* a, int n, int parent)
{
int need_child = parent * 2 + 1;
while (need_child < n)
{
if (a[need_child] < a[need_child + 1] && need_child + 1 < n)
{
need_child++;
}
if (a[parent] < a[need_child])
{
swap(&a[parent], &a[need_child]);
parent = need_child;
need_child = parent * 2 + 1;
}
else
break;
}
}
//主体函数
void HeapSort(int* a, int n)
{
HP s;
HP* p = &s;
p->arr = (int*)malloc(n*sizeof(int));
p->size = 0;
p->volume = n;
int i = 0;
for (i = 0; i < n; i++)
{
p->arr[p->size] = a[i];
p->size++;
AdjustUp(p->arr, p->size - 1);
}
for (i = 0; i < p->size; i++)
{
swap(&p->arr[0], &p->arr[p->size - 1 - i]);
AdjustDwon(p->arr, p->size - i - 1, 0);
}
for (i = 0; i < n; i++)
{
a[i] = p->arr[i];
}
free(p->arr);
p->size = 0;
p->volume = 0;
}
1.概念介绍
void BubbleSort(int* a, int n);
时间复杂度：O(N^2)
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
2.代码实现
// 冒泡排序
void BubbleSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int j = 0;
for (j = 0; j < n - 1 - i; j++)
{
if (a[j + 1] < a[j])
swap(&a[j + 1], &a[j]);
}
}
}
时间复杂度：O(NlogN)（log以2为底）
（1）概念介绍
int PartSort1(int* a, int left, int right);
void QuickSort1(int* a, int begin, int end);
霍尔法是快速排序最早的实现方法也是三种方法中最复杂的。
首先，讲单趟排序：
然后，讲递归：
（2）代码实现
在看代码之前还需要小小的解释一下，快速排序的思想虽然对于乱序数组的排序十分有效，但是对于一个接近有序的数组而言，这种排序的时间消耗会大大增加。
为了加快近似有序排序的速度，我们可以设置一个找中间值的函数，让我们的标准位置选取头、中间和尾部三个元素中的中间大的那一个（既不是最大，也不是最小）并交换到头部做key
//霍尔方法————快速排序递归实现
//霍尔法一定要让right先走，才可以保证key小于会和位置的数字
//霍尔法在选取key时有三种方法：
//1.取头或尾，就是begin或者end
//2.随机取一个位置
//3.在头、尾、中间位置的三个数据中找到中间大小的数据
int Getmid(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
//首先以两个下标为整体，第三个下标在前一种，在后一种，其余一种
//left mid right
//left right mid
//right left mid
//mid left right
//mid right left
//right mid left
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[right] < a[left])
return left;
else
return right;
}
else
{
if (a[right] > a[left])
return left;
else if (a[right] < a[mid])
return mid;
else
return right;
}
}
int PartSort1(int* a, int left, int right)
{
int key_i = Getmid(a, left, right);
while (left < right)
{
while (left < right && a[right] >= a[key_i])
right--;
while (left < right && a[left] <= a[key_i])
left++;
if (left < right)
swap(&a[left], &a[right]);
}
int meet_i = left;
swap(&a[meet_i], &a[key_i]);
return meet_i;
}
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key_i = PartSort1(a, begin, end);
QuickSort1(a, begin, key_i - 1);
QuickSort1(a, key_i+1, end);
}
2.快速排序——挖坑法
（1）概念介绍
int PartSort2(int* a, int left, int right);
void QuickSort2(int* a, int begin, int end);
挖坑法相比霍尔法注意的事项较少而且相对简单易懂。
首先，讲单趟排序：
递归思路与霍尔法相同
（2）代码实现
//快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int mid = Getmid(a, left, right);
swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
while (left < right)
{
//右边找小的数
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];//右边的数，填补左边的坑位
hole = right;//更新hole
//左边找小的数
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];//左边的数，填补右边的坑位
hole = left;//更新hole
}
a[hole] = key;
return hole;
}
void QuickSort2_1(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key_i = PartSort2(a, begin, end);
QuickSort2_1(a, begin, key_i - 1);
QuickSort2_1(a, key_i + 1, end);
}
（3）代码优化
快速排序的递归代码非常近似于二叉树，我们知道二叉树的节点呈指数从上到下增长，所以我们对越小的数组进行排序时排序的次数也越多，最后一层排序甚至占了整个排序过程的一半。
所以，我们可以在对大数组排序时，可以在排序小数组时使用插入排序。（此时的小子区间内的元素已经接近有序，插入排序对于z接近有序的数组排序的效率很高）
这个子数组在八个元素以下就可以使用插入排序。
//快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int mid = Getmid(a, left, right);
swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
while (left < right)
{
//右边找小的数
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];//右边的数，填补左边的坑位
hole = right;//更新hole
//左边找小的数
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];//左边的数，填补右边的坑位
hole = left;//更新hole
}
a[hole] = key;
return hole;
}
//优化
void QuickSort2_2(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//由于八个数据排序需要递归三层，而且随着层数变深，需要开辟栈帧排序的次数越多
//此时数组已经较为有序，对于较为有序的数组适合使用插入排序，从而减少了运行时间
if (end - begin <= 8)
{
InsertSort(a + begin, end - begin + 1);
}
else
{
int key_i = PartSort2(a, begin, end);
QuickSort2_2(a, begin, key_i - 1);
QuickSort2_2(a, key_i + 1, end);
}
}
（1）概念介绍
int PartSort3(int* a, int left, int right);
void QuickSort3(int* a, int begin, int end);
首先讲单趟排序：
（2）代码实现
//快速排序前后指针法
//包含两个指针——prev和cur
//prev指在最开头，cur指在第二个
//如果cur指向的元素比key_i下标的元素小，那么prev后挪一位，然后交换它们指向的值
//如果cur指向的元素大于等于key_i下标的元素，那么cur直接后挪一位
//直接后挪的操作导致了cur和prev不再是紧密相连的
//此时当cur停下来时prev和cur之间的数据都是大于key_i下标的元素的
//通过交换的方式就可以将大数和小数交换到后面和前面，从而达到局部有序的目的，最后把key_i下标的元素与prev的元素交换
int PartSort3(int* a, int left, int right)
{
int mid = Getmid(a, left, right);
swap(&a[mid], &a[left]);
int key_i = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[key_i] && ++prev != cur)//++prev != cur这一句可以防止自己和自己交换
swap(&a[prev], &a[cur]);
cur++;
}
swap(&a[key_i], &a[prev]);
return prev;
}
void QuickSort3(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key_i = PartSort3(a, begin, end);
QuickSort3(a, begin, key_i - 1);
QuickSort3(a, key_i + 1, end);
}
（1）概念介绍
我们知道递归代码虽然书写简单，但是占用空间大且速度慢。由于栈区空间很小大概只有几M，所以在排序一个大的数组时可能会出现栈溢出的问题。当我们使用非递归实现时，这些问题就都解决了。
非递归代码又需要用到栈，我们通过函数的调用堆栈发现递归的快速排序函数内部最主要的变量就是left与right，所以栈中的内容应该是数组的首尾元素的下标。
注意，如果你先入头下标后入尾下标，那么接收的时候应该先接收尾再接收头。
（2）代码实现
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
stack s;
stack* p = &s;
initstack(p);
//入栈头尾两个节点
stackpush(p, left);
stackpush(p, right);
while (!stackempty(p))
{
//出栈右节点
int end = stacktop(p);
stackpop(p);
//出栈左节点
int begin = stacktop(p);
stackpop(p);
if (begin >= end)//此时的序列要么是只有一个元素，要么是这个区间根本不存在
{
continue;
}
//进行排序
int key_i = PartSort2(a, begin, end);
//先入右节点，再入左节点
//入递归右侧区间
stackpush(p, key_i + 1);
stackpush(p, end);
//入递归左侧区间
stackpush(p, begin);
stackpush(p, key_i - 1);
}
stackdestory(p);
}
