- 排序的概念
- 各大常用排序算法的实现
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 堆排序
- 快速排序的三种方法递归版本及非递归版本
- hoare法
- 挖坑法
- 前后指针法
- 快排的非递归版本
- 归并排序的递归版本及非递归版本
- 归并排序
- 归并排序的非递归版本
- 各类排序的性能对比
排序的概念
排序：所谓排序，就是使一串记录或者数据，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
各大常用排序算法的实现
//交换数据
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* a, int n)
// 选择排序
void SelectSort(int* a, int n);
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
冒泡排序
时间复杂度：O(
N
2
{N^2}
N2)
空间复杂度：O(1)
稳定性：稳定
思想：通过双层循环来进行遍历，每次对相邻的两个数进行比较，如果是升序（a[j]>a[j+1]），则将其交换，通过循环每次冒泡出最大的值，下一次就是次大的值，最终达到数据的有序化。
void BubbleSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n; i++)
{
int flag = 0; //如果数据是升序 可以达到O（N）
for (int j = 1; i < n - j; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);//交换数据的函数Swap
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
选择排序
时间复杂度：O(
N
2
{N^2}
N2)
空间复杂度：O(1)
稳定性：不稳定
思想：
1.通过循环来选取数据中的最大值max和最小值min。
2.把最大值max放入最后一个数据的位置，最小值min放入最开始的位置，如果数据不在对应的位置，就和这两个数据的位置进行交换。
3.在剩余（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素或者为0个元素，奇数剩余1个，偶数剩余0个。
void SelectSort(int* a, int n)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin; //用来存放最小值
int maxi = begin; //用来存放最大值
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])//如果i的值比最小值要小 就更换最小值
{
mini = i;
}
if (a[i] > a[maxi])//如果i的值比最大值要大 就更换最大值
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
//如果begin的位置和maxi的位置重叠了，就是maxi在begin的位置
//而begin刚好被mini交换走了
//就要修正下maxi的位置 就是交换后的mini；
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]); //交换数据的函数Swap
begin++;
end--;
}
}
插入排序
时间复杂度：O(
N
2
{N^2}
N2)
空间复杂度：O(1)
稳定性：稳定
思想：在一段有序的区间内，把数据插入到它对应的位置上。可以把array[i]的位置看作有序的区间，array[i+1]的位置比它大就不用动数据，比它小就把array[i+1]插入到 i 的位置上，然后array[i]这个数据后移，循环这个步骤，直至集合内的数据有序。
下面借用在网上找到的动图展示插入排序的过程
void InsertSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end]) //升序 ：如果+1位置的数小于前面的数就挪数据
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
希尔排序
时间复杂度：O(
N
1.3
{N^{1.3}}
N1.3)左右 希尔的复杂度计算非常困难，大概在1.3左右，没有到达2倍
稳定性：不稳定
思想：希尔排序是对插入排序的优化。
1.先选定一个整数，把待排序集合中所有记录分成K个组，所有距离为N的记录分在同一组内，并对每一组内的记录进行排序。
2.然后，重复上述分组和排序的工作并且缩小距离 直到N=1。
3.在N>1时所作的所有事情被称为希尔排序的预排序，目的是为了让集合更有序，当N=1时，所有记录在一组内会被排好序。
void ShellSort(int* a, int n)
{
assert(a);
int gap = n;
while (gap > 1)
{ //用gap作为距离初始距离，每次让gap/3缩小距
gap = gap / 3 + 1;//离，+1是为了最后一次gap一定为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
∗
l
o
g
2
N
{N*log{2^N}}
N∗log2N)
空间复杂度：O(1)
稳定性：不稳定
思想：这里需要借助堆的特性来进行排序。
1.利用向下调整，把数据构建成一个大堆，注意：升序要建大堆，降序小堆
2.通过循环来进行调整，每一次调整过后，堆顶的数据就是最大值，然后和堆中最后一个数据进行交换，最大值放到最后面。
3.每交换一个数据就要调整一下堆，把最后一个值不看做堆中的数据，进行调整，挑出次大值，重复此步骤，直到最后一个值。
//向下调整
void AdjustDwon(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])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
assert(a); //i从倒数第一个非叶子结点开始调整，叶子结点不用调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
int flag = n - 1; //从最后一个叶子结点开始
while (flag > 0)
{
Swap(&a[0], &a[flag]); //堆顶最大的值和最小的值交换
AdjustDwon(a, flag, 0);//调整的时候忽略掉交换后的堆最后一个值
//不把它看作堆里的数据 调整结束就是升序
flag--;
}
}
快速排序的三种方法递归版本及非递归版本
时间复杂度：O(
N
∗
l
o
g
2
N
{N*log{2^N}}
N∗log2N)
空间复杂度：O(
l
o
g
2
N
log{2^N}
log2N)
稳定性：不稳定
思想：任意取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成左右两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
//三数取中 这是快排必须用到的子函数，用来挑选key作为基准值
int GetMidIndex(int* a, int begin, int end);
{
assert(a);
int mid = (begin + end) / 2; //先取数据中间的值作为mid
if (a[begin] < a[mid])
{
if (a[mid] < a[end]) //如果begin < mid < end 中间值是:mid
{
return mid;
}
else if (a[end] < a[begin])//如果end < begin < mid中间值是:begin
{
return begin;
}
else
{
return end; //如果begin < mid 并且mid > end并且end > begin 中间值是:end
}
}
else //a[begin] > a[mid]
{
if (a[end] < a[mid]) //如果begin > mid > end 中间值是:mid
{
return mid;
}
else if (a[begin] < a[end]) //如果end > begin > mid 中间值是:begin
{
return begin;
}
else
{
return end; //如果begin>mid 并且end > mid 并且begin > end 中间值是:end
}
}
}
//快速排序
void QuickSort(int* a, int begin, int end);
//Hoare法
int PartSort1(int* a, int begin, int end);
//挖坑法
int PartSort2(int* a, int begin, int end);
//前后指针法
int PartSort3(int* a, int begin, int end);
hoare法
思想：
1.先挑选任意一个元素的值作为key基准值，这里我们实现了三数取中，假设我们选定左边第一个位置的值，再定义一个left变量表示第一个位置的值， 一个right变量表示最后一个位置的值，left目标是找比key要大的元素，right目标是找比key要小的元素。
2.一定要使用三数取中来找到数组的中间值的位置，然后和第一个位置的值进行交换，如果不使用三数取中，那么如果第一个位置的值刚好是很小的值，那么效率就会很低。
3.如果我们挑选最左边第一个元素的值作为key基准值，那么就需要右边right先走 ，反之左边先走，找比key小的值，找到了就停下来，left再走，找比key大的值，等left与right都停下来并且位置不相等时，就交换他们俩位置的值，然后重复这个步骤，直到left与right相遇，相遇的时候停下来，交换key位置和停下来的位置的值即可。
4.最后使用递归，使用重复缩小区间的范围的方式来进行排序，比如0~10区间，举例先排序0-5区间，0-5这个区间又被分成0-2和3-5两个区间，一直分割直到不可再分割为止，如果0-2和3-5区间有序后，那0-5区间就有序了，再排序6-10区间，等6-10区间有序了后，那整体也就有序了。
下面借用在网上找到的动图展示hoare法的过程
int PartSort1(int* a, int begin, int end)
{
assert(a);
int left = begin;
int right = end;
int keyi = left;//选左边做keyi就是基准值 选左边做keyi 就要右边先走
//选右边做keyi，就左边先走
int midi = GetMidIndex(a, begin, end);
Swap(&a[keyi], &a[midi]);
while (left < right)
{
//右边先走，找比keyi小的值，如果left和right相遇了也要停下来
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左边再走，找比keyi大的值，如果left和right相遇了也要停下来
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]); //交换keyi和left与right相遇的位置 相遇的位置一定比keyi要小
keyi = left;
return keyi;
}
void QuickSort(int* a, int begin, int end)
{ //这个方法与二叉树的前序遍历类似，
assert(a);
if (begin >= end)
{
return;
}
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);//递归左半区间
QuickSort(a, keyi + 1, end);//再递归右半区间
}
挖坑法
思想：
1.相比于hoare法，挖坑法并没有做出太多改变，假设我们挑选左边第一个元素的值作为key基准值，再定义一个left变量表示第一个位置的值， 一个right变量表示最后一个位置的值，left目标是找比key要大的元素，right目标是找比key要小的元素。
2.一定要使用三数取中来找到数组的中间值的位置，然后和第一个位置的值进行交换，如果不使用三数取中，那么如果第一个位置的值刚好是很小的值，那么效率就会很低。
3.先保存key基准值的值，然后right先找比key小的值，把第一个位置看作一个坑位，然后把right停下来的值放入坑位中，right的位置就变成坑位，然后left再找比key大的值，找到了就放入坑位中，left位置就是下一个坑位，最后相遇的位置放入最开始保存下来的key基准值的值。
4.最后使用递归，使用重复缩小区间的范围的方式来进行排序，比如0~10区间，举例先排序0-5区间，0-5这个区间又被分成0-2和3-5两个区间，一直分割直到不可再分割为止，如果0-2和3-5区间有序后，那0-5区间就有序了，再排序6-10区间，等6-10区间有序了后，那整体也就有序了。
下面借用在网上找到的动图展示挖坑法的过程
int PartSort2(int* a, int begin, int end)
{
assert(a);
int keyi = begin;//基准值
int midi = GetMidIndex(a, begin, end);//三数取中后的值作为keyi 基准值
Swap(&a[keyi], &a[midi]); //交换取中后的值与最左边的值 依旧是左边为基准值 右边先走的思想
int flag = a[begin]; //用flag来保存基准值 防止挖坑法 后续覆盖掉基准值
int piti = begin;//坑
while (begin < end)
{
while (begin < end && a[end] >= flag)
{
end--;
}
a[piti] = a[end];//右边找小 然后放入坑中
piti = end;//更新坑为end的位置
while (begin < end && a[begin] <= flag)
{
begin++;
}
a[piti] = a[begin];//左边找大 然后放入坑中
piti = begin;//更新坑为begin的位置
}
a[piti] = flag; //最后一个坑的值为 基准值 基准值左边比keyi小，右边反之
return piti; //返回基准值的位置
}
void QuickSort(int* a, int begin, int end)
{
assert(a);
if (begin >= end)
{
return;
}
int keyi = PartSort2(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
前后指针法
思想：
1.利用三数取中找到中间值来作为基准值，也就是key，再创建两个指针prev和cur，cur在前面遍历数组的内容，prev在后面，如果cur遇见比key要小的值，那prev++就是向后走一步，如果遇见比key大的值，那prev指针不动，cur指针继续走，直到下一个比key小的值出现，这时把cur位置的值prev++位置的值进行交换，重复此步骤，等到cur走到NULL时，prev所在的位置和key的值进行交换。
2.最后使用递归，使用重复缩小区间的范围的方式来进行排序，比如0~10区间，举例先排序0-5区间，0-5这个区间又被分成0-2和3-5两个区间，一直分割直到不可再分割为止，如果0-2和3-5区间有序后，那0-5区间就有序了，再排序6-10区间，等6-10区间有序了后，那整体也就有序了。
下面借用在网上找到的动图展示前后指针法的过程
int PartSort3(int* a, int begin, int end)
{
assert(a);
int prev = begin;
int cur = begin + 1;
int keyi = begin;
int midi = GetMidIndex(a, begin, end); //三数取中后的值作为keyi 基准值
Swap(&a[keyi], &a[midi]); //交换取中后的值与最左边的值 依旧是最左边为基准值 右边先走的思想
while (cur <= end)
{
if (a[cur] < a[keyi] && prev++ != cur) //注意: prev只有在cur小于keyi的时候才++
{
Swap(&a[prev], &a[cur]);
}
cur++; //遇见比基准值大的值后 cur++ prev不动，直到遇见下一个比基准值小的数
}
Swap(&a[prev], &a[keyi]);//把基准值交换到循环结束的位置 使基准值左右两边有序;
keyi = prev;
return keyi; //返回基准值的位置
}
void QuickSort(int* a, int begin, int end)
{
assert(a);
if (begin >= end)
{
return;
}
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
快排的非递归版本
思想：这里需要借助栈来完成非递归，利用栈的后进先出的特性，先把要排序的区间压入栈中，假设是0-10这个区间排序，先入10再入0，然后利用前后指针法，确定一个基准值key，排序后key一定是在它正确的位置上的，假设key是5，然后区间就划分为了，0-4和6-10，然后再入栈右半区间，再入左半区间，因为栈是后进先出的，所以要先入后半区间，一直循环此步骤，直至右半区间已经排好序了，然后再排左半区间，最终栈中没有区间需要排序后，数组也就完成了排序。
void QuickSortNonR(int* a, int begin, int end)
{
assert(a);
ST st;
StackInit(&st);
StackPush(&st, end); //先把end压栈
StackPush(&st, begin); //再压begin
while (!StackEmpty(&st)) //等栈中没有元素后 数组就有序了
{
int left = StackTop(&st);//left等于后压栈进去的begin
StackPop(&st);
int right = StackTop(&st); //right等于先压栈进去的end
StackPop(&st);
int keyi = PartSort3(a, left, right); //单趟排序后 keyi的左右两边有序
//a[left]-a[keyi-1] keyi a[keyi+1]-a[right] //这时候只需要把这两个区间分别排好序 整个就有序了
if (keyi + 1 < right) //如果keyi右边的区间大于1或者区间不存在就不用压栈了
{
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
if (left < keyi - 1) //左边同上 压栈后分别在排序后确定keyi 在划分为子区间继续排序 直到区间<=1为止
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
}
StackDestroy(&st);
}
归并排序的递归版本及非递归版本
时间复杂度：O(
N
∗
l
o
g
2
N
{N*log{2^N}}
N∗log2N)
空间复杂度：O(N)
稳定性：稳定
//归并排序 void MergeSort(int* a, int n); //归并排序的子函数 void _MergeSort(int* a, int begin, int end, int* tmp); //归并排序非递归版本 void MergeSortNonR(int* a, int n);
归并排序
思想：
1.先将数组划分为两个区间，利用递归分别对这两个区间进行再次划分，直到分割到一个不可再分割为止，然后进行对比大小交换数据的位置，然后进行合并，这个过程中要借助额外数组来保存比较后的数据顺序，最后拷贝回原数组，等到左半区间有序后，再递归右半区间进行排序，等左右两区间全部合并之后，总体进行一次合并, 并进行排序，最终达到整体的有序。
2.这个过程和二叉树中的后序遍历思想一样，先递归左半区间，再递归右半区间，最后再总体合并形成有序。
下面借用在网上找到的动图展示归并排序的过程
//归并排序的子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{
assert(a);
if (begin >= end) //如果区间不存在或者区间只剩一个值 就认为这个区间是有序的
{
return;
}
int mid = (begin + end) / 2;
//将这个区间划分为左右两个区间
//a[begin]-a[mid] a[mid+1]-a[end]
_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; //i不能从0开始 要和begin1的位置相同 归并的数据要和原数组的位置对应
while (begin1 <= end1 && begin2 <= end2) //比较数据 小的放在i对应的位置
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1) //上面循环结束 一定有一个数组内的数据没有完全放入tmp数组内 把剩下的数据放入tmp数组中
{
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)
{
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);//额外开的数组
assert(tmp);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
归并排序的非递归版本
思想：利用数组来进行归并，先设定一个距离值gap，每两个相差距离值的元素进行比较换位，比较之后，放入临时数组，等到数组中所有元素都排好第一遍序之后，再拷贝回原数组，然后距离值gap以2倍的方式进行增长，从最开始的一一归并，到两两归并，直到gap不小于n为止，归并的过程中有可能计算的区间会有越界的行为，记得一定要修改边界，才能完成归并，最后整体归并后，达到数组的有序。
void MergeSortNonR(int* a, int n)
{
assert(a);
int* tmp = (int*)calloc(sizeof(int) * n, sizeof(int));
assert(tmp);
int gap = 1;
while (gap < n)//gap 代表每一次归并的距离 当gap最后一次小于n时 是最后一次数组总数的归并
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i, i + gap - 1] [i + gap, i + 2 * gap - 1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//修正越界的边界
if (end1 >= n)
{
end1 = n - 1;
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}
//归并数据
int j = begin1; //i不能从0开始 要和begin1的位置相同 归并的数据要和原数组的位置对应
while (begin1 <= end1 && begin2 <= end2) //比较数据 小的放在i对应的位置
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1) //上面循环结束 一定有一个数组内的数据没有完全放入tmp数组内 把剩下的数据放入tmp数组中
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2) //这两个循环只会进去一个 不用辨别
{
tmp[j++] = a[begin2++];
}
}
//把归并后的数据拷贝回原数组
memcpy(a, tmp, sizeof(int) * n);
gap *= 2; //gap以2的次方倍 来进行两两归并
}
free(tmp);
}
各类排序的性能对比
总结：从下面的控制台运行结果就可以看出来各大常用的排序的性能差距了，以下面数组的里的十万个数组来排序的话，O(
N
∗
l
o
g
2
N
{N*log{2^N}}
N∗log2N) 的排序算法只需要不到1秒钟的时间即可排好序数组了，而O(
N
2
{N^{2}}
N2)的排序算法则需要接近5秒来完成，至于冒泡排序也是花了整整43秒才做到十万个数据的排序，这里就可以看出来O(
N
∗
l
o
g
2
N
{N*log{2^N}}
N∗log2N) 的排序算法与O(
N
2
{N^{2}}
N2)的排序算法的差距太过于明显了。
//各类排序的性能测试
void TestOP()
{
//创建7个数组，放入十万个数据来排序进行对比
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
printf("插入排序：InsertSort:%dn", end1 - begin1);
printf("希尔排序：ShellSort:%dn", end2 - begin2);
printf("选择排序：SelectSort:%dn", end3 - begin3);
printf("堆排序 ：HeapSort:%dn", end4 - begin4);
printf("快速排序：QuickSort:%dn", end5 - begin5);
printf("归并排序：MergeSort:%dn", end6 - begin6);
printf("冒泡排序：BubbleSort:%dn", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
TestOP();
return 0;
}
