// start from here int main() {
EnableMemCheck();
int arr[20]; int arr2[20]; cout << "Enter 20 numbers: "; for(int i=0; i<20; i++) {
cin >> arr[i]; arr2[i] = arr[i]; }
temp = arr[j]; arr[j] = arr[low]; arr[low] = temp;
improved_qsort(arr, low, j-1); improved_qsort(arr, i, high); }
// // the origin quick sort method //
// divide the origin number series into two part int partition(int arr[], int low, int high) {
LARGE_INTEGER liFrequency; LARGE_INTEGER liStart; LARGE_INTEGER liEnd;
QueryPerformanceFrequency(&liFrequency); // get clock frequency
QueryPerformanceCounter(&liStart); // time start improved_qsort(arr, 0, 19); QueryPerformanceCounter(&liEnd); // time end cout << "after improved_qsort(" << (liEnd.QuadPart-liStart.QuadPart)*1000000/liFrequency.QuadPart
改进的快速排序算法(C++代码)
/* * 快速排序以及改进的快速排序算法 * 2010/8/29 * 参考自《程序员面试宝典》 */
#include <iostream> #include <crtdbg.h> #include <cstdlib> #include <windows.h> // for time test using namespace std;
int i = low; int j = high; int pivot = arr[i]; while(i < j) {
while(i<j && arr[j]>=pivot) j--; if(i<j) arr[i++] = arr[j];
while(i<j && arr[i]<=pivot) i++; if(i<j) arr[j--] = arr[i]; } arr[i] = pivot; return i; }
<< "μs): "; for(int i=0; i<20; i++) cout << arr2[i] << " "; cout << endl;
system("PAUSE"); return 0;
} 程序输出：
void quick_sort(int arr[], int low, int high) {
if(low >= high) return;
int pivot_pos = partition(arr, low, high);
quick_sort(arr, low, pivot_pos-1); quick_sort(arr _DEBUG #define new new(_NORMAL_BLOCK, __FILE__, __LINE__) #endif // _DEBUG
// memory leak check inline void EnableMemCheck() {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); }
// // improved quick sort method // void improved_qsort(int arr[], int low, int high) {
if(low >= high) return;
int i = low; int j = high+1; int pivot = arr[i]; int temp;
while(i<j) {
for(i=i+1; i<high; i++) if(arr[i] >= pivot) break;
for(j=j-1; j>low; j--) if(arr[j] <= pivot) break;
if(i<j) {
temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
<< "μs): "; for(int i=0; i<20; i++) cout << arr[i] << " "; cout << endl;
QueryPerformanceCounter(&liStart); // time start quick_sort(arr2, 0, 19); QueryPerformanceCounter(&liEnd); // time end cout << "after quick_sort(" << (liEnd.QuadPart-liStart.QuadPart)*1000000/liFrequency.QuadPart