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

《各种排序算法的时间复杂度.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.冒泡排序：n*n。 俩个for循环决定其时间复杂度为n^2template  void Swap(T A[], int i, int j){    T tmp = A[i];    A[i] = A[j];    A[j] = tmp;}//冒泡法bubble sorttemplate void BubSort(T A[], int n){    for (int i=0; i

2、            if (A[i] < A[j])                Swap(A, i, j);        }    }}     2.选择排序：n*n。 同样，俩个for循环决定其时间复杂度为n^2。  template  void Swap(T A[], int i, int j){    T tmp = A[i];    A[i] = A[j];    A[j] = tmp;} template void SelSort(T A[], int n){    f

3、or (int i=0; i(A, i, largIndex);    //只进行最后一次交换 

4、   }}    3.直接插入排序：n*n。 俩个for循环。//1->插入排序voidInsertSort(intarray[],intlength){　　　inti,j,key;　　　for(i=1;i=0&&array[j]>key;j--)　　　　　　　{　　　　　　　　　　　array[j+1]=array[j];　　　　　　　}　　　　　　　

5、//在合适位置安放当前元素　　　　　　　array[j+1]=key;　　　}}  //2-->插入法insert sort  template  void Swap(T A[], int i, int j){    T tmp = A[i];    A[i] = A[j];    A[j] = tmp;}//插入法insert sort template void InsSort(T A[], int n){    for (int i=1; i

6、化为1？因为在i的前面至少有一个元素，才能比较。    {        for (int j=i; (j>0) && (A[j]>A[j-1]); --j)//总是与它的前一个元素比较，j>0是为了保证j-1不会溢出        {            Swap(A, j, j-1);            }    }}      4.快速排序：