wordpress编辑模板下载免费seo排名软件

交换排序：即对两个数进行交换位置而进行排序。

1.冒泡排序

思想：（以从小到大排列为例）从后向前，相邻元素两两进行比较，如果A[i]<A[i-1]，则交换位置，直至序列完，称为“第一趟排序”，结果：将最小的元素放在了序列的第一个位置；再对剩下的n-1个元素依然执行上述操作，称为“第二趟排序”，结果：将次小的元素放在了序列的第二个位置；以此类推，n-1趟结束后，可确定n-1个元素的最终位置。结束。

void BubbleSort(ElemType A[],int n)
{for(int i=1;i<=n-1;i++)    //排序趟数bool flag=false;for(int j=n-1;j>i-1;j--){if(A[j]<A[j-1])swap(A[j-1],A[j]);      //交换flag=true;}if(flag==false)   //说明这一趟排序后面的序列已经有序，则结束趟数循环break；}

分析：
①空间复杂度：O(1);
②时间复杂度：
好——原列有序：O(n)
比较次数：n-1(只进行一趟两两比较)
坏——原列逆序：O(n^2)
比较次数：n-1(第一趟)+n-2+…+1=n(n-1)/2
③稳定

2.快速排序

思想图解：

划分算法：通常以一个序列的第一个元素为基准元素进行划分；通过划分算法可以找到基准元素在序列中的最终位置（左边元素<pivot<右边元素）

int  Partition(ElemType A[],int low,int high)
{int pivotpos;//基准元素位置ElemType pivot=A[low];    //将序列中第一个元素设为基准while(low<high){while(A[high]>pivot)--high;A[low]=A[high];  //将比基准小的元素移到左边while(A[low]<pivot)++low;A[high]=A[low];  //将比基准大的元素移到右边}    //while结束时，low=high,这正是基准元素存放的最终位置A[low]=pivot;  //存放基准元素pivotpos=low;return pivotpos;   //返回基准元素的位置
}

void QuickSort(ElemType A[],int low,int high)
{
if(low<high)
{int pivotpos=Partition(A,low,high);//第一次划分QuickSort(A,low,pivotpos-1);//对左边的子表划分QuickSort(A,pivotpos+1,high);//对右边的子表划分
}
}

分析：
①空间复杂度：由于采用了递归的方式，与递归调用的最大深度一致。
好——O(log₂N)；坏——O(N)；平均——O(log₂N)
②时间复杂度：与划分是否对称有关。
坏：最大程度的不对称（顺序或逆序）——O(n²)
好：对称——O(nlog₂n)
③不稳定
④快排是内排中性能最优的算法。