排序算法之插入排序、归并排序、快速排序

àì夳堔傛蜴生んèń 2022-09-30 07:05 229阅读 0赞

我的算法基本功太差了，有必要进行练习，就用经典算法——排序和搜索，来试试吧。

以下是插入排序和归并排序：

\#ifndef SomeSort\_H \#define SomeSort\_H \#include <iostream> using namespace std; /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* \*\*\*\*\*\*以下算法都是非降序排列（或者统称为升序排列）\*\*\*\*\*\*\*\*\* \*\*\*\*\*\*基本原则是：原地重排\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ template <class T> void InsertSort(T a\[\],int left,int right); template <class T> void MergeSort(T a\[\],int left,int right); template <class T> void Merge(T a\[\],int left,int mid,int right); template <class T> void Output(T a\[\],int n); /\*\*插入排序 复杂度O(n^2)\*\*/ template <class T> void InsertSort(T a\[\],int left,int right) \{ int n = right-left+1; for (int i = left+1;i < n;i++) \{ T temp = a\[i\]; int j = i-1; while(j >= 0 && temp < a\[j\]) \{ a\[j+1\] = a\[j\]; j--; \} a\[j+1\] = temp; \} \} /\*\*归并排序, 复杂度O(n\*log n) \*\*/ template <class T> void MergeSort(T a\[\],int left,int right) \{ int mid = (right+left)/2; if (left<right) \{ MergeSort(a,left,mid); MergeSort(a,mid+1,right); Merge(a,left,mid,right); \} \} /\*\*归并排序，辅助\*\*/ template <class T> void Merge(T a\[\],int left,int mid,int right) \{ T \*temp = new T\[right-left+1\];//额外开销 int i = left; int j = mid+1; int k = 0; while (i <= mid && j <= right) \{ if (a\[i\] > a\[j\]) \{ temp\[k++\] = a\[j\]; j++; \} else \{ temp\[k++\] = a\[i\]; i++; \} \} if (i > mid) while (j<=right) temp\[k++\] = a\[j++\]; if (j > right) while (i<=mid) temp\[k++\] = a\[i++\]; int end = right; while (k>0) a\[end--\] = temp\[--k\]; delete\[\] temp; \} /\*\*按照非降序（升序）打印输出\*\*/ template <class T> void Output(T a\[\],int n) \{ int i = 0; for(;i < n-1;i++) \{ cout<<a\[i\]<<","; \} cout<<a\[i\]<<endl; \} \#endif

测试代码：

\#include "SomeSort.h" void test(); int main() \{ int test\_array\[\] = \{8,5,6,-1,5,33,-9\}; int n = (int)sizeof(test\_array)/sizeof(test\_array\[0\]); Output(test\_array,n); MergeSort(test\_array,0,n-1); //InsertSort(test\_array,0,n-1); cout<<"按照非降序（升序）打印输出："<<endl; Output(test\_array,n); return 0; \}

归并排序的合并更简明的代码，在取无穷大上有BUG，仅做思路上的参考。

template <class T> void Merge(T a\[\],int left,int mid,int right) \{ int n1 = mid-left+1; int n2 = right-mid; T \*L = new T\[n1+1\];//多分配一个元素，作为哨兵 T \*R = new T\[n2+1\];//多分配一个元素，作为哨兵 int i,j; for(i = 0;i < n1;i++) L\[i\] = a\[left+i\]; for(j = 0;j < n2;j++) R\[j\] = a\[mid+1+j\]; L\[i\] = L\[i-1\]+R\[j-1\];//设为正无穷,不等于R\[n2\] R\[j\] = 2\*L\[i-1\]+2\*R\[j-1\];//设为正无穷,,不等于R\[n1\] i = 0,j = 0; for(int k = left;k <= right;k++) if(L\[i\] <= R\[j\]) a\[k\] = L\[i++\]; else a\[k\] = R\[j++\]; delete\[\] R; delete\[\] L; \}

快速排序算法实现：

/\*\*快速排序\*\*/ template <class T> void QuickSort(T a\[\],int left,int right) \{ if (left >= right) return; T pivot = a\[left\]; int i = left; int j = right+1; while(true) \{ do \{ i++; \}while (i <= right && a\[i\] <= pivot );//左边，找大于pivot的元素 do \{ j--; \}while (j >= left && a\[j\] > pivot);//右边，找不大于pivot的元素 if(i >= j) break; T t;//交换 t = a\[i\]; a\[i\] = a\[j\]; a\[j\] = t; \} a\[left\] = a\[j\]; a\[j\] = pivot; QuickSort(a,left,j-1); QuickSort(a,j+1,right); \}

以下代码的swap(),直接使用C++标准库函数<utility>即可。

/\*\*快速排序另一种实现方式\*\*/ template <class T> void Quick(T a\[\],int left,int right) \{ if(left < right) \{ int mid = Partition(a,left,right); Quick(a,left,mid-1); Quick(a,mid+1,right); \} \} template <class T> int Partition(T a\[\],int left,int right) \{ T pivot = a\[right\]; int i = left - 1; for(int j=left;j<=right-1;j++) \{ if(a\[j\]<=pivot) \{ i++; swap(a\[i\],a\[j\]); \} \} swap(a\[i+1\],a\[right\]); return (i+1); \}

谢谢。