1 #ifndef _SORT_H 2 #define _SORT_H 3  4 // goal: quicksort and insertsort 5 // time: 12/2/2014 6 // author: zrss 7 // reference: introduction to algorithms 8  9 class Sort {10 public:11     void quickSort(int A[], int p, int r);12     void insertSort(int A[], int p, int r);13 14 private:15     int partition(int A[], int p, int r); // for quickSort16 };17 18 int Sort::partition(int A[], int p, int r) {19     int x = A[r]; // use A[r] as pivot node20     21     int i = p - 1; // point to left part22 23     // divide A array to three part24     // A[p - i] <= x25     // A[(i + 1) - j] > x26     // A[(j + 1) - r) unknown27     for (int j = p; j < r; ++j) {28         if (A[j] <= x) {29             ++i;30             if (i != j) { // swap A[i] and A[j]31                 int temp = A[i];32                 A[i] = A[j];33                 A[j] = temp;34             }35         }36     }37 38     // exchange A[i + 1] and A[r]39     A[r] = A[i + 1];40     A[i + 1] = x;41 42     return (i + 1);43 }44 45 void Sort::quickSort(int A[], int p, int r) {46     if (p < r) {47         int q = partition(A, p, r);48         quickSort(A, p, q - 1);49         quickSort(A, q + 1, r);50     }51 }52 53 void Sort::insertSort(int A[], int p, int r) {54     for (int j = p + 1; j <= r; ++j) {55         int key = A[j];56         int i = j - 1;57         while (i >= p && A[i] > key) { // move backward58             A[i + 1] = A[i];59             --i;60         }61 62         if (i + 1 != j) { // insert A[j] to right position63             A[i + 1] = key;64         }65     }66 }67 68 69 #endif

 1 #include <cstdio> 2 #include <cstdlib> 3 #include "windows.h" 4 #include "sort.h" 5  6 int main(void) { 7     const int length = 100000; 8     int number[length]; 9 10     for (int i = 0; i < length; ++i) {11         number[i] = rand();12     }13 14     Sort sort;15 16     DWORD st = GetTickCount();17 18     sort.insertSort(number, 0, length - 1);19     //sort.quickSort(number, 0, length - 1);20 21     DWORD ed = GetTickCount();22 23     printf("InsertSort use time: %dms\n", ed - st);24     //printf("QuickSort use time: %dms\n", ed - st);25 26     system("pause");27     return 0;28 }