数据结构-八大排序
八大排序
- 一，直接插入排序
- 二，希尔排序
- 三，选择排序
- 四，堆排序
- 五，冒泡排序
- 六，快速排序
- 1，递归版本
- （1）hoare法
- （2）挖坑法
- （3）前后指针法（推荐）
- 2，非递归版本
- 3，快排的优化
- （1）三数取中
- （2）小区间优化
- （3）三路划分
- 七，归并排序
- 1，递归实现
- 2，非递归实现
- 八大排序稳定性总结
一，直接插入排序
思路：
在已经有序的数据基础上再插入一个新的数据，已经有序的数据最有一个数据的下标为end，将要插入的数据与end下标的数据比较，如果小于end小标的数据，那么end小标的数据就移动到end+1小标的位置，同时–end。同时，还要注意当end减小到-1时，就要停止比较直接插入到下标为0的位置。
下面看代码：
void InsertSort(int* a, int size)
{
for (int i = 0; i < size - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
选择排序的时间复杂度：O(N^2)
空间复杂度：O(1)
二，希尔排序
希尔排序是直接插入排序的升级版本，由于当插入的值较小时，直接插入排序需要移动大量的数据，希尔排序对其做出的改进就是增加了多组预排序，将每隔gap间距的数据归为一组，一共可以分成gap组，对这gap组数据进行预排序时，在需要挪动数据的时候，数据跳动的步长大，不再像直接插入排序一样一步一步的挪动。
所以，希尔排序的单趟排序与直接插入排序十分类似，
下面看单趟排序的代码：
for(int j = 0;j < gap; j++)
{
for (int i = j; i < size - gap; i+=gap)
{
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;
}
}
上面这种写法，是每排完一组后，再排另一组，我们可以对其简化一下，直接进行多组并排：
for (int i = 0; i < size - 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;
}
下面是希尔排序的完整代码：
void ShellSort(int* a, int size)
{
int gap=size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < size - 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;
}
}
}
gap再逐渐的减小，当减小到1的时候就是直接插入排序，但此时与直接插入排序相比，数据已经大部分有序了。
希尔排序是一个较为优秀的排序
时间复杂度：O(N^1.3)
空间复杂度：O(1)
三，选择排序
选择排序的思路是：
每次遍历数组标记出最大数据的小标与最小数据的下标，分别将其与最有一个数据和开头数据进行交换。
下面看代码：
void SelectSort(int* a, int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
swep(&a[begin], &a[mini]);
if (maxi == begin)
{
maxi = mini;
}
swep(&a[maxi], &a[end]);
++begin;
--end;
}
}
这种一次循环找出最大值与最小值的下标的写法，会存在一个小问题，就是maxi与begin重合的情况，当我们对mini与begin数据交换后，此时的begin下标位置的数据就已经不是最大的数据了，所以在交换end下标与maxi下标位置的数据前要先做判断。
选择排序的时间复杂度：O(N^2)
空间复杂度：O(1)
四，堆排序
堆排序的详细过程已在之前博客讲过：
链接: 堆排序博客
void AdjustDown(int* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child+1<size&&a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
swep(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int size)
{
for (int i = (size - 2) / 2; i >= 0; i--)
{
AdjustDown(a, size, i);
}
int end = size - 1;
while (end > 0)
{
swep(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
堆排序也是一个比较优秀的排序：
时间复杂度：O(N*logN)
空间复杂度：O(1)
五，冒泡排序
不得不说，冒泡排序绝对是非常经典的排序，大量出现在教学中。
思路：
前后数据对比，若前面数据大于后面的数据就交换，这样经过第一轮的排序，最大值就被换到了末尾，这样以此往复，第二大的数据被放到倒数第二的位置…
void BubbleSort(int* a, int size)
{
for (int i = 0; i < size; i++)
{
int flag = 1;
for (int j = 0; j < size - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
flag = 0;
swep(&a[j], &a[j + 1]);
}
}
if (flag)
{
break;
}
}
}
冒泡排序也可以进行一个小的优化，定义一个flag标识符，在进行一趟的比较中，如果没有进行过数据的交换，那么就证明此时这组数据已经有序了，那么就直接break跳出循环即可。
虽然，冒泡排序大量用在教学中，但其的性能不高，
时间复杂度：O(N^2)
空间复杂度：O(1)
六，快速排序
实际中，快速排序是被应用最广泛的排序，敢叫快速排序绝不是浪得虚名哟~
快速排序的单趟排序思路：首先选一个key位置，将key下标的数据调整到它在整个数据中的正确位置，并且将key位置的左右区间拆分成与其类似的子问题。
1，递归版本
（1）hoare法
hoare法：
1，选取key位置，通常选在数据的一个个位置也就是left位置。
2，如果key选在left位置，那么right指针先动，找到比key位置数据小的数据时停住。
3，left指针再动，找到比key位置数据大的数据后停住
4，交换left，right位置的数据，以此往复前面的操作，直到left，right相遇位置。
5，相遇后，交换key位置与相遇位置的数据，此时，相遇位置的左边的数据小于等于相遇位置的数据，右边的数据大于等于相遇位置的数据。所以，这个数据就调整到了它的正确位置。
int PartSort1(int* a, int begin, int end)
{
int keyi = begin;
int left = begin;
int right = end;
while (left < right)
{
//找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
//找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
swep(&a[left], &a[right]);
}
swep(&a[keyi], &a[left]);
keyi = left;
return keyi;
}
此时，肯定有人会有疑问？为什么相遇位置的数据一定小于等于key位置的数据。
首先，相遇无非两种情况：
1，right指针找到left指针
2，left指针找到right指针
先分析1：
当right指针移动的时候，说明之前已经发生过交换，交换后left指向的一定是比key位置数据小的数据。即使是right指针第一次移动时，直接移动到了数据的最左端与left相遇，那此时的相遇位置的数据与key位置的数据相同。
再分析2：
left指针移动前，right指针肯定移动过（因为规定right指针先移动），那么此时right指向的数据一定比key位置的数据小，所以left与right相遇时，相遇的位置的数据比key位置的数据要小。
（2）挖坑法
hoare法出现后，小的细节比较多，后面也出现了许多新的放法，比如：挖坑法
1，把数组left位置的数据赋值给key，形成了第一个坑位hole就是left位置。
注意：此时的key不再是数组的下标
2，还有right指针先动，找到比key小的数据停止，将数据填到坑位中，将此时的right赋值给hole形成新的坑位。
3，left指针后动，找到别key数据大的数据停止，将其填到坑位中，将left赋值给hole，形成新的坑位。
4，right与left相遇时停止，将key填入坑位中。此时，key数据就调整到了它的正确位置。
int PartSort2(int* a, int begin, int end)
{
int key = a[begin];
int hole = begin;
int left = begin;
int right = end;
while (left < right)
{
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
（3）前后指针法（推荐）
定义一个key是数组第一个元素的下标，prev指向第一个元素，cur指向第二个元素。
1，cur指针移动，找到比key为下标的数小的时候停止。
2，++prev，交换prev与cur位置的数据。
3，当cur指向数组最有一个位置的下一个位置时，循环停止。
4，交换key下标与prev下标的数据。
int PartSort3(int* a, int begin, int end)
{
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
swep(&a[prev], &a[cur]);
}
++cur;
}
swep(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
这段代码中，可能有人会对if条件判断语句产生疑问，为什么这样写呢？
下面通过图示来解答：
上图就是，单趟循环的整个过程，我们发现前几次cur与prev指向的是同一个位置，所以就没必要进行交换。
下面看递归版本的完整代码：
int PartSort3(int* a, int begin, int end)
{
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
swep(&a[prev], &a[cur]);
}
++cur;
}
swep(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
swep(&a[begin], &a[mid]);
int keyi = PartSort3(a, begin, end);
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}
2，非递归版本
递归的写法虽然简单，但是当递归深度太深的话，就会出现问题，所以就出现了非递归的写法：
非递归是借助数据结构的栈来实现的
因为，快排是针对同一个数组的不同区间进行调整的，所以把要调整的区间存到栈中，然后每次取出栈顶的区间进行调整，调整完后将形成新的两段区间压栈。
注意：为了模拟递归的过程，要先压有段区间，再压左端区间。还有如果产生的两段区间中数据个数小于两个时，就不需要压栈了。
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
STInit(&st);
STPush(&st, end);
STPush(&st, begin);
while (!STEmpty(&st))
{
int left = STTop(&st);
STPop(&st);
int right = STTop(&st);
STPop(&st);
int keyi = left;
int cur = left + 1;
int prev = left;
while (cur <= right)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
swep(&a[prev], &a[cur]);
}
++cur;
}
swep(&a[prev], &a[keyi]);
keyi = prev;
if (keyi + 1 < right)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (left < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
3，快排的优化
当每次选的key最终都被调整到数组的中间位置时，那么快排就类似一个二分结构，时间复杂度是O(N*logN)。
（1）三数取中
当数组本身就有序或者接近有序的时候，每次key都被调整到最开始或最末尾的位置，导致快排达不到一个二分的结构，此时的时间复杂度就为O(N^2)。
为了防止这种现象的出现，采取三数取中的方式，在begin，end，一个随机位置中选出第二大的数据与begin数据做交换，在在begin位置标记为key。
这样就不会存在上述问题了
int GetMidIndex(int* a, int begin, int end)
{
int mid = begin + rand() % (end - begin);
if (a[begin] > a[end])
{
if (a[end] > a[mid])
{
return end;
}
else if (a[mid] > a[begin])
{
return begin;
}
else
{
return mid;
}
}
else
{
if (a[mid] < a[begin])
{
return begin;
}
else if (a[mid] > a[end])
{
return end;
}
else
{
return mid;
}
}
}
（2）小区间优化
正常的快排类似于一个二分的结构，
最后一层的数量要占到总数的1/2左右，最后两层占到总数的3/4左右。
由于，递归是有消耗的，所以当区间内数据量小于10个的时候，我们就用插入排序来代替快速排序，这样减少递归的消耗。
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 10)
{
InsertSort(a, (end - begin + 1));
}
int mid = GetMidIndex(a, begin, end);
swep(&a[begin], &a[mid]);
int keyi = PartSort3(a, begin, end);
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}
（3）三路划分
当要排序的一组数据中，所有数据或者说绝大多数数据相等时，也会极大的降低快排的效率。
1，left和right分别指向数组的首个元素和末尾元素，将首个元素赋值给key。
2，cur指针指向首个元素的下一个元素。
3，当cur指向的数据小于key时，交换left和cur的数据，并且left++，cur++
4，当cur指向的数据大于key时，交换right和cur的数据，并且right–。
5，当cur指向的数据等于key时，cur++。
6，当cur与right错过时，停止循环。
将数组拆分为三段，begin-left-1是小于key的数据
left到right是等于key的数据
right+1到end是大于key的数据
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 10)
{
InsertSort(a, (end - begin + 1));
}
int mid = GetMidIndex(a, begin, end);
swep(&a[begin], &a[mid]);
int left = begin;
int right = end;
int key = a[begin];
int cur = begin + 1;
while (cur <= right)
{
if (a[cur] < key)
{
swep(&a[left], &a[cur]);
++left;
++cur;
}
else if (a[cur] > key)
{
swep(&a[right], &a[cur]);
--right;
}
else
{
++cur;
}
}
QuickSort2(a, begin, left-1);
QuickSort2(a, right+1, end);
}
七，归并排序
1，递归实现
思路：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
（1）拆分：
（2）归并
递归代码实现：
void _MergeSort(int* a, int begin, int end,int* tmp)
{
if (begin >= end)
{
return;
}
int mid = begin + (end - begin) / 2;
_MergeSort(a, begin, mid,tmp);
_MergeSort(a, mid+1, end,tmp);
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[begin1];
++begin1;
}
else
{
tmp[i++] = a[begin2];
++begin2;
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
if (!tmp)
{
perror("malloc fail");
exit(-1);
}
_MergeSort(a, 0, size - 1,tmp);
free(tmp);
tmp = NULL;
}
2，非递归实现
递归调用占用堆栈的空间，每递归一次都会新开辟一块空间，这样当递归的深度太深的时候，可能会栈溢出。
由于，归并的第一步是拆分，将一个n个数据的数组，拆分成n个一个数据的数组，再归并tmp数组中，再将tmp数组拷贝回去。设定一个rangeN表示两两数组归并时，数组中的数据个数。
上面是理想状态
当数据个数不是2的整数倍的时候，会出现越界的情况，需要我们对区间进行控制。
（1）end1越界
（2）begin2越界
（3）end2越界
对上述情况做出处理：
void MergeSortNonR(int* a, int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
if (!tmp)
{
perror("malloc fail");
exit(-1);
}
int rangeN = 1;
while (rangeN < size)
{
for (int j = 0; j < size; j += rangeN * 2)
{
int begin1 = j;
int end1 = j + rangeN - 1;
int begin2 = j + rangeN;
int end2 = j + rangeN * 2 - 1;
if (end1 >= size)
{
end1 = size - 1;
begin2 = size;
end2 = size - 1;
}
else if (begin2 >= size)
{
begin2 = size;
end2 = size - 1;
}
else if (end2 >= size)
{
end2 = size - 1;
}
int i = j;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1];
++begin1;
}
else
{
tmp[i++] = a[begin2];
++begin2;
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
}
memcpy(a, tmp, sizeof(int) * size);
rangeN *= 2;
}
}
归并排序时间复杂度：O(N*logN)
空间复杂度:O(N)
八大排序稳定性总结
稳定排序：冒泡排序，插入排序，归并排序
非稳定排序：选择排序，希尔排序，堆排序，快速排序
非稳定排序的例子
1，选择排序
2，希尔排序由于进行多组预排序，当相同的数据被分配到不同组时，并且在不同组内的相对顺序不同时，就会使排序不稳定。
3，堆排序
这是一个大堆当第一个8与堆的最后一个元素交换后，将堆的节点数-1，向下调整后再与堆的最有一个元素交换时，就会破坏稳定性。
（4）快速排序
