【算法导论】排序算法源码

#include "stdio.h" #include "gtest.h" #include "SK_Common.h" #include "SK_Sort.h" using testing::Test; class Test_Sort : public Test { void SetUp() { } void TearDown() { } }; bool checkSorted(int *pArray,int cnt) { if(cnt <= 0) return true; int i = 0; for(i=0;i<cnt-1;i++) if(pArray[i+1] < pArray[i]) return false; return true; } bool cmpArray(int *pArray,int *pSorted,int cnt) { if(cnt <= 0) return true; int i = 0; for(i=0;i<cnt;i++) if(pArray[i] != pSorted[i]) return false; return true; } void PrintArray(int *pArray,int cnt) { printf("\n"); int i = 0; for(i=0;i<cnt;i++) printf("%d,",pArray[i]); printf("\n"); } void SortTest(SK_SORT pFunc,const char *strFuncName) { static const int bigArray = 1024; static const int testCnt = 9; static int test1[] = {1,2,3,4,5,6,7,8,9,10}; static int stest1[] = {1,2,3,4,5,6,7,8,9,10}; static int test2[] = {10,9,8,7,6,5,4,3,2,1}; static int stest2[] = {1,2,3,4,5,6,7,8,9,10}; static int test3[] = {1}; static int stest3[] = {1}; static int test4[] = {1,1,1,1,1}; static int stest4[] = {1,1,1,1,1}; static int test5[] = {1,2,3,2,1}; static int stest5[] = {1,1,2,2,3}; static int test6[] = {3,1,4,6,5,9,7,5,1}; static int stest6[] = {1,1,3,4,5,5,6,7,9}; static int test7[] = {4,2,7,4,5,6,9,4,3,1,5,7,9,32,4,5,7,8}; static int stest7[] = {1,2,3,4,4,4,4,5,5,5,6,7,7,7,8,9,9,32}; static int test8[bigArray]; static int stest8[bigArray]; static int test9[bigArray]; static int stest9[bigArray]; static bool binit = false; int i = 0; if(!binit) { binit = true; for(i=0;i<bigArray;i++) { test8[i] = bigArray-i; stest8[i] = i+1; } for(i=0;i<bigArray;i++) { test9[i] = get_random(0,4096); stest9[i] = test9[i]; } SelectionSort(stest9,bigArray); } static struct tagTestCase { int *pArray; int *pSorted; int cnt; bool bPrint; }tests[testCnt] = {{test1,stest1,10,false}, {test2,stest2,10,false}, {test3,stest3,1,false}, {test4,stest4,5,false}, {test5,stest5,5,false}, {test6,stest6,9,false}, {test7,stest7,18,false}, {test8,stest8,bigArray,false}, {test9,stest9,bigArray,false},}; printf("%s -- TestCase:",strFuncName); for(i=0;i<testCnt;i++) { printf("%d..",i); if(tests[i].bPrint) PrintArray(tests[i].pArray,tests[i].cnt); pFunc(tests[i].pArray,tests[i].cnt); if(tests[i].bPrint) PrintArray(tests[i].pArray,tests[i].cnt); ASSERT_TRUE(cmpArray(tests[i].pArray,tests[i].pSorted,tests[i].cnt)); } printf("----OK\n"); } TEST_F(Test_Sort,QuickSort) { SortTest(QuickSort,"QuickSort"); } TEST_F(Test_Sort,QuickSort1) { SortTest(QuickSort1,"QuickSort1"); } TEST_F(Test_Sort,QuickSortRandom) { SortTest(QuickSortRandom,"QuickSortRandom"); } TEST_F(Test_Sort,InsertionSort) { SortTest(InsertionSort,"InsertionSort"); } TEST_F(Test_Sort,BubbleSort) { SortTest(BubbleSort,"BubbleSort"); } TEST_F(Test_Sort,SelectionSort) { SortTest(SelectionSort,"SelectionSort"); } TEST_F(Test_Sort,MergeSort) { SortTest(MergeSort,"MergeSort"); } TEST_F(Test_Sort,MergeSort1) { SortTest(MergeSort1,"MergeSort1"); } TEST_F(Test_Sort,HeapSort) { SortTest(HeapSort,"HeapSort"); } TEST_F(Test_Sort,CountingSort) { SortTest(CountingSort,"CountingSort"); } TEST_F(Test_Sort,RadixSort) { SortTest(RadixSort,"RadixSort"); } TEST_F(Test_Sort,BucketSort) { SortTest(BucketSort,"BucketSort"); } TEST_F(Test_Sort,QuickSearch) { int test1[] = {1,2,3,4,5,6,7,8,9,10}; int test2[] = {10,9,8,7,6,5,4,3,2,1}; int test3[] = {1}; int test4[] = {1,1,1,1,1}; int test5[] = {1,2,3,2,1}; int test6[] = {3,1,4,6,5,9,7,5,1}; int test7[] = {4,2,7,4,5,6,9,4,3,1,5,7,9,32,4,5,7,8}; ASSERT_EQ(5,QuickSearch(test1,10,5)); ASSERT_EQ(10,QuickSearch(test2,10,11)); ASSERT_EQ(1,QuickSearch(test3,1,1)); ASSERT_EQ(1,QuickSearch(test4,5,3)); ASSERT_EQ(5,QuickSearch(test6,10,6)); ASSERT_EQ(7,QuickSearch(test7,18,13)); }