常见的排序算法
前言
排序在我们日常的生活中起到了非常大的作用，所以今天我们就来介绍一下常见的几种排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序。
一、直接插入排序
1.1流程图演示
如图所示这里是要排升序，假设前【0~end】（这里指的是数组的下标）个数是有序的，插入排序就是将第end+1(这里指的是数组的下标)往前插入，如果end位置的这个数大于 end+1位置的这个数，那么就将end位置的值往后移（为了防止数据被覆盖的问题，所以要提前对end+1位置的值进行保存，具体代码实现等会会给），直到找到比我们刚开始end+1这个位置的值小的位置，然后我们就进行插入（这里看不懂的话可以结合下面的代码来看）。
代码实现：
//直接插入排序
void InsertSort(int* a, int size)
{
for (int i = 0; i < size - 1; i++)
{
int end = i;
int tmp = a[end + 1];//提前保存end+1位置的数据
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;//将tmp的值赋给end+1的位置
}
}
二、希尔排序
希尔排序这里我们分成两个步骤来进行排序：首先是预排序，其次是插入排序。预排序的目的就是让数据趋近于有序。
2.1流程图演示
希尔排序就是将数组分成几个组，每个数据之间相差gap个，上图所示的gap=3，因此分出了蓝、红、绿这几个组，然后分别对这几个组进行插入排序。（注意当gap=1时，就是插入排序），具体看下面的代码实现。
代码实现：
希尔排序
先预排序，再插入排序
void ShellSort(int* a, int size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
}
for (int j = 0; j < gap; j++)
{
for (int i = j; i < size - gap; i = i + gap)//防止越界，所以i<size-gap
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end = end - gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
三、选择排序
3.1流程图演示
选择排序就是通过遍历这个数组去找最大值或最小值，如果你要排升序，那你每次就找最小值，降序每次就找最大值。
代码实现：
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//选择排序
void SelectSort(int* a, int size)
{
for (int i = 0; i < size; i++)
{
int min = a[i];//假设一个最小值（这里排升序）
int mini = i;//假设最小值的下标为i
for (int j = i; j < size; j++)
{
if (a[j] < min)
{
min = a[j];
mini=j;//这里记录比min小的值的下标
}
}
Swap(&a[i], &a[mini]);//将最小值放在数组前面
}
}
四、堆排序
堆排序就是利用堆的特性进行对数据的排序，对堆的知识点有点遗忘的可以翻看我前面的几篇的博客。
总体思路：就是首先堆数据进进行建堆处理，如果排升序，就建大堆；排降序，就建小堆。若对其不太理解，可以看（二叉树-堆）这篇博客。其次将堆顶的数据和堆低的数据进行交换（这样最大值或最小值就在最后一个位置了），交换后再进行一次向下调整算法；最后通过while循环就可以完成堆排序了。
代码实现：
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//堆排序
void HeapSort(int* a, int size)
{
//首先进行建堆
for (int i = (size - 1 - 1) / 2; i>=0; i--)
{
Adjustdown(a, size, i);
}
int end= size-1;
while (end>0)
{
Swap(&a[0], &a[end]);//交换数据
Adjustdown(a, end, 0);//进行向下调算法
end--;
}
}
五、冒泡排序
5.1流程图演示
冒泡排序就是两两比较，只要不符合你的条件就交换，排完一趟之后最后一个值就是最大值或者最小值。
代码实现：
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//冒泡排序
void BubbleSort(int* a, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}
六、快速排序
6.1 hoare版本流程图演示
大概的思路就是首先确定一个key,上图将下标为0的位置的值设置为key，然后右边找小（比key要小），找到之后，左边再找大（比key要大）；其次找到之后交换他们的位置，然后继续右边找小，左边找大。最后当他们相遇时就把key的值与他们交换的位置的值进行交换。最后得到的结果就是比key大的值在key右边，比key小的值在key左边。然后用递归的思路进行排序。
代码实现
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//三数取中函数
int Getmid(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[right] < a[left])
{
return right;
}
else
return left;
}
else//a[left]> a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[right] > a[left])
{
return a[left];
}
else
return right;
}
}
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
//三数取中
int mid = Getmid(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
//右边找小
while (begin<end && a[end]>=a[keyi])
{
end=end-1;
}
//左边找大
while (begin < end && a[begin] <= a[keyi])
{
begin=begin+1;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[end]);
//[ left keyi-1] keyi [ keyi+1 right ]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
这里用了一个三数取中，这个三数取中的作用就是假如你要排升序，但是数据是降序，这就导致代码的运行效率非常低，运用这个三数取中可以不断的调整key，这样就有效避免了一些特殊情况。
6.2 前后指针法流程图演示
这个的方法和上面的hoare版本一样也是先确定一个key，然后定义一个prev指向key的位置，再定义一个cur指向prev的下一个位置。之后呢cur先去找比key位置小的值，找到之后prev往前+1，然年交换他们俩位置的值，如果他们指向的是一个同样的值，那就可以不用交换（其实交换也没事）。然后一直循环，cur找小；prev找大，直到cur指向的位置越界了，这时就交换key和prev位置的值。然后也是用递归的方法进行排序。
代码实现：
//交换函数
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//快速排序前后指针
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi =left;
int prev =left;
int cur =prev+1;
while (cur <=right)
{
if (a[cur] < a[keyi]&&prev!=cur)
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
七、快速排序非递归法
快速排序非递归这里要借助栈来实现，每次入栈和出栈都是一个区间，然后借助前面的hoare版本或者前后指针版本进行排序。
代码实现：
/快速排序前后指针
int QuickSort(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)
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
//快速排序非递归法
void QuickSortNoR(int *a,int left,int right)
{
ST p;
STInit(&p);
//将右左区间入栈
STpush(&p, right);
STpush(&p, left);
while (!IsEmpty(&p))
{
int begin = STtop(&p);
STPop(&p);
int end = STtop(&p);
STPop(&p);
int keyi = QuickSort(a, begin, end);//这里借助前后指针法来排序
//begin keyi-1 keyi keyi+1,end
if (keyi +1 < end)
{
STpush(&p, end);
STpush(&p, keyi+1);
}
if (begin<keyi-1)
{
STpush(&p, keyi-1);
STpush(&p,begin);
}
}
}
八、归并排序
归并排序就是将一个数组进行不断的分成两组，分完之后依次对这两组的每个数据进行比较，小的值放在创建的另外的一个tmp数组里面。
8.1代码实现
void _MergeSort1(int* a, int* tmp, int begin, int end)
{
if (begin>=end)//递归结束条件
{
return;
}
int mid = (begin + end) / 2;
//这时分成了[begin mid]和[mid+1 end]两组
_MergeSort1(a, tmp, begin, mid);
_MergeSort1(a, tmp, mid + 1, end);
//归并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] >= a[begin2])
{
tmp[i] = a[begin2];
i++;
begin2++;
}
if (a[begin1] < a[begin2])
{
tmp[i] = a[begin1];
i++;
begin1++;
}
}
while(begin1<=end1)
{
tmp[i] = a[begin1];
i++;
begin1++;
}
while(begin2<=end2)
{
tmp[i] = a[begin2];
i++;
begin2++;
}
memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort1(int *a,int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);//创建一个tmp数组
_MergeSort1(a, tmp, 0, size - 1);
free(tmp);
tmp=NULL;
}
归并排序非递归：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
// gap每组归并数据的数据个数
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [begin1, end1][begin2, end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
// 第二组都越界不存在，这一组就不需要归并
if (begin2 >= n)
break;
// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
if (end2 >= n)
end2 = n - 1;
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, sizeof(int) * (end2 - i + 1));
}
printf("\n");
gap *= 2;
}
free(tmp);
tmp = NULL;
}
