后面的排序中都要用到的函数
//交换
void Swap(int* p1, int* p2)
{
int* tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}包含的头文件 "Sort.h"
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#include<string.h>
//交换
void Swap(int* p1, int* p2);
//向下调整，parent和child都是指下标，n指要调整的所有数据的上限下标
void AdjustDown(int* arr, int n, int parent);
//堆排序
void HeapSort(int* a, int n);
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n);
// 快速排序递归实现
// 快速排序hoare版本
//left:区间的左端点，right：区间的右端点（都是指下标）
int QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
//归并排序,n是数组长度
void MergeSort(int* a, int n);
//归并排序非递归实现
void MergeSortNonR(int* a, int n);一.冒泡排序
// 冒泡排序
void BubbleSort(int* a, int n)
{
//单趟：把最大的数换到最后
for (int i = 0; i < n; i++)
{
//如果一趟走完没有发生交换，说明已经有序
int flag = 1;
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
flag = 0;
}
}
if (flag == 1)
return;
}
}二.选择排序
// 选择排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n-1;
while(begin < end)
{
int mini = begin;
int maxi = end;//二者都是下标
//[i,n]中选出最大，和最小的数，分别放到begin，end的位置
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
//maxi可能和begin重叠，此时maxi换到了mini位置
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}三.插入排序
// 插入排序,O(N^2)
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
//把a[end+1]插入到[0,end]的位置
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];//大的数往后挪
end--;
}
else
{
break;
}
//出循环有两种情况：
//1.end = -1，即tmp比[0,end]之间的数都要小
//2.a[end]<tmp
a[end + 1] = tmp;
}
}
}四.堆排
//向下调整，parent和child都是指下标，n指要调整的所有数据的上限下标
void AdjustDown(int* arr, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)//child >= n,说明孩子不存在
{
//建小堆(建大堆：表示比较关系的"<",">"全部取反）
//假设法，假设左孩子小
if (arr[child + 1] < arr[child] && (child + 1) < n)//防止child+1越界
{
child++;
}
if (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
assert(a);
//1.向下调整建堆(小堆)
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)//n-1是最后一个数据的下标，(n-1-1)/2是最后一个非叶子节点
{
AdjustDown(a, n, i);
}
//2.堆顶的数据和最后一个数据进行交换，调整完的数据向下调整，再将钱n-1个数据看做一个新堆
//堆顶（最小的）数据放到数据末尾，第二小的放到倒数第二位，依次进行
int end = n - 1;
while (end > 0)
{
//交换
Swap(&a[0], &a[end]);
//调整
AdjustDown(a, end, 0);
end--;
}
}五.希尔排序
// 希尔排序，时间复杂度O(N^1.3)
void ShellSort(int* a, int n)
{
//1.分gap组
int gap = n;
while (gap > 1)
{
// +1保证最后一个gap一定是1
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;
//2.多个gap组并行
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];//大的数往后移
end -= gap;//一次跳gap步
}
else
{
break;
}
a[end + gap] = tmp;
}
}
}
}六.快速排序（快排）
三数取中
int Getmidi(int*a,int left,int right)
{
int midi = (right + left) / 2;
//左<中
if (a[left] < a[midi])
{
//中>右，中是最大的
if (a[midi] > a[right])
{
//左<右<中
if (a[left] < a[right])
{
return right;
}
else//右<左<中
{
return left;
}
}
else//左<中<右
{
return midi;
}
}
else//左>中
{
//中<左，中<右
if (a[midi] < a[right])
{
//中<左<右
if (a[left] < a[right])
{
return left;
}
else//中<右<左
{
return right;
}
}
else//右<中<左
{
return midi;
}
}
}1.快排单趟的不同版本
1.1 hoare版本
//单趟（hoare版本）
int partsort1(int*a,int left,int right)
{
//优化——keyi的选择：
// 如果数据是有序的，此时再选left位置的数当作keyi，则分割的区间就会变成0+n-1，时间复杂度退化为O(N^2)
//解决方法——三数取中：选left，right，midi（区间中间位置的数）中，中间大小的数）
int midi = Getmidi(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//左边找大，右边找小
//begin<end 这个条件要加上，否则在找大（或找小）的过程中，begin可能越过了end
while (begin < end && a[begin] < a[keyi])
{
++begin;
}
while (begin<end && a[end]>a[keyi])
{
--end;
}
//begin和end停下后，交换，把比a[keyi]大的数放右边，小的数放左边
Swap(&a[begin], &a[end]);
}
//begin和end相遇的位置（记为meet)一定比a[keyi]小(该结论可证明)，二者交换
Swap(&a[keyi], &a[begin]);
return begin;
}1.2前后指针法
//前后指针法
int partsort2(int* a, int left, int right)
{
//优化——keyi的选择：
// 如果数据是有序的，此时再选left位置的数当作keyi，则分割的区间就会变成0+n-1，时间复杂度退化为O(N^2)
//解决方法——三数取中：选left，right，midi（区间中间位置的数）中，中间大小的数）
int midi = Getmidi(a, left, right);
Swap(&a[midi], &a[left]);
int prev = left;
int cur = prev + 1;
//a[cur]<a[left]，二者同时++
//a[cur]<a[left]，cur++，prev不动
while (cur <= right)
{
//a[cur]<a[left]时，有两种情况
//prev++后，1.a[prev]<a[left] 2.a[prev]>a[left]
//若是第一种情况，则二者不需要交换，且此时prev == cur
//第二种情况，二者需要交换
if (a[cur] < a[left] && ++prev != cur)//这里的++是前置++，能保证在第一个条件满足的前提下，prev一定向前移动
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[left]);
return prev;
}
2.快排的不同版本
2.1 递归版
int QuickSort(int* a, int left, int right)
{
//结束条件：1.区间内只剩一个数；2.区间不存在
if (left >= right)
return;
//优化——小区间优化：当区间<10时，再使用函数递归调用很不划算，所以改为使用插入排序
if (right - left <= 10)
{
//区间左端：a+left，大小：right - left + 1 ([0,9]是十个数）
InsertSort(a + left, right - left + 1);
}
else
{
//单趟
int keyi = partsort1(a, left, right);
//meet将数据分割为左区间和右区间
//根据二叉树的思想，使用递归,对左右区间进行同样的操作
//[left,keyi-1] keyi [keyi+1,right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}2.2 非递归版
（栈实现的所有接口代码我会放在后面，也可看我之前的博客）
#include"Stack.h"
// 快速排序 非递归实现
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 = partsort1(a, begin, end);
//[begin,keyi-1] keyi [keyi+1,end]
//先入右区间，再入左区间，先取出的就是左区间，和递归的逻辑顺序相一致
//区间只有一个值或区间不存在时，不需要入栈
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);//栈的销毁
}七.归并排序
1.递归版
//归并排序
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;
int begin2 = mid + 1;
int i = begin;//i是tmp中的元素下标
//对进行归并的两个区间进行排序，并将排序后的结果放到tmp数组中
while (begin1 <= mid && begin2 <= end)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= mid)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end)
{
tmp[i++] = a[begin2++];
}
//将tmp数组中的数拷贝回a数组
//注意拷贝范围是归并后的两个区间和
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));//[0,9]是十个数
}
//n是数组长度
void MergeSort(int* a, int n)//主函数
{
//在主函数内创建数组，在子函数内实现排序算法
//这样可避免在递归时，子函数重复动态申请内存的过程
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
perror("malloc");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}2.非递归版
//归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc");
return;
}
int gap = 1;
while (gap < n)
{
//单趟归并
//11归并，22归并，44归并
//每次归并两组，一组含有gap个数,gap是2的次方倍
for (int i = 0; i < n; i += 2*gap)
{
//[begin1,end1] [begin2,end2]
int begin1 = i;
int end1 = begin1 + gap - 1;
int begin2 = end1 + 1;
int end2 = begin2 + gap - 1;
//对进行归并的两个区间进行排序，并将排序后的结果放到tmp数组中
//在这样的区间划分下，end1，begin2，end2都有可能会越界
//修改优化：
if (begin2 >= n)//begin2越界，说明end2肯定也越界了，此时不再需要归并
{
break;
}
if (end2 >= n)//走到这里说明begin2,end1都没有越界,修改end2后继续归并
{
end2 = n - 1;
}
int j = begin1;//j是tmp中的元素下标
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));//为防止越界，不能直接乘以2倍的gap
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}附：栈的接口代码
Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;//用数组来实现栈
int top;
int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);Stack.c
#include"Stack.h"
// 初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->arr = NULL;
pst->capacity = 0;
pst->top = 0;//top指向栈顶元素的下一位，数组下标从0开始
//top = 数据个数
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->arr);
pst->arr = NULL;
pst->capacity = 0;
pst->top = 0;
}
// 入栈 出栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)//扩容
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
STDataType* tmp = (STDataType*)realloc(pst->arr, newcapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
pst->arr = tmp;
pst->capacity = newcapacity;
}
pst->arr[pst->top++] = x;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);//栈的数据个数大于0
pst->top--;
}
// 取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);//栈的数据个数大于0
return pst->arr[(pst->top - 1)];
}
// 判空
bool STEmpty(ST* pst)
{
assert(pst);
return (pst->top == 0);
}
// 获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top ;
}
本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 常见排序算法，快排，希尔，归并，堆排
发表评论 取消回复