直接选择排序（选择排序）

1.直接选择排序介绍直接选择排序就是每轮从待排元素中找一个最小的放到要排的位置比如第一次要排的位置是0号下标第二次要排的位置是1号下标...重复直到排完。举个生活例子就像你在班里按身高排队第一次从没排好的人里找一个最矮的放在第一位再从没排好的人里找一个第二矮的放在第二位...重复这个过程就把班里的所有人按照身高从矮到高全部排好了。和直接插入排序的对比插入排序每摸一张新牌插到手里合适位置选择排序把所有牌摊在桌上每次捡走最小的依次排成一列你不需要插来插去只需要找和换。优缺点你不需要插来插去只需要找和换。优点超级简单脑子不用转弯交换次数很少最多 n-1 次因为前面n-1个数据都是找的小的排好了最后一个数据自然就是最大的所以不用再排一轮了不管原数组什么样流程都一样不依赖数据缺点慢每次都要把剩下的全部看一遍O(n²)不稳定相等的两个数可能前后顺序会变2.直接选择排序具体过程假设数组有n个元素由上面介绍中班级按身高排队的例子可以看出来我们要想排好这n个元素只需要把下标为0~n-2位置的元素的值确定好就可以了 也就是n-1次选择待排元素中最小、第二小....第n-1小放在数组下标0、1...n-2处就可以了最后数组n-1下标对应的值自然就是最大的也就是第n小所以不需要再排一轮了。//循环n-1次选择n-1轮 for (int i 0; i n - 1; i)然后假设待排位置待排位置比如第一轮进入循环i0待排位置就是数组下标为0处的值是待排元素中最小的然后看看i1~n-1中有没有比i位置的值更小的待排元素如果有就把最小值的下标更新。int minIndex i;//假设待排元素就是最小的 for (int j i 1; j n; j)//从i1位置开始找比i位置元素更小的值 { if (arr[j] arr[minIndex]) { minIndex j;//找到了就更新最小元素的下标 } }循环退出就找到了待排元素中最小值的下标如果最小值的下标就是我们第一开始假设的下标i则不需要交换i和minIndex下标对应的值如果不是就交换。//如果假设位置就是最小的元素就没有必要进行交换 if (minIndex ! i) { int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; }3.直接选择排序完整代码//排n-1次后最后一个位置已经是最大值不需要排n次 for (int i 0; i n - 1; i) { //假设待排元素中的最小值是arr[i] int minIndex i; //从i1找有没有比i位置元素更小的值 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j;//更新最小值下标 } } //i下标的值就是待排元素中最小的就不需要交换了 if (i ! minIndex) { int tmp arr[minIndex]; arr[minIndex] arr[i]; arr[i] tmp; } }4.直接选择排序时间复杂度和稳定性时间复杂度最好/最坏/平均都是 O(n²)稳定性不稳定