1基本排序对于所有排序算法，被排序元素需要满足下列数学性质：Ø自反性（reflextive）：for all v，v=vØ对称性（antisymmetric）：for all v and w，if vv and if v=w then w=vØ传递性（transitive）：for all v，w and x，if v<=w and w<=x then v<=x对于包含这样元素的数组，我们才能对其排序。1.1选择排序(selection sort)思路与实现选择排序的思路很简单：数组的前半部分是排好序的，那么之后不断从后半部分选择出最小元素，交换到后半部分的第一个位置上。实现思路很清晰，要注意的是要用数组下标记录min的位置，然后才能swap，避免低级错误…选择排序的特点1）输入不敏感：在任何输入上的性能总是n平方，不存在最好、平均、最坏情况之分。2）数据移动最小化：key的swap次数仅为n-1。这也是在众多排序算法中，选择排序的与众不同之处。1.2冒泡排序(bubble sort)思路与实现冒泡排序不断交换两个元素的位置，将最大元素“冒泡”到数组末尾。基本排序的思想很简单，所以实现时一般循环体比较好写，难的是循环条件。例如，冒泡排序的inner loop写成j，没想好是<还是<=，结果造成最后一个元素永远不会被排序。冒泡排序与选择排序类似，在任何输入上性能都一样。但是swap次
...
继续阅读
(118)
