数据结构与算法学习--排序（归并排序，快排序）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法学习--排序（归并排序，快排序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3177字，纯文字阅读大概需要5分钟。

内容图文

1、归并排序
归并排序使用时分治思想，就是将大问题分解成子问题，一般都是通过递归来实现。
下面是归并排序的代码实现。

void merge_sort(int a[],int left,int right)
{
    int middle = 0;
     /*递归结束条件*/
	if(left >= right)
	{
		return;
	}
	middle = (left + right)/2;
	merge_sort(a,left,middle);
	merge_sort(a,middle + 1,right);
   /*合并有序数组*/
    merge_sentry(a,middle,left,right);
	return;
}

有序数组的合并，有两种方式，一种是哨兵方式，一种纯遍历。

/*哨兵方式实现简化代码*/
void merge_sentry(int a[],int middle,int left,int right)
{
	int *pleft = NULL;
	int *pright = NULL;
	int i = 0;
	int j = 0;
	int k = 0;
	int left_size = middle - left + 1;
	int right_size = right - middle;

	
	pleft = (int *)malloc(sizeof(int)*(left_size + 1));
	assert(pleft != NULL);
	pright = (int *)malloc(sizeof(int)*(right_size + 1));
	assert(pright != NULL);

	for(i = 0; i < left_size; i ++)
	{
		pleft[i] = a[left + i];
	}
	pleft[left_size] = SORT_MAX;
	for(i = 0; i < right_size; i ++)
	{
		pright[i] = a[middle + 1 + i];
	}
	pright[right_size] = SORT_MAX;

    for (k = left,i = 0,j = 0; k <= right; k++)
	{
		if (pleft[i] <= pright[j])
		{
			a[k] = pleft[i++];
		}
		else
		{
			a[k] = pright[j++];
		}
	}

	free(pleft);
	free(pright);

    return;
}
/*两个有序数组合并*/
void merge(int a[],int middle,int left,int right)
{
    int *tmp = NULL;
	int i = 0;
	int j = 0;
	int k = 0;

	tmp = (int*)malloc((right - left + 1)*sizeof(int));
    assert(tmp != NULL);

	i = left;
	j = middle + 1;

	while(1)
	{
	    if((i > middle) || (j > right))
	    {
			break;
	    }

		if (a[i] > a[j])
		{
			tmp[k++] = a[j++];
		}
		else
		{
			tmp[k++] = a[i++];
		}
	}

	if (i > middle)
	{
		while(j <= right)
		{
			tmp[k++] = a[j++];
		}
	}
	else
	{
		while(i <= middle)
		{
			tmp[k++] = a[i++];
		}
	}
	memcpy((a + left),tmp,(right - left + 1)*sizeof(int));
	free(tmp);
	return  ;
}

快速排序
快速排序是一个原地不稳定的排序方法，时间复杂度0(nlogn)

/* SWAP 使用必须主要，不能是同一个数据进行交换*/
#define SWAP(a,b) \
do{\
	(a) ^= (b);\
	(b) ^= (a);\
	(a) ^= (b);\
}while(0)

int partition2(int a[],int left,int right)
{
   int i = left;
   int j = left;

   for(; j <  right;j++)
   {
	   if (a[j] < a[right])
	   {
		   if(i != j)
		   {
			   SWAP(a[i],a[j]);
		   }
		   i++;
	   }
   }

   if(i != right)
   {
       SWAP(a[i],a[right]);
   }

   return i;
}

int partition(int a[],int left,int right)
{
   int i = left;
   int j = right;
   int key = a[left];

   while(i < j)
   {
	   while((i < j)&& (a[j] >= key))
	   {
		   j--;
	   }
	   if (i < j)
	   {
		   a[i] = a[j];
	   }
	   while((i < j) && a[i] <= key)
	   {
		   i++;
	   }

	   if (i<j)
	   {
		   a[j] = a[i];
	   }
   }
   a[i] = key;

   return i;
}

void quick_sort(int a[],int left,int right)
{
	int q = 0;
	/*递归终止条件*/
	if (left >= right)
	{
		return;
	}

	q = partition2(a,left,right);
	quick_sort(a,left,(q - 1));
	quick_sort(a,(q + 1),right);
	return;
}

两者的区别：
都是利用分治的思想，除了下面区别外，还有实现的区别，
归并排序是从下往上的，先处理子问题再合并。快速排序是从上往下的，先分区，再处理子问题。

问题：
求无序数组的第K大元素。
求解思路就是利用快排的思想。

int partiton(int *a,int left,int right)
{
    int i = left;
    int j = right;
    int key = a[left];
    int tmp = 0;
    
    while(i < j)
    {
        while((i < j) && (a[j] < key))
        {
             j--;    
        }
        
        while ((i <j) && (a[i] > key))
        {
            i++;
        }
        if (i < j)
        {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    
    a[i] = key;
    
    return i;
}

int helper(int *nums,int left,int right,int k)
{
    int q = 0;
    
    q = partiton(nums,left,right);
    
    if (q == (k - 1))
    {
        return nums[q];
    }
    else if (q > (k-1))
    {
        return helper(nums,left,q-1,k);
    }
   
    return helper(nums,q+1,right,k);
    
  
}

int findKthLargest(int* nums, int numsSize, int k) {
   
     return helper(nums,0,numsSize-1,k);
    
}

内容总结

以上是互联网集市为您收集整理的数据结构与算法学习--排序（归并排序，快排序）全部内容，希望文章能够帮你解决数据结构与算法学习--排序（归并排序，快排序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---