快速排序
int partition(std::vector<int>& arr,int low,int high){int pivot = arr[low];int left = low;int right = high;while(left!=right){while(right!=left){if(arr[right]<pivot){arr[left]=arr[right];left++;break;}right--;}while(left!=right){if(arr[left]>pivot){arr[right]=arr[left];right--;break;}left++;}}arr[left]=pivot;return left;}void quickSort(std::vector<int>& arr,int low,int high){if(low<high){int pi = partition(arr,low,high);quickSort(arr,low,pi-1);quickSort(arr,pi+1,high);}}
归并排序
void myMerge(std::vector<int>& arr,int left,int middle,int right){int i = left;int j = middle+1;std::vector<int> auxiliary_vec(right-left+1,0);int n = 0;while (i<=middle&&j<=right){if(arr[i]<=arr[j]){auxiliary_vec[n]=arr[i];i++;}else{auxiliary_vec[n]=arr[j];j++;}n++;}while(i<=middle){auxiliary_vec[n]=arr[i];i++;n++;}while(j<=right){auxiliary_vec[n]=arr[j];j++;n++;}for(int k = 0;k<auxiliary_vec.size();k++){arr[left+k]=auxiliary_vec[k];}}void mergeSort(std::vector<int>& arr, int left, int right){if(left<right){int middle = left+(right-left)/2;mergeSort(arr,left,middle);mergeSort(arr,middle+1,right);myMerge(arr,left,middle,right);}}
堆排序
void heapify(std::vector<int>& arr,int n,int root){int largest = root;int left = 2*root + 1;int right = 2*root + 2;if(left<n&&arr[left]>arr[largest]){largest=left;}if(right<n&&arr[right]>arr[largest]){largest=right;}if(largest!=root){std::swap(arr[root],arr[largest]);heapify(arr,n,largest);//向下传递，选出替换节点值后的原最大节点和其子节点中的最大值}}void heapSort(std::vector<int>& arr){int n = arr.size();//构建最大堆，n/2 - 1恰好为右子树的最后一个拥有子节点的节点for(int i = n/2 - 1;i>=0;i--){heapify(arr,n,i);//向上传递，选出最大数字}//排序，逐渐移动当前最大值arr[0]到当前末尾ifor(int i = n-1;i>0;i--){std::swap(arr[0],arr[i]);heapify(arr,i,0);}}
