归并排序
实现思想:
归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。
归并排序中一般所用到的是2-路归并排序,即将含有n个元素的序列看成是n个有序的子序列,
每个子序列的长度为1,而后两两合并,得到n/2个长度为2或1的有序子序列,再进行两两合并。。。
直到最后由两个有序的子序列合并成为一个长度为n的有序序列。
2-路归并的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
2-路归并的代码:
/*
蒋有绪的arr[start...mid]和有序的arr[mid+1...end]
合并为有序的arr[start...end]
*/
void merge(int *arr,int start,int mid,int end)
{
int i=start;
int j=mid+1;
int k=0;
//brr为辅助数组
int *brr=(int *)malloc((end-start+1)*sizeof(int));
//比较两个有序序列中的元素,将较小的元素插入到brr
while(i<=mid&&j<=end)
{
if(arr[i]<=arr[j])
brr[k++]=arr[i++];
else
brr[k++]=arr[j++];
}
//将arr 序列中剩余的元素复制到brr
while(i<=mid)
brr[k+]=arr[i++];
while(j<=end)
brr[k++]=arr[j++];
//将brr 复制到arr,使arr[start..end]有序
for(i=0;i<k;i++)
arr[i+start]=brr[i];
//释放brr所占空间
free(brr);
brr=0;
}
/*
对arr[start...end]内的元素进行归并排序
归并排序后的顺序为从小到大
*/
void sort(int *arr,int start,int end)
{
if(start<end)
{
int mid=(start+end)/2;
sort(arr,start,mid);
sort(arr,mid+1,end);
merge(arr,start,mid,end);
}
}
void merge_sort(int *arr,int len)
{
sort(arr,0,len-1);
}
为了避免递归使用malloc和free,用这种经典的实现方式
void merge(int *arr,int *brr,int start,int mid,int end)
{
int i=start;
int j=mid+1;
int k=0;
//比较两个有序序列中的元素,将较小的元素插入到brr中
while(i<=mid&&j<=end)
{
if(arr[i]<=arr[j])
brr[k++]=arr[i++];
else
brr[k++]=arr[j++];
}
while(i<=mid)
brr[k++]=arr[i++];
while(j<=end)
brr[k++]=arr[j++];
for(i=0;i<k;i++)
arr[i+start]=brr[i];
}
void sort(int *arr,int *brr,int start,int end)
{
if(start<end)
{
int mid=(start+end)/2;
sort(arr,brr,start,mid);
sort(arr,brr,mid+1,end);
merge(arr,brr,start,mid,end);
}
}
void merge_sort(int *arr,int len)
{
int *brr=(int *)malloc(len*sizeof(int));
sort(arr,brr,0,len-1);
free(brr);
brr=0;
}
归并排序的最好最坏和平均时间复杂度都是O(n*logn),但是需要额外的长度为n的辅助数组
快速排序:
实现思想
快速排序的基本思想如下:
1、从待排序列中任选一个元素作为枢轴;
2、将序列中比枢轴大的元素全部放在枢轴的右边,比枢轴小的元素全部放在其左边;
3、以枢轴为分界线,对其两边的两个子序列重复执行步骤1和2中的操作,直到最后每个子序列中只有一个元素。
void quick_sort(int *arr,int low,int high)
{
int pos;
if(low<high)
{
pos=findPos(arr,low,high);
quick_sort(arr,low,pos-1);
quick_sort(arr,pos+1,high);
}
}
/*
该函数返回分割点数值所在的位置,a为待排序数组的首地址,
low刚开始表示排序范围内的第一个元素的位置,逐渐向右移动,
high刚开始表示排序范围内的最后一个位置,逐渐向左移动
*/
int findPos(int *arr,int low,int high)
{
int val=arr[low];
while(low<high)
{
while(low<high&&arr[high]>=val)
high--;
arr[low]=arr[high];
while(low<high&&arr[low]<=val)
low++;
arr[high]=arr[low];
//最终low=high
arr[low]=val;
return low;
}
}
通常,快速排序被认为在所有同数量级(平均时间复杂度均为O(n*logn))的排序方法中,平均性能最好
所以通常枢轴元素的选择一般基于“三者取中”的原则,即比较首元素、末元素、中间元素的值,取三者中中间大小的那个。
分享到:
相关推荐
这里我们将深入探讨两种常见的排序算法:归并排序(Merge Sort)和快速排序(Quick Sort)。这两种都是基于分治策略的高效排序算法。 **归并排序**: 归并排序是一种稳定的排序算法,它通过将数据分成较小的部分,...
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
本实验旨在通过对两种经典排序算法——快速排序和归并排序的研究与实现,深入理解它们的基本原理、时间复杂度,并通过编程实践比较这两种算法在不同数据规模下的性能表现。 #### 二、快速排序 **1. 基本思想** ...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过选取一个“基准”元素,将数组分为两个子数组,使得左边的元素都小于基准,右边的元素都大于基准,然后对这...
快速排序、归并排序和堆排序都是经典且高效的排序算法,它们各自具有独特的实现方式和性能特点。这篇文章将详细探讨这三个排序算法,并对比它们的时间复杂度。 首先,我们来看快速排序。快速排序由C.A.R. Hoare在...
本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...
JAVA排序大全 冒泡 快速 选择 归并排序
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
根据给定的文件信息,我们将深入探讨两种经典的排序算法——快速排序和归并排序,并结合Java语言实现进行详细解析。 ### 快速排序算法 快速排序是一种高效的排序算法,采用分而治之的策略,其核心思想是选择一个...
**快速排序与归并排序算法比较实验报告** 在计算机科学中,排序算法是处理大量数据时不可或缺的一部分。这篇实验报告将深入探讨两种经典的排序算法——快速排序和归并排序,通过对它们在Java环境中的实现和性能测试...
以下是关于"插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序"这十大经典排序算法的详细解释: 1. 插入排序:插入排序是一种简单的排序算法,它通过构建有序...
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
本文将深入探讨三种常见的高效排序算法:堆排序、快速排序和归并排序。它们都是基于不同的原理和策略,具有各自的优势和适用场景。 首先,堆排序是一种基于比较的排序算法,利用了二叉堆的数据结构。二叉堆是一个...
以下是关于"冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序"这七种常见排序算法的源码实现及相关知识点的详细解释: 1. **冒泡排序**:冒泡排序是一种简单的排序算法,它重复地遍历待排序的...
本篇将详细探讨快速排序、希尔排序和归并排序这三种在C语言中常见的排序算法。 首先,我们来看快速排序(Quick Sort)。快速排序由C.A.R. Hoare在1960年提出,其基本思想是分治法。它的核心是选择一个基准元素,...
### 归并排序与快速排序的时间复杂度实验报告 #### 实验目的 1. **比较归并排序与快速排序在平均情况下的效率**:通过实际编程实现这两种排序算法,并使用相同的数据集测试它们的执行时间,进而判断在平均情况下哪...
本项目涵盖了五种经典的排序算法:快速排序、堆排序、归并排序、插入排序和选择排序。接下来,我们将深入探讨这些算法的原理、实现及性能特点。 1. **快速排序**: 快速排序由C.A.R. Hoare在1960年提出,是一种采用...
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...