插入排序算法,今天进行了验证其稳定性,本质上来说.由于在后面的数据,相同时可以保证永远不会排在前边,因此,可以保证稳定.书上复制哨兵的算法本身要求数据要设计成 含有哨兵,非常不方便使用,并且难于阅读.因此,本算法对其进行改进,算法思路清晰明白.
/* * File: main.cpp * Author: Administrator * * Created on 2013年6月27日, 下午6:46 */ #include <cstdlib> #include <iostream> using namespace std; class A { public: A& operator = (const A& rhs){ key = rhs.key; value = rhs.value; value2 = rhs.value2; return *this; } A(int k, int v, int v2){ key = k; value = v; value2 = v2; } int key; int value; int value2; }; void printArray(A array[], int count); void insertSortByKey(A array[], int count) { for(int i = 1; i < count; ++ i) { A temp = array[i]; int j = i - 1; for(; j >= 0 ; --j) { if(array[j].key > temp.key) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = temp; printArray(array , 6); } }; void insertSortByValue(A array[], int count) { for(int i = 1; i < count; ++ i) { A temp = array[i]; int j = i - 1; for(; j >= 0 ; --j) { if(array[j].value > temp.value) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = temp; printArray(array , 6); } }; void printArray(A array[], int count){ for(int i = 0; i < count; ++ i) { std::cout<<"["<<array[i].key<<","<<array[i].value<<","<<array[i].value2<<"]"; } std::cout<<endl; } /* * */ int main(int argc, char** argv) { A values[6] = { A(4, 41, 411), A(2, 21, 211), A(3, 31, 311),A(1, 72, 121),A(1, 71, 111),A(5, 51, 511)}; insertSortByValue(values , 6); std::cout<<endl; insertSortByKey(values , 6); std::cout<<endl; printArray(values , 6); system("PAUSE"); return 0; }
