場景: 1.有時候需要把集合或數組裡的數據排序後展現出來時. 2.由於有些數據結構處理需要先對數組進行排序才能進行時. 文件: test_sort.cpp [cpp] #include <stdio.h> #include <algorithm> #include <stdlib.h> #include <iostream> #include <time.h> #include <assert.h> #include <vector> #include <windows.h> using namespace std; void InsertSort(vector<int>& array,size_t length) { int key = 0; for(size_t j=1;j<length;++j) { int i = j-1; key = array[j]; while(i>=0 && array[i] > key) { array[i+1] = array[i]; --i; } array[i+1] = key; } } bool cmp(int a,int b) { return a<b; } int main(int argc, char *argv[]) { printf("Hello, world\n"); //RAND_MAX srand(time(NULL)); const int kMaxNum = 100000; vector<int> v1(kMaxNum,0); for(int i=0;i<kMaxNum;++i) { v1[i] = rand()%100; } vector<int> v2(v1); //這個在windows下是毫秒級別. //1.使用庫函數排序. cout << CLOCKS_PER_SEC << endl; double time=clock(); sort(v1.begin(),v1.end(),cmp); double Inteval = clock()-time; cout << "排序耗時 單位(毫秒): " << Inteval << endl; //1.驗證排序. int pre = v1[0]; for(int i=0;i<kMaxNum;++i) { assert(v1[i] >= pre); pre = v1[i]; } //2.使用自己的排序算法. size_t length = v2.size(); time=clock(); InsertSort(v2,length); Inteval = clock()-time; cout << "插入排序耗時 單位(毫秒): " << Inteval << endl; pre = v1[0]; for(int i=0;i<kMaxNum;++i) { assert(v1[i] >= pre); pre = v1[i]; } return 0; } 輸出,執行了4次,可見插入排序的確不怎麼地: [plain] Hello, world 1000 排序耗時 單位(毫秒): 36 插入排序耗時 單位(毫秒): 32114 Hello, world 1000 排序耗時 單位(毫秒): 38 插入排序耗時 單位(毫秒): 27737 Hello, world 1000 排序耗時 單位(毫秒): 37 插入排序耗時 單位(毫秒): 32807 Hello, world 1000 排序耗時 單位(毫秒): 44 插入排序耗時 單位(毫秒): 28157
