21xrx.com
2024-05-10 01:09:11 Friday
登录
文章检索 我的文章 写文章
用C/C++编程实现归并快速排序算法
2023-07-09 13:17:53 深夜i     --     --
C/C++编程 归并排序 快速排序 算法 实现

归并快速排序算法是一种常用的排序算法，能够实现对大型数据集合的快速排序。C/C++是一种广泛使用的编程语言，在实现归并快速排序算法时也可以用它来编写代码。

归并排序

归并排序是通过将一个大的数据集合分割成多个小的数据集合，将其每个子集合进行排序，最后再合并成一个完整的数据集合的过程。归并排序的具体实现步骤如下：

1. 将数据集合分割成若干个子集合，直到每个子集合只包含一个元素。

2. 将相邻的子集合进行合并，以实现更大集合的排序。

3. 重复上述过程，最后整个数据集合会被合并成一个有序的集合。

快速排序

快速排序是将数据集合按照一个元素的大小关系，分为两个子集合。其中一个子集合包含所有比分界点小的元素，另一个子集合包含所有比分界点大的元素。快速排序的具体实现步骤如下：

1. 选择一个元素作为分界点，将数据集合分为两个子集合，一个子集合包含所有小于元素的数据，另一个子集合包含所有大于等于元素的数据。

2. 对两个子集合分别进行递归排序，得到分界点的前半部分和后半部分。

3. 将前半部分、分界点、后半部分依次连接起来，形成新的有序数据集合。

归并快速排序

归并快速排序是将归并排序和快速排序两种算法组合起来使用的排序算法。归并快速排序的具体实现步骤如下：

1. 将数据集合分割为若干个子集合，每个子集合的个数不超过一个临界值。

2. 对每个小子集合使用快速排序算法进行排序。

3. 对排序后的各个小子集合进行递归归并排序，得到一个有序数据集合。

4. 重复上述过程，直到整个数据集合被拆分为单个元素，最后进行归并排序得到有序数据集合。

C/C++实现

在C/C++中，我们可以先实现快速排序和归并排序两个函数，然后再将两个函数合并实现归并快速排序。以下为C++实现代码示例：



#include<iostream>


#include<vector>


using namespace std;


void quick_sort(vector<int>& nums,int left,int right){


  if(left>=right) return;


  int i=left,j=right,pivot=nums[left];


  while(i<j){


    while(i<j&&nums[j]>=pivot) j--;


    nums[i]=nums[j];


    while(i<j&&nums[i]<=pivot) i++;


    nums[j]=nums[i];


  }


  nums[i]=pivot;


  quick_sort(nums,left,i-1);


  quick_sort(nums,i+1,right);


  return;


}


void merge(vector<int>& nums,int left,int mid,int right){


  vector<int> temp(right-left+1);


  int i=left,j=mid,k=0;


  while(i<mid&&j<=right){


    if(nums[i]<=nums[j]) temp[k++]=nums[i++];


    else temp[k++]=nums[j++];


  }


  while(i<mid) temp[k++]=nums[i++];


  while(j<=right) temp[k++]=nums[j++];


  for(int i=0;i<k;i++) nums[left+i]=temp[i];


  return;


}


void merge_sort(vector<int>& nums,int left,int right){


  if(left>=right) return;


  int mid=(left+right)/2;


  merge_sort(nums,left,mid);


  merge_sort(nums,mid+1,right);


  merge(nums,left,mid+1,right);


  return;


}


void merge_quick_sort(vector<int>& nums,int left,int right,int threshold){


  if(right-left+1<=threshold){


    quick_sort(nums,left,right);


    return;


  }


  int mid=(left+right)/2;


  merge_quick_sort(nums,left,mid,threshold);


  merge_quick_sort(nums,mid+1,right,threshold);


  merge(nums,left,mid+1,right);


  return;


}


void merge_quick_sort(vector<int>& nums){


  int threshold=8;


  merge_quick_sort(nums,0,nums.size()-1,threshold);


  merge(nums,0,threshold-1,min(2*threshold-1,int(nums.size()-1)));


  int step=threshold*2;


  while(step<=nums.size()){


    for(int i=0;i<nums.size();i+=step){


      int left=i;


      int right=min(int(i+step-1),int(nums.size()-1));


      int mid=left+threshold-1;


      if(mid>=right) continue;


      merge(nums,left,mid,right);


    }


    step*=2;


  }


}


int main(){


  vector<int> nums=2;


  merge_quick_sort(nums);


  for(int num:nums) cout<<num<<" ";


  cout<<endl;


  return 0;


}

上述代码首先实现了快速排序和归并排序两个函数，然后将快速排序的阈值设置到8，并在归并排序中使用快速排序来对数据分块，最后在归并时合并分块算法得到有序数据集合。通过上述方法，可以很方便地实现归并快速排序算法，使其在处理大型数据集合时能够快速排序。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复