快速排序C++实现
发布时间:2020-12-16 07:45:25 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 //快速排序 #includeiostream #includefunctional #includeWindows.h using namespace std; void qksort(int* arr,int cnt) { functionint(int*,int,i
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 //快速排序 #include<iostream> #include<functional> #include<Windows.h> using namespace std; void qksort(int* arr,int cnt) { function<int(int*,int,int)> getPivot = [&](int* arr,int left,int right)->int { int mid = (left + right) / 2; if (arr[left] > arr[mid]) swap(arr[left],arr[mid]); if (arr[left] > arr[right]) swap(arr[left],arr[right]); if (arr[mid] > arr[right]) swap(arr[mid],arr[right]); swap(arr[mid],arr[right - 1]); return arr[right - 1]; }; function<void(int*,int)> insertSort = [&](int* arr,int begin,int end) { int i = 0,j = 0; for (i = begin + 1; i <= end; i++) { int tmp = arr[i]; for (j = i; j > begin && arr[j - 1] > tmp; j--) arr[j] = arr[j - 1]; arr[j] = tmp; } }; function<void(int*,int)> qk = [&](int* arr,int right) { if (left + 9 <= right) //当数组元素大于等于10个的时候,我们用快速排序 { int pivot = getPivot(arr,left,right); int i = left; int j = right - 1; while (1) { while (arr[++i] < pivot){} while (arr[--j] > pivot){} if (i < j) swap(arr[i],arr[j]); else break; } swap(arr[i],arr[right - 1]); qk(arr,i - 1); qk(arr,i + 1,right); } else //当数组元素小于10个的时候我们用插入排序 insertSort(arr,right); }; qk(arr,cnt - 1); }; int main() { int arr[1000]; int tmp = -1; for (int i = 0; i < 500; i++) { if (i % 2) arr[i] = i*tmp; else arr[i] = i; } for (int i = 500; i < 1000; i++) { if (i % 2) arr[i] = i*tmp; else arr[i] = i; } //我们可以对上面进行全不快排还是部分快排部分插入排序进行时间上的测试,理论上我们元素个数界限是10个,取十个在有些时候不一定是最佳的,但是可以避免一些有害的特殊情形 { LARGE_INTEGER large_interger; double dff; __int64 c1,c2; QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; qksort(arr,1000); QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; printf("计时%lf毫秒n",(c2 - c1) * 1000 / dff); } for (auto i : arr) cout << i << endl; cin.get(); return 0; } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |