归并排序
归并排序
//归并merge,需要一个辅助数组
void merge(vector<int>&arr, int start, int mid, int end, vector<int>&temp) { int istart = start; int iend = mid; int jstart = mid + 1; int jend = end; while (istart <=iend&& jstart<=jend) { if (arr[istart] > arr[jstart]) { temp.push_back(arr[jstart]); jstart++; } else { temp.push_back(arr[istart]); istart++; } } while (istart <= iend) { temp.push_back(arr[istart]); istart++; } while (jstart <= jend) { temp.push_back(arr[jstart]); jstart++; } for (int i = 0; i < temp.size(); i++) { arr[start + i] = temp[i]; } temp.clear(); } void mergeSort(vector<int>&arr, int start, int end, vector<int>&temp) { if (start < end) { int mid = (start + end) / 2; mergeSort(arr, start, mid, temp); mergeSort(arr, mid + 1, end, temp); merge(arr, start, mid, end, temp); } }