数据结构-排序
插入排序
逻辑：从前往后选择数据，把后面的数据与前面的数据比较后插入前面。
void InsertSort(int* a, int n)//插排
{
for (int i = 0; i < n - 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）到O（n^2)
希尔排序
在插入排序的基础上，分组进行排序，把每隔gap个元素看作一组进行排序，gap每次都细分最后细分到最基本的插入排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - 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;
}
}
}希尔排序的时间复杂度为O（n^1.3)
堆排序
堆排序是一种完全二叉树，采用向下调整建堆，从下向上调整
如果在排小根堆，就把较小的孩子向上送，反之把较大的孩子往上送，向下调整建堆从第一个父亲结点向上即可，因为子叶没有孩子。
void HeapDown(int* a, int size, int parent)//正序
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n-2)/2 ; i >= 0 ; i--)
{
HeapDown(a, n, i);
}
}时间复杂度为O（nlogn）
快速排序
快速排序，在正序排列过程中，像二叉树一样把大于中间的数放到左边，小于中间的数放到右边，在新的被划分出来两个区间继续分别划分排序。
可以利用插入排序对小区间进行优化，可以用三数区中进一步优化时间复杂度。
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
if ((right - left + 1) < 10)//利用插入排序优化小区间
{
InsertSort(a + left, right - left + 1);
}
else
{
int midi = GetMidi(a, left, right);//三数区中优化
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
while (begin < end && a[end] >= a[keyi])
{
end--;//end 找小
}
while (begin < end && a[begin] <= a[keyi])
{
begin++;//begin 找大
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}三数取中
int GetMidi(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[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else
{
if (a[midi] > a[right])
{
return midi;
}
else if(a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}这个排序的时间复杂度为O（nlogn）到O（n^2)
利用栈进行非递归快速排列
注 St是栈
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STinit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
StPop(&st);
int end = STTop(&st);
StPop(&st);
int keyi = PartSortb(a, begin, end);
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}利用前后指针法继续快速排列
用两个指针 较快的指针走前面 较慢的指针走后门 如果较快的指针找到了小于keyi的值，就和慢指针进行交换（慢指针的下一个不能是快指针，如果是的话跳过），当快指针越界后，把keyi和慢指针所指的数据进行交换。
int PartSortb(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSortA(int* a, int left, int right)
{
if (left >= right)
return;
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
int keyi = PartSortb(a,left,right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}时间复杂度没有优化
归并排序
如果快速排列是二叉树向下走到子叶，那么归并排列就是从子叶回到根。
它先从小的区间进行排列gap从1步到n/2步 对每两个“子叶”进行选择排序
void _MergeSort(int* a,int* tmp,int begin,int end)
{
if (begin == end)
return;
int mid = (begin + end) / 2;
//递
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
//归
int begin1 = begin, end1 = mid, begin2 = mid+1, end2 = end, i = begin;
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);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}时间复杂度为O（nlogn）
归并排序的非递归走法
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)
{
int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + gap * 2 - 1;
int j = i;
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
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, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
