[洛谷深基]第9章 排序v202102 - 图文

选择排序思路：n次大循环，第i次大循环中，用小循环寻找数列中第i小的元素。如果发现更小的数字，则交换至第i个位置。for(inti=0;ia[j+1])swap(a[j],a[j+1]);特点：总交换次数恰为逆序对数。每次迭代都能保证至少一个（最大）元素的位置被确定。后i个元素有序，且为最大的i个元素。冒泡排序插入排序思路：n次大循环；第i次大循环将第i个元素向前交换，直至左侧元素不大于它，或抵达数列首部。for(inti=1;i=0;j--)if(a[j]>now)a[j+1]=a[j];elsebreak;a[j+1]=now;}特点：前i个元素有序。但是直到排序完成，不能保证任何一个元素的最终位置被确定（设想最小元素在数列尾部）。可以用来动态维护前k小元素，单次插入时间复杂度O??。在此场景下，第??+1小的元素将不会右移，而是被直接丢弃。可以用来理牌。