C++ 归并排序与快速排序
归并排序:
【算法逻辑】 归并的思路(分治)是把一个大问题a拆解成两个小问题b和c,解决了两个子问题再整合一下,就解决了原问题。用递归的方法,先分解再合并(分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突):
【代码实现】
#include<iostream> using namespace std; void Merge(int arr[], int l, int q, int r){ int n=r-l+1;//临时数组存合并后的有序序列 int* tmp=new int[n]; int i=0; int left=l; int right=q+1; while(left<=q && right<=r) tmp[i++] = arr[left]<= arr[right]?arr[left++]:arr[right++]; while(left<=q) tmp[i++]=arr[left++]; while(right<=r) tmp[i++]=arr[right++]; for(int j=0;j<n;++j) arr[l+j]=tmp[j]; delete [] tmp;//删掉堆区的内存 } void MergeSort(int arr[], int l, int r){ if(l==r) return; //递归基是让数组中的每个数单独成为长度为1的区间 int q = (l + r)/2; MergeSort(arr, l, q); MergeSort(arr, q + 1, r); Merge(arr, l, q, r); } int main(){ int a[8] = {3,1,2,4,5,8,7,6}; MergeSort(a,0,7); for(int i=0;i<8;++i) cout<<a[i]<<" "; }
关于归并排序的迭代实现可以参考我的另一篇博客:
快速排序:
【算法逻辑】
从数列中挑出一个元素,称为 “基准”(pivot); 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作; 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。这里涉及到基准的选择问题,因此必须有函数Partition()来实现“基准”。
【代码实现】
#include<iostream> using namespace std; int Parition(int a[], int low,int high){ int pivot=a[high]; int i=low; for(int j=low;j<high;++j) { //j指向当前遍历元素,如果大于等于pivot,继续向前 //如果小于当前元素,则和i指向的元素交换 if (a[j]<pivot) { swap(a[j], a[i]); i++; } } swap(a[i], a[high]); return i; } void QuickSort(int a[], int low, int high){ if(low<high) { int q=Parition(a,low, high); QuickSort(a, low, q-1); QuickSort(a, q+1,high); } } int main(){ int a[8] = {3,1,2,4,5,8,7,6}; QuickSort(a,0,7); for(int i=0;i<8;++i) cout<<a[i]<<" "; }