各种排序算法的间复杂度.docxVIP

? ? 1.冒泡排序：n*n。? 俩个for循环决定其时间复杂度为n^2 template?class?T?void?Swap(T?A[],?int?i,?int?j){????T?tmp?=?A[i];????A[i]?=?A[j];????A[j]?=?tmp;}//冒泡法bubble?sorttemplateclass?T?void?BubSort(T?A[],?int?n){????for?(int?i=0;?in;?++i)????{????????for?(int?j=i+1;?jn;?++j)????????{????????????if?(A[i]??A[j])????????????????Swap(A,?i,?j);????????}????}} ? ? ? ? ? 2.选择排序：n*n。? 同样，俩个for循环决定其时间复杂度为n^2。 ??template?class?T?void?Swap(T?A[],?int?i,?int?j){????T?tmp?=?A[i];????A[i]?=?A[j];????A[j]?=?tmp;} ? templateclass?T?void?SelSort(T?A[],?int?n){????for?(int?i=0;?in;?++i)????{????????int?largIndex?=?i;????//largIndex存储元素值大的下标????????for?(int?j=i+1;?jn;?++j)????????{????????????if?(A[largIndex]??A[j])????????????????largIndex?=?j;????//发现了较大的元素，记录下它的下标????????}????????SwapT(A,?i,?largIndex);????//只进行最后一次交换????}} ? ? ? ? 3.直接插入排序：n*n。? 俩个for循环。 // 1-插入排序void InsertSort(int array[], int length){　　　 int i, j, key;　　　 for (i = 1; i length; i++)　　　 {　　　　　　　 key = array[i];　　　　　　　 // 把i之前所有大于array[i]的数据向后移动　　　　　　　 for (j = i - 1; j = 0 array[j] key; j--)　　　　　　　 {　　　　　　　　　　　 array[j + 1] = array[j];　　　　　　　 }　　　　　　　 // 在合适位置安放当前元素　　　　　　　 array[j + 1] = key;　　　 }} ? ? // 2--插入法insert?sort? ?template?class?T?void?Swap(T?A[],?int?i,?int?j){????T?tmp?=?A[i];????A[i]?=?A[j];????A[j]?=?tmp;} //插入法insert?sort?templateclass?T?void?InsSort(T?A[],?int?n){????for?(int?i=1;?in;?++i)????//i为什么要初始化为1？因为在i的前面至少有一个元素，才能比较。????{????????for?(int?j=i;?(j0)??(A[j]A[j-1]);?--j)//总是与它的前一个元素比较，j0是为了保证j-1不会溢出????????{????????????SwapT(A,?j,?j-1);????????????}????}} ? ? ? ? ? ? 4.快速排序： ? ?